Category Dynamic Programming

Mar 18 2013

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

Mar 16 2013

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

Mar 3 2013

Minimum Steps to One

 

Problem : Minimum Steps to One

Problem Statement: On a positive integer, you can perform any one of the following 3 steps. 1.) Subtract 1 from it. ( n = n – 1 )  , 2.) If its divisible by 2, divide by 2. ( if n % 2 == 0 , then n = n / 2  )  , 3.) If its divisible by 3, divide by 3. ( if n % 3 == 0 , then n = n / 3  ). Now the question is, given a positive integer n, find the minimum number of steps that takes n to 1
eg: 1.)For n = 1 , output: 0       2.) For n = 4 , output: 2  ( 4  /2 = 2  /2 = 1 )    3.)  For n = 7 , output: 3  (  7  -1 = 6   /3 = 2   /2 = 1 )
Approach / Idea: One can think of greedily choosing the step, which makes n as low as possible and conitnue the same, till it reaches  1. If you observe carefully, the greedy strategy doesn’t work here. Eg: Given n = 10 , Greedy –> 10 /2 = 5  -1 = 4  /2 = 2  /2 = 1  ( 4 steps ). But the optimal way is –> 10  -1 = 9  /3 = 3  /3 = 1 ( 3 steps ). So, we need to try out all possible steps we can make for each possible value of n we encounter and choose the minimum of these possibilities.
It all starts with recursion :).  F(n) =   1 + min{  F(n-1) ,  F(n/2)  ,  F(n/3)  }  if (n>1) , else 0  ( i.e., F(1) = 0 ) . Now that we have our recurrence equation, we can right way start coding the recursion. Wait.., does it have over-lapping subproblems ?  YES. Is the optimal solution to a given input depends on the optimal solution of its subproblems ? Yes… Bingo ! its DP 🙂 So, we just store the solutions  to the subproblems we solve and use them later on, as in memoization.. or we start from bottom and move up till the given n, as in dp.