10943 - How do you add?

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

Moderator: Board moderators

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sun Oct 23, 2005 12:19 pm

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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sun Oct 23, 2005 12:28 pm

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.
Cho wrote: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!!! ..... :wink:


[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]
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Output

Post by rushel » Sun Oct 23, 2005 2:27 pm

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

Raj Ariyan
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

Post by Raj Ariyan » Tue Oct 25, 2005 11:23 am

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.
Some Love Stories Live Forever ....

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

Post by kp » Wed Oct 26, 2005 10:58 am

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
New poster
Posts: 28
Joined: Mon Nov 04, 2002 8:03 pm
Location: South Korea, Seoul
Contact:

It's easy DP.

Post by Gaolious » Thu Oct 27, 2005 5:52 pm

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
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Using Discrete Math

Post by rushel » Thu Oct 27, 2005 8:47 pm

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
New poster
Posts: 3
Joined: Sun Jun 26, 2005 6:57 pm

10943 - How do you add?

Post by Yumin » Sun Nov 13, 2005 8:06 pm

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sun Nov 13, 2005 8:41 pm

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
New poster
Posts: 3
Joined: Sun Jun 26, 2005 6:57 pm

Post by Yumin » Mon Nov 14, 2005 11:10 am

thank you,mf. :)

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Fri Nov 18, 2005 12:26 am

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

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Fri Nov 18, 2005 10:18 am

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
New poster
Posts: 11
Joined: Thu Dec 29, 2005 8:30 am
Contact:

10943 - How do you add?

Post by xlvector » Wed Jan 04, 2006 1:43 pm

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
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Re: 10943 WA

Post by mamun » Wed Jan 04, 2006 5:29 pm

xlvector wrote: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
New poster
Posts: 11
Joined: Thu Dec 29, 2005 8:30 am
Contact:

mod 1000000

Post by xlvector » Thu Jan 05, 2006 4:22 am

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

Post Reply

Return to “Volume 109 (10900-10999)”