911 - Multinomial Coefficients

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

Moderator: Board moderators

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

911 - Multinomial Coefficients

Post by helloneo »

Hello..~
I'm getting WA.. don't know why..
Can anybody tell me what's wrong..?
Thanks..

Code: Select all

code removed
Last edited by helloneo on Tue May 22, 2007 8:13 am, edited 2 times in total.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

I don't know. I also get WA although I think my code is correct.
For this input:

Code: Select all

10
3
4 4 2

10
4
4 3 2 1

5
5
1 1 1 1 1

100
1
101

100
1
100

100
5
90 4 3 2 1

1
1
0

1
1
1

7
7
0 0 0 0 0 0 7
I get this output:

Code: Select all

3150
12600
120
0
1
218109899151144000
0
1
1
Note that I print '0' if the exponents don't add up to n, which is correct, I think.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko »

Well, someone got it accepted, so we might be missing something. I use BigInt and also print 0 if exponents don't add up to n (and they don't in some cases - unless input per test case is in more than 3 lines, I haven't considered that).

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

I have got it accepted. There can be inputs for which z1+z2+..+zk > n, then I made n = z1+z2+...+zk, and returned the result. But I think that the output should be 0.

It is not right. I have informed the judges about this problem, but they havent replied.
Ami ekhono shopno dekhi...
HomePage

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko »

Oh, man, that's just wrong :(

Anyway - they should've tested judge's data in this volume or at least get someone to test it for them. It seems every other problem has something wrong with its I/O. And there are a few problems that shouldn't be solvable under the given constraints, but they are - those problem statements should be changed, too. (e.g n=1000000 and m <= n*(n+1)/2 ?!?)

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

I agree. The problems should be rechecked.
Ami ekhono shopno dekhi...
HomePage

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo »

Thanks everybody..
I got it.. :D

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

Post by sakhassan »

Can anyone Help me ? I dont know what's worng
with this input ?

100
5
90 4 3 2 1

Code: Select all

Removed after AC
Thanks In Advance
Last edited by sakhassan on Thu Nov 02, 2006 10:21 am, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

sakhassan wrote:I dont know what's worng
with this input ?

100
5
90 4 3 2 1
The output of your input exceeds 32 bit int. So, it is not a valid input. And you can use 'int' instead of 'double'(precision error!). Read my previous posts. I hope you will get some help. :wink:
Ami ekhono shopno dekhi...
HomePage

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

Post by sakhassan »

Thanks J@N....
Really there's no such input
100
5
90 4 3 2 1
I got ma problem
I wonder if z1+z2+..+zk>n how could the output is 1 !!!!!!!!!! :o

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

if z1 + z2 + z3 + ... + zk > n then the output should be zero. But I believe there are no such faulty inputs(They were removed).
Ami ekhono shopno dekhi...
HomePage

farzane
New poster
Posts: 26
Joined: Thu Jun 15, 2006 9:26 am

Post by farzane »

I need your help to find my mistake.I'm getting WA and realy don't know where is the bug.

Code: Select all

removed
Thanks in advance
Last edited by farzane on Fri Nov 10, 2006 4:17 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

Your algorithm is correct. But the problem is overflow. Check the I/O set.

Input:

Code: Select all

100
2
5 95
100
2
4 96
100
2
3 97
100
2
2 98
100
2
1 99
100
2
0 100
Output:

Code: Select all

75287520
3921225
161700
4950
100
1
Use Biginteger or use different approach. Hope these help.
Ami ekhono shopno dekhi...
HomePage

farzane
New poster
Posts: 26
Joined: Thu Jun 15, 2006 9:26 am

Post by farzane »

Thank you very much jan.I got the idea,add one more function to my code and got AC.I don't know why I forget to check this case.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

There's no need to use big integers to solve this problem. The key is to find a recurrence for the multinomial coefficient involving only sums and/or products. It is guaranteed to not overflow.

Post Reply

Return to “Volume 9 (900-999)”