Page 1 of 3

10994 - Simple Addition

Posted: Sun Feb 12, 2006 12:58 am
by bakey2
Can anyone tell me how to solve the problem 10994 which is the E problem last contest?Thx

Posted: Sun Feb 12, 2006 1:37 am
by misof
(sum from a to b) = (sum from 1 to b) - (sum from 1 to a-1)

To compute the sum from 1 to N, split the numbers 1..N into two groups: those that end with zero, and those that don't. You can compute the sum for the second group directly. Then, find the sum for the first group recursively.

Posted: Sun Feb 12, 2006 4:11 am
by bakey2
Do you think it is efficient to solve this problem?when i compute sum(p~q) directly i got a TLE.And when i use an array flag[p] to save the sum(1~p) I got a MLE.~~~~~I have no idea,so faint~~~~

Posted: Sun Feb 12, 2006 4:23 am
by wook
bakey2 wrote:Do you think it is efficient to solve this problem?when i compute sum(p~q) directly i got a TLE.And when i use an array flag[p] to save the sum(1~p) I got a MLE.~~~~~I have no idea,so faint~~~~
sure it is.
Computing sum(p~q) directly MUST make TLE.
and also you CANNOT use an array like a[2147483647];

the misof's explanation is exactly the method to solve it.

using this method,
we are able to compute S(k) = f(1)+f(2)+...+f(k) with just few operations.
The depth of recursion is no more than 10, since the length of a string "2147483647" is 10.

Posted: Sun Feb 12, 2006 4:24 am
by misof
bakey2 wrote:Do you think it is efficient to solve this problem?when i compute sum(p~q) directly i got a TLE.And when i use an array flag[p] to save the sum(1~p) I got a MLE.~~~~~I have no idea,so faint~~~~
By "directly" I meant "find a formula that can compute this in constant time".

For example, let's compute the sum for 1 to 37.

The first group: 10, 20, 30. The sum for this group is the same as the sum for 1, 2, 3.

The second group:
1,2,3,4,5,6,7,8,9,
11,12,13,14,15,16,17,18,19,
21,22,23,24,25,26,27,28,29,
31,32,33,34,35,36,37

In general, if we write the second group like this, how many rows will we get? What is the sum of our function for each row?

Posted: Sun Feb 12, 2006 5:09 am
by bakey2
Thx wook & misof ~~~
I will have a try~

Posted: Sun Feb 12, 2006 6:40 am
by imnew
---thanks.....got it.....
what is the result for
p = 1, q = 2147483647
p = 100000, q = 200000
Thanks in advance.....

Posted: Sun Feb 12, 2006 6:46 am
by wook
imnew wrote:what is the result for
p = 1, q = 2147483647
p = 100000, q = 200000
Thanks in advance.....
10737418158 and 499998, respectively.

10994 Compile Error

Posted: Mon Feb 13, 2006 12:59 am
by el cheeto
I have a problem with problem 10994, I only get CE and my solution seems to be okay. I'll thank any help

//erased after ACC

Posted: Mon Feb 13, 2006 5:43 am
by chunyi81
1) main should return int
2) Don't use C++ style comments (//) in your C code. This will give compile error in this judge. This thread should be under forum volume CIX, by the way.

Posted: Mon Feb 13, 2006 7:04 am
by el cheeto
Thank you chunyi81, I submited my code in C instead of C++ and get Accepted, but the true is that i don

Posted: Mon Feb 13, 2006 10:52 am
by sclo
Remember, this is for Volume I, next time, post in Volume CIX plz.

Posted: Tue Feb 21, 2006 8:09 am
by chunyi81
Can anyone post some more test cases? I have already got 3 WA for this problem and I am using the method misof suggested for this problem. My code passes the sample input as well as the 2 test cases wook posted. It can also handle p = q as well as either p or q is 0. I am very sure my code is correct unless there is something simple I missed. Thanks for any help.

Edit: Found my mistake and got AC. It was a careless mistake in the condition of the loops in my code.

sorry i don't know your program..

Posted: Fri Mar 03, 2006 8:38 am
by sds1100
sorry i don't know your program..
sorry.sorry.sorry.sorry.sorry.

sorry i don't know your program..

Posted: Fri Mar 03, 2006 8:39 am
by sds1100
sorry i don't know your program..
sorry.sorry.sorry.sorry.sorry.