## UVA Problem: 136(Steps)

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

## UVA Problem: 12293 ( Box Game)

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)

**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)

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