CodeChef Hints

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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s