forum 'Volume CVI' description wrote: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.
10634  Say NO to Memorization
Moderator: Board moderators

 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
Re: 10634 Say NO to Memorization  WA
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://onlinejudge.uva.es/board/viewto ... ight=10634 and http://onlinejudge.uva.es/board/viewto ... ight=10634)

 New poster
 Posts: 33
 Joined: Fri Jan 06, 2006 5:51 pm

 New poster
 Posts: 33
 Joined: Fri Jan 06, 2006 5:51 pm
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(k1) + (n1)C(k1)
Consider this function:
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 64bit integer, so do the terms nC(k1) and (n1)C(k1)
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)
nCk = nC(k1) + (n1)C(k1)
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);
}
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)