OJ Board

Posted: **Fri Apr 16, 2004 8:37 am**

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.

Posted: **Fri Apr 16, 2004 8:49 am**

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.

Posted: **Sun Apr 18, 2004 8:48 pm**

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.

Posted: **Mon Apr 19, 2004 7:58 am**

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

Posted: **Mon Apr 19, 2004 8:21 am**

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

Posted: **Mon Apr 19, 2004 11:35 am**

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.

Posted: **Mon Apr 19, 2004 11:44 am**

windows2k:
The output is:

Code: Select all

6852201722390613528
6118171326
<illegal test case>
<illegal test case>
1
1

Cases 3 and 4 are illegal since the answers won't fit in 63 bits.

You could also try:

Code: Select all

15 111
958 8

Output:

Code: Select all

9188907830737093233
9171632935212769528

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.

Posted: **Wed May 05, 2004 12:45 pm**

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]

Posted: **Fri May 28, 2004 5:15 pm**

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

Posted: **Mon May 31, 2004 9:06 am**

Whoops, you're right.

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

Posted: **Sun Feb 27, 2005 10:59 pm**

Here is my code:

Code: Select all


#include <stdio.h>

#define MAXN 1000


int 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?

Posted: **Mon Feb 28, 2005 1:40 am**

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?

Posted: **Tue Mar 01, 2005 4:27 pm**

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.

Posted: **Wed Aug 16, 2006 6:43 pm**

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

Posted: **Wed Aug 16, 2006 10:59 pm**

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 1000
0 0

My AC's output:

Code: Select all

1409882508284251

OJ Board

10634 - Say NO to Memorization

10634 - Say NO to Memorization

10634

I still get WA

10634 Say NO to Memorization - WA

Re: 10634 Say NO to Memorization - WA