### Coding Contest-13 Editorial

Posted:

**Sun Feb 19, 2017 2:41 pm**Problem A: Cube Game

Link: http://devskill.com/CodingProblems/ViewProblem/254

Problem Setter: Jayed Al Hasan

For this problem, you have to calculate score using formula: B*1+S*3+G*10+R*(-5).

The critical thing is that maximum score will come directly comparing all scores whereas individual score should be printed non-negative. if score become negative, you should print 0.

Problem B: Write an algorithm

Link: http://devskill.com/CodingProblems/ViewProblem/219

Problem Setter: Mir Lutfur Rahman

It's a string problem depend on some basic operation +,-,*,/. You just need to detect the operation from string and add into STL Map for repetition check.

And two tricky condition is x+y=y+x and x*y=y*x these two types operation will be treat as same but on the other hand x/y!=y/x and x-y!=y-x these two types operation will not be treat as same.

Problem C: Journey By Circle

Link: http://devskill.com/CodingProblems/ViewProblem/251

Problem Setter: MD Musfiqur Rahman Sanim

As velocity of both satellite is PI meter per second. The Time taken by both to come to their beginning position for one move will be :

time=distance/velocity, where distance= 2*PI*R to move around a circle.

So, time for Satellite_A= 2*r1

time for Satellite_B= 2*r2

Now, we have to determine which is the lowest value which is divisible by both 2*r1 and 2*r2.

This can easily be calculate by finding LCM of 2*r1 and 2*r2.

Problem D: Escape from Grid-land

Link: http://devskill.com/CodingProblems/ViewProblem/245

Problem Setter: Bishal Gautam

You are given n*n grid. Each cell of the grid has gold value in it. You have to calculate maximum multiplication of value you can take which is less than K while reaching cell (n,n) from cell (1,1) and print total count of such values.

Idea:

One may easily come up with idea of recursion or dynamic programming in 2D grid. As products of values may be very large, we can not solve this problem using dp within time limit. So, we have to think in different optimized way.

Lets think that what is total length of any path reaching to (n,n) from (1,1).

This is always: (2*n-2).

If we observe more deeply, we may see that all paths of half length ( n-1 ) always ended into anti-diagonal.

So, we generate and store values of multiplications of all paths of length (n-1) from begin cell (1,1) to every anti-diagonal cells.

We need total n vectors to store values in every cell of anti-diagonal.

Now ,we can generate same length path from end cell (n,n) and check for all valid multiplications values in particular vector using binary search.

A sample for path storing mechanishm is shown in picture below. Where, Blue cell represent starting cell, Green cell represents target cell and Yellow cells represents anti-diagonal cells.

This approach is called meet in the middle approach.Here,we consider the anti-diagonal grid cell as middle.

Critical thing is that, you have to handle overflow while multiplication.

For this, lets consider current product of values as : cur_prod.

Then, we will take gold ( g ) if and only if g is less than or equal to ratio of K with cur_prod.

i.e g<=(K/cur_prod) .

Time complexity: O( TC* 2^n * 15 ),

where 2^n for generation of values and 15 is for Binary search.

Problem E: Parand()thesis

Link: http://devskill.com/CodingProblems/ViewProblem/255

Problem Setter: Md. Nahidul Islam

Here, number of parenthesis pairs = N. Probability of getting valid expression P =?

P can be written as A / B, where A = number of valid expressions and B = number of all possible expressions.

A = (2n)!/(n+1)!(n)! = Nth Catalan number.

And B = 2^2n.

So, A / B = (2n)!/((n+1)!(n)!2^2n )

Now, we have to make A / B irreducible (making A, B coprime). This can be done easily by prime factorization. After prime factorization part reduce the common primes from A and B. This technique does the same effect as dividing both by their gcd, so that gcd(A, B) becomes 1 (coprime).

Finally, do modulo operation to both A and B using their remaining primes.

Total complexity O(2N*P) with some minor optimizations, P = number of primes up to 2N.

Link: http://devskill.com/CodingProblems/ViewProblem/254

Problem Setter: Jayed Al Hasan

For this problem, you have to calculate score using formula: B*1+S*3+G*10+R*(-5).

The critical thing is that maximum score will come directly comparing all scores whereas individual score should be printed non-negative. if score become negative, you should print 0.

Problem B: Write an algorithm

Link: http://devskill.com/CodingProblems/ViewProblem/219

Problem Setter: Mir Lutfur Rahman

It's a string problem depend on some basic operation +,-,*,/. You just need to detect the operation from string and add into STL Map for repetition check.

And two tricky condition is x+y=y+x and x*y=y*x these two types operation will be treat as same but on the other hand x/y!=y/x and x-y!=y-x these two types operation will not be treat as same.

Problem C: Journey By Circle

Link: http://devskill.com/CodingProblems/ViewProblem/251

Problem Setter: MD Musfiqur Rahman Sanim

As velocity of both satellite is PI meter per second. The Time taken by both to come to their beginning position for one move will be :

time=distance/velocity, where distance= 2*PI*R to move around a circle.

So, time for Satellite_A= 2*r1

time for Satellite_B= 2*r2

Now, we have to determine which is the lowest value which is divisible by both 2*r1 and 2*r2.

This can easily be calculate by finding LCM of 2*r1 and 2*r2.

Problem D: Escape from Grid-land

Link: http://devskill.com/CodingProblems/ViewProblem/245

Problem Setter: Bishal Gautam

You are given n*n grid. Each cell of the grid has gold value in it. You have to calculate maximum multiplication of value you can take which is less than K while reaching cell (n,n) from cell (1,1) and print total count of such values.

Idea:

One may easily come up with idea of recursion or dynamic programming in 2D grid. As products of values may be very large, we can not solve this problem using dp within time limit. So, we have to think in different optimized way.

Lets think that what is total length of any path reaching to (n,n) from (1,1).

This is always: (2*n-2).

If we observe more deeply, we may see that all paths of half length ( n-1 ) always ended into anti-diagonal.

So, we generate and store values of multiplications of all paths of length (n-1) from begin cell (1,1) to every anti-diagonal cells.

We need total n vectors to store values in every cell of anti-diagonal.

Now ,we can generate same length path from end cell (n,n) and check for all valid multiplications values in particular vector using binary search.

A sample for path storing mechanishm is shown in picture below. Where, Blue cell represent starting cell, Green cell represents target cell and Yellow cells represents anti-diagonal cells.

This approach is called meet in the middle approach.Here,we consider the anti-diagonal grid cell as middle.

Critical thing is that, you have to handle overflow while multiplication.

For this, lets consider current product of values as : cur_prod.

Then, we will take gold ( g ) if and only if g is less than or equal to ratio of K with cur_prod.

i.e g<=(K/cur_prod) .

Time complexity: O( TC* 2^n * 15 ),

where 2^n for generation of values and 15 is for Binary search.

Problem E: Parand()thesis

Link: http://devskill.com/CodingProblems/ViewProblem/255

Problem Setter: Md. Nahidul Islam

Here, number of parenthesis pairs = N. Probability of getting valid expression P =?

P can be written as A / B, where A = number of valid expressions and B = number of all possible expressions.

A = (2n)!/(n+1)!(n)! = Nth Catalan number.

And B = 2^2n.

So, A / B = (2n)!/((n+1)!(n)!2^2n )

Now, we have to make A / B irreducible (making A, B coprime). This can be done easily by prime factorization. After prime factorization part reduce the common primes from A and B. This technique does the same effect as dividing both by their gcd, so that gcd(A, B) becomes 1 (coprime).

Finally, do modulo operation to both A and B using their remaining primes.

Total complexity O(2N*P) with some minor optimizations, P = number of primes up to 2N.