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

Problem-16(Power digit sum)

2¹⁵ = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2¹⁰⁰⁰?

Solution Trick:

The logic goes to childhood multiplication process. What can we do when we want to multiply a big number a( such as a=9999999999999) by a number b (such as b=2 ) . We continuously multiply the rightmost digit of a by b until we reach the leftmost digit of a.

My Solution: Click Here

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.

Top-Down Solution

Bottom-Up Solution