OJ Board

Posted: **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!

Posted: **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!!! .....

[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]

Posted: **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

Posted: **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

But ur code generates

Code: Select all

Hope it helps. Thanks in advance.

Posted: **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.

Posted: **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.

Posted: **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

Posted: **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;
}

Posted: **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.)

Posted: **Mon Nov 14, 2005 11:10 am**

thank you,mf.

Posted: **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?

Posted: **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.

Posted: **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;
	}
}

Posted: **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

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

Posted: **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

OJ Board

10943 - How do you add?

Output

It's easy DP.

Using Discrete Math

10943 - How do you add?

10943 - How do you add?

Re: 10943 WA

mod 1000000