10634 - Say NO to Memorization

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

Moderator: Board moderators

Martin Macko
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

Post by 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/viewto ... ight=10634 and http://online-judge.uva.es/board/viewto ... ight=10634)
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.

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

Post by 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
New poster
Posts: 33
Joined: Fri Jan 06, 2006 5:51 pm

Post by 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
New poster
Posts: 8
Joined: Tue Dec 26, 2006 10:37 am

Post by 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.

Post Reply

Return to “Volume 106 (10600-10699)”