Skip to content

UVA Problem: 136(Steps)

October 5, 2011

Problem Statment:

Problem Explanation:

There exist a direct formula but I prefer this algorithm since there is no floating point calculation present here and its faster.

Here goes my algorithm

First find what is the maximum sum that can be made usingn element- 
if n=1 -> 1 sum=1; 
if n=2 -> 1,1 sum=2; 
if n=3 -> 1,2,1 sum=4;
if n=4 -> 1,2,2,1 sum=6; 
if n=5 -> 1,2,3,2,1 sum=9; 
if n=6 -> 1,2,3,3,2,1 sum=12;  
if n=100000 -> .................... 
Declare an Array , A[i] and populate it with the above calculation like A[1]=1, A[2]=2, A[3]=4, A[4]=6 
and so on. Now consider the input.  

Suppose you are given- 45 50 calculate the difference that is 5. Using 3 element you can't make 5, 
at most 4 can be made, but using 4 element you can make 6 , so its certainly possible to make 5, 
Like 1 2 1 1. So the result is 4. 

So you only need a binary search to find out the minimum index i in A[] that is A[i]>= difference.
 And thats all. n=100000 is enough to hold the 31 bit number. Hope Its understandable. 
No comments yet

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: