Skip to content

Coconuts, Revisited (616)

September 14, 2014

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

December 19, 2011

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)

October 9, 2011

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)

October 8, 2011

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)

October 8, 2011

 

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 )

October 5, 2011

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)

October 5, 2011

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?