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

Uva-674 – Coin Change

Short Problem Description:

Given the 5 coins 1,5,10,25,30 and an amount( assume, taka). You have to find the number of ways the amount can be made using these 5 coins.

Solution Approach:

This is an easy dp problem. So try to find overlapping sub-problem,
recurrence relation and also base case. This is a common technique to solve a dp problem.

In this problem I will try to find these…At first I declare a function f(i,j) which returns the number of ways of j taking first i coins.

Now,

f(i,j)=0, if i==0 base case
f(i,j)=1, if j<5 base case
f(i,j)=f(i-1,j) ,if(j-coin[i])=0 recurrence relation

Problem Link: Click Here

My Code: Click Here

Uva-10450 – World Cup Noise

Short Problem Description:

Given n. You have to output how many bit string of length n is possible so that no consecutive 1 exists. As for example, if n=3, then there are total 2^3=8 bit string possible. They are 000, 001, 010, 011, 100, 101, 110, 111. But among these 011, 110, 111 have the bit string with consecutive 1. So answer is 8-3=5.
Solution Trick:

The logic of this problem goes to Tree Diagram. Simply try to draw a tree with 0 and 1 so that no consecutive 1 remains together. Then see, the logic is just Fibonacci Series.

My Code: Click Here

Uva-10003 – Cutting Sticks

Solution Trick:

The problem goes to the simple Dynamic Programming. Just divide the problem into similar subproblems and write an efficient code. Actually,
for dp problem idea is very important for solving. So try to develop your own Algorithm.

My Code: Click Here