Coconuts, Revisited (616)

Problem statement

The maximum people number must be less than sqrt() of given coconut number n, so maximum people <= (int)sqrt(n);

---

int result = 0;

— For i = (int)sqrt(n) to 2

—– if (n % i == 1)   

———  result = calculatePeople(n, i, i);

——if (result != 0)

———– break;

if (result != 0)

—print(“Solution”);

else

—print (“No Solution”);

---

int calculatePeople(int m, int i, int k)

{    

     //Termination Condition

       if ( k == 1 &&  m%i  == 1)

             return i;

//Calculate updated m after a person taking his share + giving 1 to monkey.

      m = (m/i) * (i -1);

     int result;

      //Now Check if (m /%(i -1) == 1)?

            if  condition true

                 result = calculatePeople(m, i , k -1);

                 return result;      

          else

               return  0

}

---

By recursively calling this method you will get the correct result. if the function return any value except 0, that means it has a solution with number of people same as return value.

Lets go with first example in sample dataset.

n= 25.

i = 5 to 2;

i = 5 ,

       –> n = 25

       –>  doesn’t meet n%i == 1.

i = 4,

      –> n = 25

      –> meet (n%i) == 1.

      –> Call calculatePeople()

      –> m = 18

      –>  doesn’t meet m%i == 1.

      –> return 0, means no solution exist with i =4

i = 3

      –> n = 25

      –> meet (n%i) == 1.

      –> Call calculatePeople()

      –> m = 25  k = 3

      –> meet (m%i) == 1.

      –> m = 16   k = 2

      –> meet (m%i) == 1.

      –> Call calculatePeople()

      –> m = 10  k = 1

      –> k = 1  && (m%i) == 1.

           –>return i = 3

UVA Problem (12335) : Lexicographic Order

Problem statement:

This problem is a adhoc problem. In this problem you need generate the lexicographic smallest
permutation given a permutation and it’s lexicographic order.

So before proceed recall,if a<b<c<d and string is- abcd, there are 24 permutation,where

1-6 permutation start with smallest, here a.
7-12 permutation start with second smallest, here b.
13-18 permutation start with third smallest, here c.
19-24 permutation start with fourth smallest, here d.

lets Define, x= current_lexographic_order;
= 11

So consider the input –

bdac 11

So start with first character b,

x= x % factorial(current examining string length)
= 11%factorial(4)
= 11%24
=11;

So from it is clear that if (b)dac in lexographically 11'th smallest permutation,
then b is second smallest element,

bcoz it fall's in range between 7-12,

So A[1]=b,

So,

_______***_______________
| () | b | () | () |
|_____|_____|_____|______|
A[0] A[1] A[2] A[3]

Next remain, (d)ac, there are 6 permutation

1-2 permutation start with smallest.
3-4 permutation start with second smallest.
5-6 permutation start with third smallest.

(d)ac is 5’th smallest permutation, How we do we know this??? Since bdac in lexographically
11’th smallest permutation ,string starting with b starts from 7, so 7,8,9,10,(11), 5’th smallest permutation.

By calculation-

x=x % factorial(current examining string length)
= 11%factorial(3)
= 11%6
=5;

SO d goes to last position among d,a,c (empty position in array) .

___________________***__
| () | b | () | d |
|_____|_____|_____|______|
A[0] A[1] A[2] A[3]

Next remain, (a)c, there are 2 permutation

1 permutation start with smallest.
2 permutation start with second smallest.

(a)c which is 1’th smallest permutation. So a goes before c.How? same thing.

x=x % factorial(current examining string length)
= 5%factorial(2)
= 5%2
=1;

So now-

_________________________
| a | b | () | d |
|_____|_____|_____|______|
A[0] A[1] A[2] A[3]

And then lasr the remaining element (c), place it in the empty position, here it is A[2].

So overall array looks like-

___________***______
a b c d
____________________
A[0] A[1] A[2] A[3]

Hope it’s understandable.
Please leave a comment so that i can add more solution, because inspiration lies behind everything.

For any query email me salimsazzad222@gmail.com.

UVA Problem: Game of Sum(10891)

Problem Statement:

Problem Explanation:

This Problem is classic example of dynamic programing.

Lets , Sum{i,j}= sum of element from i to j;
Best{i,j}= max point can be achieved from i to j element.

suppose n=4, A can take following 7 way-

1. Sum{1} – Best{2-4}
2. Sum{1-2} – Best {3-4}
3. Sum{1-3} – Best {4}
4. Sum{1-4} – Best {}
5. Sum{4-4} – Best {1-3}
6. Sum{3,4} – Best {1-2}
7. Sum{2-4} – Best{1-1}

A will choose from above 7 option in which he can get maximum score that
is Best[1-4].if A take {1} then B will get element{2-4}. Then B will play perfectly
to achieve more point from elemenmt {2-4}, which is Best{2-4}. B can achieve
Best{2,4} by maximum of following way-

1. Sum{2} – Best{3-4}
2. Sum{2-3} – best{4}
3. Sum{2-4} – Best{}
4. Sum{4-4} – Best{2-3}

B will take the option where he can get maximum score. If B take {2} , then
A will get element{3-4}, So A will try to get maximum score from element {3,4},
which is Best{3,4} and can be achieved either following way-

1. Sum{3-3} – Best{4-4}
2. Sum{3-4} – Best{}
3. Sum{4-4} – Best{3-3}.

Above we solved all the subproblems to calcualte option 1 of Problem Best[1-4],
Sum{1} – Best{2-4}. Similary we have to calculate other 6 option. And the option
with higest value is the our answer.

UVA Problem: Subsequence(1121)

Problem Statement:

Problem Explanation:

This problem is very interesting. The main concern goes to develop a O(n) algorithm , else there is no way to avoid TLE.

I am explaning this problem with sample I/O. consider
10 15
5 1 3 5 10 7 4 9 2 8.
we need to sum up >=15 using fewest number of consecutive element.

we need two iterator first and last.
s=15;
sum=0;
first=0;
last=0;
while(1)
{
while(sum<s)
{
add A[last] to sum and increament last;
}

we get >=s using 5 element {5,1,3,5,10}.
Now,
while (sum>=s)
   {
subtract A[first] to sum and increament first;
}

diff=(last-1)- (first-1) + 1;
if(diff< minSeq)
{
minSeq=diff;
}
}

UVA Problem: Longest Run on a Snowboard (10285)

 

Problem Statement

 
In this problem we need to find the longest path in a directed acyclic graph (dag).

The algorithm and explanation is given bellow-

# Consider each grid point/height  as a node of a  directed graph.

# Initially length of each node is lengthOf (r,c)= 1.    0<=r<R  , 0<=c<C.

# Consider a directed edge from node X to four neighboring node (top, down, bottom, left) if there value is less than X value.

Example-

10   2    4

3  14  22

8  13  20

Here  directed edge from node 10 is 10->2 and 10->3.  Directed edge from node 2 is none, since neighbor node 10,4,14 all of are greater than 2 and so on.

Now loop  –

For(i=0; i<row; i++)
{
For(j=0; j<column; j++)
{
longestRun(node at i’th row & j’th column);
}
}

 

 

longestRun function return the longest run from node position at (r,c).

int longestRun(int r,int c)
{

if any neighbor (i,j)  of (r,c)  has value  less than (r,c) value then && lengthOf(r,c) not previously calculated then

{

x= longestRun(i,j);

if(lengthOf(r,c)<x)

{

lengthOf(r,c)=x;

}

}

return lengthOf(r,c) + 1;

}

Here is the explanation;

# Start from node 10. 2 directed edge from node 10.

a.     10->2,  2->empty .  No edge from node 2. Highest length of 2 is 1.

b.     10->3, 3->empty. No edge from node 3. Highest length of 3 is 1.

So we get highest length of 10 is 2.

#  Start from node 2.

We calculate highest length of node 2 previously, so no need to calculate again.

# Start from node 4.

1 directed edge 4->2

1. highest length of 2 is 1, so highest length of 4 is 2.

Continue this for each node and take the maximum.

In this example we get the longest run for node 22.

3 Directed edge for node 22.

1. 22->4 , we have calculated longest run for 4 before which is 2, so here longest run for 22 is  3.
2. 22->14, we have calculated longest run for 14 before which is 4, so here longest run for 22 is 5.
3. 22->20, which is not calculated before , so calculate longest run for 20. We find longest run for 20 is 4, 20->13->8->3. So longest run for 22 is 5.

UVA Problem: 12101 (Prime Path )

Problem Statement:

Problem Explanation:

This is a simple BFS problem . There is nothing special to mention for this problem.

1.  First generate prime number upto  9999.

2.  Then just run BFS from the initial number. Like if the number is 1033 where else we can go

2.a  Changing the first digit we get 8 number (2-9)033, changing second digit we get 9 number 1(1-9)33 and so  on.  If   any of the number is prime then place it in queue and mark this as visited so that you don’t push it again.

3.  Push and Pop the numbers until you get the desired number. If number not found print “Impossible.” else print the distance.

UVA Problem: 12032 (The Monkey and the Oiled Bamboo)

Problem Statement:

Problem Explanation:

This problem may seems complicated at the the first glance, But if closely observed then it becomes apparent that there is only a few candidate for minimum value of k. First find what can be the maximum of (minimum value of k). If the maximum difference between any two rung of ladder is n, then maximum of (minimum value of k) is n+1, since in this case no decrement is performed for k, and certainly all rung can be reached, since n is the highest difference. Next comes the question can we minimize k from (n+1). Since maximum difference between any two rung is n, so k must at least n. So now check whether it is possible to reach all rung using value n, if possible then print n, else print n+1. Simple is in’t?

UVA Problem: 136(Steps)

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. 

UVA Problem: 12293 ( Box Game)

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)

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.