911 - Multinomial Coefficients

Moderator: Board moderators

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

911 - Multinomial Coefficients

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
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
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
Contact:
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.

Ami ekhono shopno dekhi...
HomePage

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
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
Contact:
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
Thanks everybody..
I got it..

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU
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
``````
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
Contact:
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.
Ami ekhono shopno dekhi...
HomePage

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU
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 !!!!!!!!!!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
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
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
``````
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
Contact:
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
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