Uva-12455 – Bars

UVA-12455
তোমাকে আমি চারটি লাঠি দিলাম। ধর লাঠিগুলোর দৈর্ঘ্য ২৫,১৫,১০,৮ সেঃমিঃ। আর তোমাকে যদি বলি ১৮ দৈর্ঘ্যের একটি লাঠি বানানো সম্ভব কিনা? তুমি তো সাথে সাথে মনে মনে ভাববে এটা তো class two এর বাচ্চাকে বলতে পারতেন!! ( সামনাসামনি তো আর বলতে পারবে না!! ) আর তক্ষুনি তুমি একটা superglue আঠা দিয়ে ১০ ও ৮ দৈর্ঘ্যের লাঠি দুটো জোড়া মেরে আমার হাতে ধরিয়ে দেবে। কিন্তু তোমাকে যদি ২০০ টা লাঠি ( ভিন্ন ভিন্ন দৈর্ঘ্যের ) দিয়ে বলি p দৈর্ঘ্যের একটা লাঠি তৈরি করা সম্ভব কিনা? এখন পালাবে কোথায় বাছাধন! p অবশ্যই সবগুলো লাঠি যোগ করলে যে দৈর্ঘ্য হবে তার সমান বা ছোট হবে।
একটু চিন্তা কর কিভাবে এই problem টা solve করা যায়। তোমাকে ১৫ মিঃ সময় দিলাম।

আসলে এটা একটা DP এর কেরামতি। DP দুটি প্রধান Characteristics হলঃ ( Top-Bottom Dynamic Programming এর ক্ষেত্রে )

(১) Latest Value কে বের করার জন্য Previous Value কে Use করা।
(২) Problem এ অবশ্যই at least একটা উত্তর তোমার জানা থাকতে হবে।( Base Case)

আচ্ছা বলতো এই Problem এ জানা উত্তর টা কি? জানা উত্তর টা হল 0 দৈর্ঘ্যের একটা লাঠি তৈরি করা সম্ভব কিনা এর উত্তর সবসময় Yes. অনেক DP Problem এর ক্ষেত্রে এই জানা উত্তর টা খুবই গুরুত্বপূর্ণ ।
যেমন LCS(Longest Common Sub-sequence).

ধরি, আমাদের চারটি লাঠি আছে। ৪,৫,২,৯ সেঃমিঃ । বলা হল ১১ দৈর্ঘ্যের লাঠি তৈরি করা সম্ভব কিনা?
আচ্ছা বলতো সবচেয়ে কত বড় দৈর্ঘ্যের লাঠি তৈরি করা সম্ভব? ৪+৫+২+৯=২১
তার মানে, 0 থেকে ২১ দৈর্ঘ্যের মধ্যে Fixed কোন কোন দৈর্ঘ্যের জন্য লাঠি তৈরি করা সম্ভব আমাদের সেটাই বের করতে হবে।

আমরা একটা Array Use করব। নাম দিলাম identifier[i] .এর মান হবে কেবল 0 অথবা ১
i তম Value-র মান 0 মানে i দৈর্ঘ্যের লাঠি তৈরি করা সম্ভব না। আর i তম Value-র মান ১ মানে i দৈর্ঘ্যের লাঠি তৈরি করা সম্ভব।
প্রথমে ধরি একটা দৈর্ঘ্যের জন্যও লাঠি তৈরি করা সম্ভব না। তাহলে,
for(i=0;i> এই ধাপে প্রথম লাঠির দৈর্ঘ্য 4সেঃমিঃ।
>> Previous Information(Before this step): 0 দৈর্ঘ্যের জন্য লাঠি তৈরি সম্ভব অর্থাৎ identifier[0]=1;
>>Updated Information(In this step): 0+4=4 দৈর্ঘ্যের জন্য লাঠি তৈরি সম্ভব অর্থাৎ identifier[4]=1;
*Grand Information(After processing this step):
identifier[0]=1;
identifier[4]=1;

Step-2

>> এই ধাপে প্রথম লাঠির দৈর্ঘ্য 5সেঃমিঃ।
>> Previous Information(Before this step): 0,4 দৈর্ঘ্যের জন্য লাঠি তৈরি সম্ভব অর্থাৎ identifier[0]=1;
identifier[4]=1;
>>Updated Information(In this step): 0+5=5,4+5=9 দৈর্ঘ্যের জন্য লাঠি তৈরি সম্ভব অর্থাৎ identifier[5]=1;
identifier[9]=1;
*Grand Information(After processing this step):
identifier[0]=1;
identifier[4]=1;
identifier[5]=1;
identifier[9]=1;

Step-3

>> এই ধাপে প্রথম লাঠির দৈর্ঘ্য 2সেঃমিঃ।
>> Previous Information(Before this step): 0,4,5,9 দৈর্ঘ্যের জন্য লাঠি তৈরি সম্ভব অর্থাৎ
identifier[0]=1;
identifier[4]=1;
identifier[5]=1;
identifier[9]=1;
>>Updated Information(In this step): 0+2=2,4+2=6,5+2=7,9+2=11 দৈর্ঘ্যের জন্য লাঠি তৈরি সম্ভব অর্থাৎ
identifier[2]=1;
identifier[6]=1;
identifier[7]=1;
identifier[11]=1;

*Grand Information(After processing this step):
identifier[0]=1;
identifier[4]=1;
identifier[5]=1;
identifier[9]=1;
identifier[2]=1;
identifier[6]=1;
identifier[7]=1;
identifier[11]=1;

Step-4

>> এই ধাপে প্রথম লাঠির দৈর্ঘ্য 9সেঃমিঃ।
>> Previous Information(Before this step): 0,4,5,9,2,6,7,11 দৈর্ঘ্যের জন্য লাঠি তৈরি সম্ভব অর্থাৎ
identifier[0]=1;
identifier[4]=1;
identifier[5]=1;
identifier[9]=1;
identifier[2]=1;
identifier[6]=1;
identifier[7]=1;
identifier[11]=1;
>>UpdatedInformation(In this step): 0+9=9,4+9=13,5+9=14,9+9=18,2+9=11,6+9=15,7+9=16,11+9=20 দৈর্ঘ্যের জন্য লাঠি তৈরি সম্ভব অর্থাৎ
identifier[9]=1;
identifier[13]=1;
identifier[14]=1;
identifier[18]=1;
identifier[11]=1;
identifier[15]=1;
identifier[16]=1;
identifier[20]=1;

*Grand Information(After processing this step):
identifier[0]=1;
identifier[4]=1;
identifier[5]=1;
identifier[9]=1;
identifier[2]=1;
identifier[6]=1;
identifier[7]=1;
identifier[11]=1;
identifier[9]=1;
identifier[13]=1;
identifier[14]=1;
identifier[18]=1;
identifier[11]=1;
identifier[15]=1;
identifier[16]=1;
identifier[20]=1;

তাহলে যে যে দৈর্ঘ্যের জন্য লাঠি তৈরি করা সম্ভব টা হলঃ
0,2,4,5,6,7,9,11,13,14,15,16,18,20
কেউ যদি জানতে চায় m দৈর্ঘ্যের লাঠি তৈরি করা সম্ভব কিনা, তাহলে identifier[m] এর মান যদি ১ হয় তাহলে সম্ভব , যদি 0 হয় তাহলে সম্ভব নয়।

আশা করি Problem এর Base টা তোমাদের Clear হয়েছে। তাহলে আর দেরি না করে ঝটপট এই প্রবলেম টা Solve করে ফেলো। UVA 12455 এবং UVA 562

এই পোস্টটি যদি পুরপুরি না বুঝতে পার তাহলে কোথায় বুঝলেনা আমাকে জানাতে পারো। তারপরও যদি না পারো তাহলে “Solution” এই Menu তে Code দেখতে পারবে। তবে ভালভাবে না বুঝে Code দেখা ঠিক হবেনা।

এই পোস্টটি PDF Format এ Download