C - Help howcum, you must :
Problem Category: implementation, fibonacci numbers, pisano's period.
Well the problem is plain simulation. The steps are given in a very organized way. One has just to implement those.
At first one has to compute fibonacci numbers upto 10^6. Don't get anxious as you only will need the last 4 digits of those.So one can mod every time so that the numbers don't get out of range to fit in int data type.To do this you can mod every time with least number of 5 digit if you don't know about Pisano's period.
fibonacci numbers have a amazing property discovered by Pisano.
every last 1/2/3/4 digit(s) of fibonacci numbers repeats with a period of 60/300/1500/15000, respectively. (So you can easily understand you don't have to compute all 10^6 fibonacci numbers either :) ).
So upto this we covered the first two steps of the problem requirement.
For the 3rd and 4th steps you just have to count how many bits are on in the numbers got in the previous steps. ( you can just use __builtin_popcount() function for this steps. )
And now for the last step you have to count how many numbers in that range are there of which the sum of digits are divisible by P. Pretty easy you may think.. :P
you can prune out that in this last part- the range is never greater than 14. So the mod value given is just to scare you out. :P (you know RAM is a bit weird :) , but that's how howcum likes her ^_^ ).
Well you may need something extra. just be careful when k and p is zero.
E - Breaking Toys :
Problem Category: Number theory,catalan numbers,backtracking
Well this problem is very easy if you know the catalan numbers and its properties.
Dyck language is the language consisting of balanced strings of square brackets [ and ].
Cn is the number of Dyck words of length 2n. A Dyck word is a string consisting of n X's and n Y's such that no initial segment of the string has more Y's than X's. For example, the following are the Dyck words of length 6.
- XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.
In this problem you just need to calculate and pre-compute the first 14 catalan numbers.you can try this formula:
cat(m) = (2m*(2m-1))/((m+1)*m)* cat(m-1).
Then you can just give the result for every test case in O(1).
Alternative Solution:
As the input limit is small, so one can use backtrack to calculate the answer if he/she does not find the pattern or for any other reason.
J - RAM weds howcum :
This problem was set jointly by me and Shubhashis Roy Dipta.
Well to be honest we were trying to set a DP problem. In fact our solution of this problem was also DP until one of the contestants submit a solutions faster than us. Then we figure out it is a pure combinatorics problem :P and can be done with a linear loop. :P (A weird place, the world is :) )
The problem was to make a number of exactly length n without any consecutive same digit. ( this means no leading zeros are allowed).
So one can easily prune out that in the first position there can be at most 9 digits.( 0 is not allowed)
then in the second position there can also be 9 digits (0 to 9 except the digit placed in first position).
Thus in ith position there can also be 9 digits( 0 to 9 except the digits placed in position i-1)
So the solution is 9^n. you have to mod as per the mod value described in the problem.
DP Solution:
if you are really curious, this part is for you- Our DP solution consists of two state, in which position we are currently in and what was the last digit placed in the last position.
In the function we loop over 0 to 9 and check if this digit is not same with the last placed digit then do nothing, otherwise call the function for next position with this digit as the last placed digit.
The base case is if all the positions are placed with some digits then just return 1. :)
This can be what a raw code look like:
#define ll long long int
ll call(int pos,int last)
{
if(pos==n)
{
return 1;
}
ll res=0;
if(pos==0)
{
for(int i=1;i<=9;i++)
{
res+=call(pos+1,i);
}
}
else
{
for(int i=0;i<=9;i++)
{
if(last==i) continue;
res+=call(pos+1,i);
}
}
return res%mod;
}
And also Don't forget to memorize the results for this function. Because you know "Those who do not memorize the past are to repeat the same things again and again." :P :)
Hope this may be helpful. Anyone is warmly welcomed for any type of criticism. :)
