10634 - Say NO to Memorization

[Martin Macko]

And btw, there is already a thread on this problem. If there is a thread on a particular problem, please, use it to post your question and do not create a new one. (see http://online-judge.uva.es/board/viewtopic.php?t=5477&highlight=10634 and http://online-judge.uva.es/board/viewtopic.php?t=7631&highlight=10634)

All about problems in Volume CVI. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

[Khaled_912]

Thanks a lot, I noticed the silly mistake concerning the size of my array, got AC now.
I'll remember next time to post my Q in an existing thread.

[Khaled_912]

The fastest and safest method to evaluate nCk is using the fact from the pascal's traingle that this recurrence relation holds true:
nCk = nC(k-1) + (n-1)C(k-1)
Consider this function:

Code: Select all

long long mem[2005][2005]; //initialized to -1

long long c(int n, int k)
{
   if (n == k) return 1;
   if (k == 0) return 1;
   if (mem[n][k] != -1) return mem[n][k];
   return mem[n][k] = c(n - 1, k) + c(n - 1, k - 1);
}


After building some parts in the memoization array, you can find the answer of nCk in O(1). In addition, you don't have to worry about overflow, as the term nCk is represented as the sum of two smaller terms, so if nCk fits in a 64-bit integer, so do the terms nC(k-1) and (n-1)C(k-1)
Using this function to evaluate nCk I got AC in 0.35 seconds.
You can build another funtion that uses the same concept of memoization to evaluate the desired interval of summation. It should only be worth coding if the input file contained a huge amount of test cases, which seems to be the case.
I managed to get accepted in 0.14secs using the method.
With few other optimizations, I managed to get AC is 0.74 secs (I'm #11 on the list)

[klopyrev]

nCk is not needed here. The answer is F(n, v) = F(n-1, v) + F(n, v-1). If n==0, the answer is 1. If v==0, the answer is 1 if n is even and 0 if n is odd.