10943 - How do you add?

[Larry]

The problemset's difficulty might be a bit easy for veteran problemsolvers, but it was intended to be a local contest, so that's why.

Perhaps I should always write very precisely, but ya, I didn't write it with the intention of posting it on UVa, just so that it happened that way, and maybe next year/semester I'll keep the possibility in mind! I also didn't have anyone to look over the problems (my professor had looked at it and thought the difficulty was okay, but of course, thinking of problems in algorithms terms and thinking of solving problems precisely is always different!) so I didn't have much feedback. Next time I'll work on it.

Thanks!

[Observer]

Thanks to Larry. I appreciate your contribution of the new tasks, though some of them are flawed.

I do think that it is unfair to change the problem description just because the judge solution doesn't solve the task. I would really love to see the test data changed to fit the problem description. If you are too busy to do that, I can help.

I think this is unlikely to happen.

Of course I have no way to affect their decision, but if they insist in changing the problem description to fit the wrong judge solution, I would be very disappointed, since I think that is not what a responsible problemsetter should do.

Thanks again everyone!!


P.S. This question makes me think of our old friend 10323 Factorial! You Must be Kidding!!! .....


[FYI, 'add up to N' means 'amount to N', or 'equal N when they are added together'. Clearly, negative numbers are NOT prohibited by this definition]

[rushel]

1
3
6
1
4
10
20
1
5
15
35
70
420660
686660
319660
441660
5151
101

[Raj Ariyan]

Hi Sarah_S,
Your code produce trailing zero. Just ignore it. Like , for input

Code: Select all

6 46

Correct output should be

Code: Select all

9460

But ur code generates

Code: Select all

009460

Hope it helps. Thanks in advance.

[kp]

I thought of this problem as a completely mathimatical one

How many solutions does equation x1+...+xk = N have?

if xi > 0 then answer is C(N-1,K-1)

if xi > -1 then answer is C(N+K-1,K-1)

Here, C(N,K) is binomial coefficient.

[Gaolious]

D[ l, s ] = { l : Length of expression, s : sum of expression }

D[ l, s ] = SUM{ D[ l-1 , m ] } for m=0 to N and l <= K


and,

output is

Since Larry is only interested in the last few digits of the answer, for each pair of numbers N and K, print a single number mod 1,000,000 on a single line.

[rushel]

Of course this prob can be solved by DP and u can also solve this problem
using combination with repetition:

x1+x2+...+xk = n
how many solution does the above equation have answers the problem.
whie xi>=0 and xi <=n

Refrence : Discrete Mathmatics and Its Application by Rosen Page 336

[Yumin]

I try to solve this problem with Combinatorial Math, but get WA.
My method is below
1. input n and k // x1+x2+x3+...+xk = n
2. compute the value of C(n+k-1,n) //C is the binomial coefficient
3. output

when I input
100 1 //output 1
100 2 //output 101
100 3 //output 5151
100 4 //output 176851
100 5 //output 598126
the corresponding answer is alright.

But,
n=100 k=6 my program output 760646 => wrong answer
(ps. the corect answer should be 560646)


who can help me? here is my code..

Code: Select all

#include <cstdio>

int main(int argc, char *argv[])
{
	int n,k,m,result;
	while(scanf("%d %d",&n,&k)) {
		if(!n && !k)
			break;
		m = k+n-1;
		result = 1;
	
		if(n>(m>>1))
			n = m - n;

		for(int i=1;i<=n;i++,m--) {
			result*=m;
			result/=i;
			result%=1000000;
			
		}
		printf("%d\n",result);

	}


	return 0;
}

[mf]

for(int i=1;i<=n;i++,m--) {
result*=m;
result/=i;
result%=1000000;
}

When you're doing computations modulo some integer, you can't just divide like that (you can multiply, subtract, add, but not *divide*.)

Here's a numeric example, which shows it's wrong:
2000000 = 5000000 = 0 (mod 1000000).
But: 2000000/2 != 5000000/2 (mod 1000000).

(If the modulus were prime (which isn't the case in this problem), you could've implemented division as multiplication by the modular inverse of the divisor, though.)

[Yumin]

thank you,mf.

[technobug]

ac, but took 2 seconds... i used cin and cout.... does anyone know how to make it faster?

[mamun]

2 seconds! Dynamic approach should be faster. Once you calculate all the values you have to just retrieve it from the table. scanf() is faster than cin.

[xlvector]

I think , the solution is C(N+K-1,K-1), but my program get WA.

In my program, 100 100 return 0. I don't know is it wrong.

This is my code:

Code: Select all

#include <vector>
#include <iostream>
using namespace std;

int C(int n, int k)
{
	if(k==0) return 1;
	if(k==1) return n;
	int K;
	if(k>(int)(n/2)) K = n-k;
	else K = k;
	//cout<<"&&"<<n<<" "<<K<<endl;
	vector<int> d;
	vector<int> d1;
	int i,j;
	for(i=K;i>=2;i--){
		d.push_back(i);
		d1.push_back(i);
	}
	int ret = 1;
	int num;
	for(i=n;i>n-K;i--){
		num = i;
		d = d1;
		d1.clear();
		for(j=0;j<d.size();j++){
			if(num%d[j]==0){
				//cout<<num<<" "<<d[j]<<endl;
				num = (int)(num/d[j]);
			}else{
				d1.push_back(d[j]);
			}
		}
		ret = (ret*num)%1000000;
		//cout<<ret<<endl;
	}
	return ret;
}

int solve(int N, int K)
{
	if(K==1) return 1;
	return C(N+K-1,K-1);
}

int main()
{
	vector<int> ret;
	int N,K;
	while(true){
		cin>>N>>K;
		if(N==0 && K==0) break;
		ret.push_back(solve(N,K));
	}
	int i;
	for(i=0;i<ret.size();i++){
		cout<<ret[i]<<endl;
	}
}

[mamun]

In my program, 100 100 return 0. I don't know is it wrong.

It is. There are so many ways to make 100 by summing up 100 elements. The answer for this problem is

Code: Select all

420660

Check other threads about this problem. They should be very helpful.

[xlvector]

My true result is not zero, but after mod 1000000, it is zero.
can someone tell me what 's wrong with my algo