10634 - Say NO to Memorization

Moderator: Board moderators

10634 - Say NO to Memorization

The answer is just the value of C(n+v-1,v-1)+C(n+v-3,v-1)+C(n+v-5,v-1)+...+C(v or v-1,v-1).
I caculated it directly and my program got ACed in 1.9x(sec). rather slow
But many people's programs used much less time. I wonder how they made it.
Last edited by koala on Sun Apr 18, 2004 11:10 am, edited 2 times in total.
koala
New poster

Posts: 7
Joined: Sun Mar 28, 2004 9:41 am
Location: Tsinghua University, Peking, P.R.China

I used the same formula, but when computing it, i used the fact that
Code: Select all
`C(n,k) = C(n-1,k) * n / (n-k)`

And of course -- only compute each value once, save them in a table.
Per
A great helper

Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

By the way, make sure you don't use the advantage of the fact that
Code: Select all
`c(n, k) = c(n, k-1) * (n-k+1) / k`

There will be trouble with the overflow.
Aleksandrs Saveljevs
New poster

Posts: 39
Joined: Fri Nov 14, 2003 11:18 pm
Location: Riga, Latvia

There will be overflow if you just use the formula i wrote as well, you just have to be careful enough to avoid it.
Per
A great helper

Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Per wrote:There will be overflow if you just use the formula i wrote as well, you just have to be careful enough to avoid it.

Hello, Per
I tried to solve the problem.
It looks like an easy combinatrial problem.
But I get WA all the time.
Could you tell me the output? Thx
Code: Select all
`44 2611 3335 34300 1431 10 1`
windows2k
Experienced poster

Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

So from what it looks,
the number of ways to fill v spaces such that the sum of the numbers is n
is equal to C(n+v-1, v-1).

Example : n = 4 and v=2, then the lists are
0 4
1 3
2 2
3 1
4 0

and C(4+2-1, 2-1) = C(5,1) = 5;

Therefore it works......... but can someone tell me how the formula is derived || why does it work.
Thanks.

sohel
Guru

Posts: 865
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

windows2k:
The output is:
Code: Select all
`68522017223906135286118171326<illegal test case><illegal test case>11`
Cases 3 and 4 are illegal since the answers won't fit in 63 bits.

You could also try:
Code: Select all
`15 111958 8`

Output:
Code: Select all
`91889078307370932339171632935212769528`

sohel: one way of describing the binomial coefficient C(n+v-1, v-1) is as the number of ways to choose v elements from a set of n elements, with repetition. In other words the number of monomials of degree v in n variables.
Last edited by Per on Mon May 31, 2004 9:05 am, edited 1 time in total.
Per
A great helper

Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Thanks Per, got it now.

I opend my discreet maths book and found/learnded the proof of the given formula... its very interesting, I must add.

[/c]

sohel
Guru

Posts: 865
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

The input "15 120" will overflow.

The actual answer (calculated using Java BigInteger) is:
27664065003647705984

If you subtract 2^64 from it, you get Per's answer of:
9217320929938154368

UFP2161
A great helper

Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm

Whoops, you're right.

Sorry about that, I've removed the faulty test case from my post.
Per
A great helper

Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

10634

Here is my code:
Code: Select all
`#include <stdio.h>#define MAXN 1000int main(){  unsigned long f[MAXN + 1]; /* f[n] = f(n, v) */  int n, v;  int i, start;  while (1) {    scanf("%d %d", &n, &v);    if ((n == 0) && (v == 0))      break;    f[0] = 1;    f[1] = (unsigned long)v;    start = (n % 2 == 0 ? 0 : 1);    for(i = start; i <= n - 2; i+=2)      f[i + 2] = f[i] *  ((i + v)*(i + v + 1)) / ((i + 1)*(i + 2));    for(i = start; i < n; i+=2)      f[n] += f[i];    printf("%ld\n", f[n]);  }  return 0;}`

What's worng? i have no idea, maybe it has something to do
with the fact that the answer will fit a 64-bit signed integer?
Yaron Wittenstein
New poster

Posts: 18
Joined: Wed Jul 21, 2004 5:09 pm

Yaron Wittenstein wrote:What's worng? i have no idea, maybe it has something to do with the fact that the answer will fit a 64-bit signed integer?

That's right. Why do you use 32-bit longs if you know that's not enough?

Krzysztof Duleba
Guru

Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland

I still get WA

i tried unsigned long long and still got WA
i don't have a clue why i get WA!
it seems to work fine on my computer.
please try to help me here.
Yaron Wittenstein
New poster

Posts: 18
Joined: Wed Jul 21, 2004 5:09 pm

10634 Say NO to Memorization - WA

I'm keeping to get WA on this problem, although I've tried all of the test cases in the other posts.
If anybody can tell me where's the mistake or post some extra i/o I'll be thankful.
Code: Select all
`Removied after AC`
Last edited by Khaled_912 on Thu Aug 17, 2006 2:57 pm, edited 1 time in total.
Khaled_912
New poster

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

Re: 10634 Say NO to Memorization - WA

Khaled_912 wrote:I'm keeping to get WA on this problem, although I've tried all of the test cases in the other posts.
If anybody can tell me where's the mistake or post some extra i/o I'll be thankful.

Your solution gets Segmentation fault on:
Code: Select all
`6 10000 0`

My AC's output:
Code: Select all
`1409882508284251`

Martin Macko
A great helper

Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Next