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. 
Advertisements

UVA Problem: 12293 ( Box Game)

October 5, 2011

Problem Statement:

This problem seems complicated at fast glance. But there is a hidden pattern inside solution.  Problem statement says –

One of them contains n balls, while the other box contains one ball.

Forget the other box , just consider the box with n balls.

Remember , Alice moves first , Both try to win and play perfectly.

Let’s Define ,

Game(t)=Win , if a player  get (t ) ball and his move leads to win the game.

Game(t)=Lose , if a player  get (t ) ball and his move leads to lose the game.

Now try to generate pattern-

n=2 , which can be split into (1+1) , Bob can’t take the ball next turn So winner is  Alice,  so  Game(2)=Win.

n=3 , which can be split into (2+1) ,  So Bob get 2 ball and its his turn, and we previously computed that Game(2)=Win, so Bobs win and Alice Lose that means Game(3)=Lose.

n=4, which can be split into (2+2) or (3+1), Alice want to to give bob that number of ball so that Bob Lose.  If she give Bob 3 ball then Bob will certainly lose since Game(3)=Lose. So in this case Alice will win , so Game(4)=Win.

If you go on that way you will be able to generate a pattern when Alice/Bob will win.

UVA Problem: 1152 (4 Values whose Sum is 0)

October 5, 2011

Problem Statement

Problem Explanation:

The main concern of this problem is to develop a fast algorithm. The O(n^4) or O(n^3) algorithm is not enough to pass the time limit. So we need a O((n^2)lg(n)) algorithm.

Ok, Here is my O(n^2lg(n)) algorithm-

Suppose there is four array A[], B[], C[], D[]. we want to find the number of way A[i]+B[j]+C[k]+D[l] = 0 can be made where 0 <= i,j,k,l < n.

So sum up all possible arrangement of A[] and B[] and place them in another array E[] that contain n*n number of element.

int k=0; for(i=0;i<n;i++) { for(j=0;j<n;j++) { E[k++]=A[i]+B[j]; } } 

The complexity of above code is O(n^2).

Do the same thing for C[] and D[].

int l=0; for(i=0;i<n;i++) { for(j=0;j<n;j++) { AUX[l++]=C[i]+D[j]; } } 

The complexity of above code is O(n^2).

Now sort AUX[] so that you can find the number of occurrence of unique element in AUX[] easily.

Sorting complexity of AUX[] is O(n^2 lg(n^2)).

now declare a structure-

struct myHash { int value; int valueOccuredNumberOfTimes; }F[]; 

Now in structure F[] place the unique element of AUX[] and number of time they appeared.

It’s complexity is O(n^2)

possibleQuardtupple=0; 

Now for each item of E[], do the following

for(i=0;i<k;i++) { x=E[i]; find -x in structure F[] using binary search. if(found in j'th position) { possibleQuardtupple+=number of occurrences of -x in F[j]; } } For loop i ,total n^2 number of iteration is performed and in each iteration for binary search lg(n^2)
comparison is done. So Here complexity is O(n^2 lg(n^2)) which is mathmatically  O(n^2 lg(n)).

And the overall complexity of above program is O(n^2 lg(n)). You can speed up program run time by some
modification. But the overall complexity is remain same.


Now you can use stl map/ binary search. But stl map is slow, so its better to use binary search.

Hope my explanation is clear enough to understand.

Acm Problem: Graph Construction(10720) + Dream (11414)

July 31, 2011

Acm Problem: Graph Construction(10720) + Dream (11414)

This 2 problems are basically same. Here you are given degree sequence of graph and you have to find whether or not that sequence is graphic that is you can make a graph from that sequence.

There is a excellent algorithm for this problem named Havel-Hakimi algorithm.

The algorithm for the degree sequence S as follows-

1. If there exists an integer d in S such that d > n−1 then halt and report failure.
That is, we cannot have a vertex that is adjacent to more than n − 1 other vertices.

2. If there are an odd number of odd numbers in S halt and report failure.
That is, there must be an even number of vertices of odd degree.

3. If the sequence contains a negative number then halt and report failure.

4. If the sequence is all zeros then halt and report success.

5. Reorder S such that it is non-increasing.

6. Delete the first term d1 from S and subtract one from the next d1 terms to form a new sequence. Go to step 3

Consider the following input from sample input

6 2 4 5 5 2 1

and now follow the algorithm

a. The 1st condition (di > n−1 ) for i=0 to n-1 does not meet so continue.

b. The 2nd condition meet (there are an odd number of odd number),so the answer is not possible.

Another input-

6 1 3 4 2 5 2

a. The 1st condition (di > n−1 ) for i=0 to n-1 does not meet so continue.

b. The 2nd condition does not meet, so continue.

c. Now enter into a loop-

iteration: 1

c.1 3rd condition does not meet.

c.2 4th condition does not meet.

c.3 Sort the input.Looks like- 5 4 3 2 2 1

c.4 Now set x=value of first term,in this case it is 5. Now delete the first term.

so sequence is -> 4 3 2 2 1. Next subtract 1 from next x=5 item where x is the value of

deleted item.so the sequence is – 3 2 1 1 0.

iteration: 2

c.1 3rd condition does not meet.

c.2 4th condition does not meet.

c.3 Sort the input.Looks like- 3 2 1 1 0

c.4 Now set x=value of first term,in this case it is 3. Now delete the first term.

so sequence is -> 2 1 1 0. Next subtract 1 from next x=3 item where x is the value of

deleted item.so the sequence is 1 0 0 -1.

iteration: 3

c.1 3rd condition meet. So break and output not possible.