10910 - Marks Distribution

ImLazy · Post by **ImLazy** » Fri Oct 07, 2005 8:51 am

I generate all the decreasing sequences and multiply each of them with its number of permutations. But TLE.
Is there any faster algorithm?

wook · Post by **wook** » Fri Oct 07, 2005 12:58 pm

the algorithm you described as above will too slow for this problem;

A Simple DP will do enough.

Some key hint:

for example,
when N=3, T=34, P=9,

11 + 11 + 12 = 34
min(11, 11, 12) = 11 >= 9 = P

Do you see some relations between above and below?

2 + 2 + 3 = 7
min(2, 2, 3) = 2 >= 0

ImLazy · Post by **ImLazy** » Fri Oct 07, 2005 2:04 pm

The above is 9 greater than the below. But I don't understand how to use this to solve the problem.

wook · Post by **wook** » Fri Oct 07, 2005 3:02 pm

min(a, b, c, ..., z) >= P

is same as :

a >= P, b >= P, c >= P, ...

So,

given statement, min(a1, a2, ..., aN) >= P means

a1 >= P, a2 >= P, a3 >= P, ..., aN >= P,
where a1 + a2 + a3 + ... + aN = T

Think a sequence {bn} = an - P
Then, the equation above is translated into these forms:

b1 >= 0, b2 >= 0, ..., bN >= 0
b1 + b2 + b3 + ... + bN = T - N * P

this form, which is easier than first, is a commonplace problem;
and it can be solved with simple DP.

ImLazy · Post by **ImLazy** » Fri Oct 07, 2005 5:18 pm

:O, thanks. I'll try it.

ImLazy · Post by **ImLazy** » Sun Oct 09, 2005 12:26 pm

No TLE now, but WA. Here is my output for small cases, are they right?
Input:

Code: Select all

Output:

Code: Select all

misof · Post by **misof** » Sun Oct 09, 2005 12:55 pm

ImLazy: Some of your outputs are wrong. Here is my output:

Code: Select all

ImLazy · Post by **ImLazy** » Sun Oct 09, 2005 2:56 pm

I've found my bug and get AC. Thanks.

The bug is in the function of calculating the number of permutation & combination. In the above wrong output, my program calculates 14C6 as 12012, but it should be 3003.

ranban282 · Post by **ranban282** » Thu Mar 01, 2007 2:41 pm

I have absolutely no idea why this gives WA. It passes the test cases given above. Can anybody give me test cases with solutions?

Code: Select all

Removed after AC

ranban282 · Post by **ranban282** » Thu Mar 01, 2007 2:47 pm

When I used int, it gave WA. When I used long long, I got AC

rohituberoi · Post by **rohituberoi** » Sun Jun 10, 2007 3:39 pm

Plzz help.......i don't know why i m getting runtime error in this code......It is working perfectly on my compliler......

#include<iostream>
using namespace std;
int main(){
long long int u,v,y;
long long int l,i,n,t,p,j,s,k;
cin>>l;
for(i=0;i<l;i++){
n=t=p=j=0;
cin>>n>>t>>p;
j=t-(n*p);
s=j+n-1;
if(n>1){
v=1;
for(k=1;k<=(n-1);k++){
v=v*s;
s--;
}
u=1;
for(k=1;k<=(n-1);k++){
u=u*k;
}
y=v/u;
cout<<y<<endl;
}
else if(n==1){
cout<<"1"<<endl;
}
}
return 0;
}

jan_holmes · Post by **jan_holmes** » Sun Jun 10, 2007 8:56 pm

I don't know whether this is the problem but you might use "long long" instead of "long long int".

mf · Post by mf » Sun Jun 10, 2007 9:06 pm

'long long' and 'long long int' are the same thing.

Runtime error is in "y=v/u;"
He tries to put (N-1)! into u, and that overflows, and results in u=0.

jan_holmes · Post by **jan_holmes** » Sun Jun 10, 2007 9:14 pm

ic...

Thx for the correction

lucky16g · Post by **lucky16g** » Tue Jul 10, 2007 9:44 pm

why my code got wrong anser

can anyone tell me what input will let it wrong

is it over flower for long long int ?

thx before

Code: Select all

i have got ac

thanks for mf's help

OJ Board

10910 - Marks Distribution

10910 - Marks Distribution

Why WA??

Problem description

Runtime Error