**Bytelandian gold coins :** Simple DP problem. We can use a function as get_coin ( long long coin ) which will return 0 if dp [ coin ] == 0 ; else

return dp [ coin ] = max ( coin, get_coin(coin/2)+get_coin(coin/3)+get_coin(coin/4) );

**Prime Generator : **Basic Segmented Sieve problem. If you do not know how segmented sieve works, try this link : Segmented Sieve.

**Closing the Tweets : **Simple adhoc problem

**Marbles : ** Already k marbles one from each type have been chosen, so there must be n-k marbles available. And we have to choose n-k marbles from n-1 marbles as one type is already chosen. The answer would be nCr ( n-1 , n-k ). As both n & k can be much bigger, we can’t use simple recursive nCr calculation for this purpose. Here is a sample nCr generator : nCr .

**The Next Palindrome : **Implementation problem. If all the digits are 9’s then the solution would be 1 ( k-times 0) 1, here k = length of the digit. We should take input as string and when there is not all 9’s for even and for odd length of string we should implement the code accordingly. As the output should be a palindrome, we can check only length/2 size to determine our answer, otherwise O(n) solution will get TLE.

# CodeChef Hints

Advertisements