10634 - Say NO to Memorization

[koala]

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.

[Per]

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.

[Aleksandrs Saveljevs]

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.

[Per]

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

[windows2k]

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 26
11 33
35 34
300 143
1 1
0 1


[sohel]

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.

[Per]

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.

[sohel]

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]

[UFP2161]

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

[Per]

Whoops, you're right.

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

[Yaron Wittenstein]

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?

[Krzysztof Duleba]

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?

[Yaron Wittenstein]

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.

[Khaled_912]

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


[Martin Macko]

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