10994 - Simple Addition

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

bakey2
New poster
Posts: 3
Joined: Sun Feb 12, 2006 12:56 am

10994 - Simple Addition

Post by bakey2 » Sun Feb 12, 2006 12:58 am

Can anyone tell me how to solve the problem 10994 which is the E problem last contest?Thx

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Sun Feb 12, 2006 1:37 am

(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.

bakey2
New poster
Posts: 3
Joined: Sun Feb 12, 2006 12:56 am

Post by bakey2 » Sun Feb 12, 2006 4:11 am

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~~~~

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

Post by wook » Sun Feb 12, 2006 4:23 am

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.
Sorry For My Poor English.. :)

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Sun Feb 12, 2006 4:24 am

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?

bakey2
New poster
Posts: 3
Joined: Sun Feb 12, 2006 12:56 am

Post by bakey2 » Sun Feb 12, 2006 5:09 am

Thx wook & misof ~~~
I will have a try~

imnew
New poster
Posts: 5
Joined: Sun Feb 12, 2006 6:37 am

Post by imnew » Sun Feb 12, 2006 6:40 am

---thanks.....got it.....
what is the result for
p = 1, q = 2147483647
p = 100000, q = 200000
Thanks in advance.....
Last edited by imnew on Sun Feb 12, 2006 6:48 am, edited 1 time in total.

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

Post by wook » Sun Feb 12, 2006 6:46 am

imnew wrote:what is the result for
p = 1, q = 2147483647
p = 100000, q = 200000
Thanks in advance.....
10737418158 and 499998, respectively.
Sorry For My Poor English.. :)

el cheeto
New poster
Posts: 9
Joined: Mon Feb 13, 2006 12:40 am
Location: Mexico

10994 Compile Error

Post by el cheeto » Mon Feb 13, 2006 12:59 am

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
Last edited by el cheeto on Mon Mar 27, 2006 7:00 am, edited 3 times in total.

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Mon Feb 13, 2006 5:43 am

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.

el cheeto
New poster
Posts: 9
Joined: Mon Feb 13, 2006 12:40 am
Location: Mexico

Post by el cheeto » Mon Feb 13, 2006 7:04 am

Thank you chunyi81, I submited my code in C instead of C++ and get Accepted, but the true is that i don

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Feb 13, 2006 10:52 am

Remember, this is for Volume I, next time, post in Volume CIX plz.

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Tue Feb 21, 2006 8:09 am

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.

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

sorry i don't know your program..

Post by sds1100 » Fri Mar 03, 2006 8:38 am

sorry i don't know your program..
sorry.sorry.sorry.sorry.sorry.

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

sorry i don't know your program..

Post by sds1100 » Fri Mar 03, 2006 8:39 am

sorry i don't know your program..
sorry.sorry.sorry.sorry.sorry.

Post Reply

Return to “Volume 109 (10900-10999)”