Coding Contest-13 Editorial

All contest related discussion goes here. Both Dev Skill and Non Dev Skill contest related discussion is allowed. (But please keep the forum clean)

Coding Contest-13 Editorial

by BishalG » 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.

Image

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.
User avatar
 
Posts: 43
Joined: Tue Jan 17, 2017 10:10 pm

Re: Coding Contest-13 Editorial

by habibrahman » Sun Feb 19, 2017 8:54 pm

In Problem D path sould be, 2n-1
 
Posts: 1
Joined: Sun Feb 19, 2017 4:31 pm

Re: Coding Contest-13 Editorial

by BishalG » Mon Feb 20, 2017 1:02 pm

habibrahman wrote:In Problem D path sould be, 2n-1

As starting cell is always (1,1) and target cell is always (n,n). Remaining path length will always be ((2*n)-2).
User avatar
 
Posts: 43
Joined: Tue Jan 17, 2017 10:10 pm


Who is online
Users browsing this forum: No registered users and 1 guest
cron