10830 - A New Function

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

Moderator: Board moderators

Programmer
New poster
Posts: 9
Joined: Sun Mar 13, 2005 11:41 am

10830 - A New Function

Post by Programmer » Mon Mar 21, 2005 6:05 pm

Hello.Can somebody tell me how to solve this problem.
I find formula for SOD.I find formula for CSOD too but it takes N operations.I do it another way and came up to the problem of finding sum of reminders 1 to n.
Please help me give some hint.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Mon Mar 21, 2005 8:34 pm

I don't know what formulas your have now so I just talk about my logic.
Although the detail may be different from each person, but the logic should be similar:

To find CSOD you can sum some function O(1) f(x, N) from 1 to N, that is,
CSOD(N) = f(1,N)+f(2,N)+...+f(N,N)

In my code, the values f(x,N) will repeat many times when x > root(N), so I don't add each term f(x,N) slowly when x > root(N). Instead, I find out how many values of x will make f(x,N) = k of a certain value in O(1), then I use multiplication to sum these f(x,N) to the answer.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

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

Post by Larry » Mon Mar 21, 2005 8:49 pm

I've tested my solution with bruteforce for N < 1000000, but I cannot get the right answer for 2 billion. I also cannot detect any overflows (or underflows).. can someone lend me some insight and/or test cases? Thanks.

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Mon Mar 21, 2005 9:06 pm

Hello.
I dont think it's hard to find this formula.
CSOD(n)=P-n+1 P=((n div 2)-1)*2+((n div 3)-1)*3 +...+((n div n)-1)*n
But for calculating it I must do N operations,it is too slow.Can this formula calculated faster?
Eduard
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Mon Mar 21, 2005 9:17 pm

Eduard wrote: Can this formula calculated faster?
My previous post is talking about that.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Mon Mar 21, 2005 9:46 pm

I don't understand your previous post well.
I find out how many values of x will make f(x,N) = k of a certain value in O(1)
For wich K are you doing it?What is time complexity of your program?
Thanks.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Mon Mar 21, 2005 10:03 pm

In my previous post I don't want to give too much detail as I don't want to write spoiler..... Here is the detail:

Code: Select all

CSOD(n)=((n div 2)-1)*2+((n div 3)-1)*3 +...+((n div n)-1)*n 
       =(n div 2)*2 + (n div 3)*3 + ..... + (n div n)*n - sum(2,n)
The value of "n div x" will repeat when x becomes larger, and when x > root(N), n div x <= root(N), and I just try all such n div x as value K.

And so the complexity is root(N)
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Mon Mar 21, 2005 10:07 pm

Now i got it.
Thanks.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

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

Post by Larry » Mon Mar 21, 2005 11:39 pm

What's the answer for:

Code: Select all

1000000
2000000
1000000000
I get:

Code: Select all

322466618438
1289867461381
322467032612360629

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

Post by misof » Tue Mar 22, 2005 2:42 am

Larry wrote:What's the answer for:

Code: Select all

1000000
2000000
1000000000
I get:

Code: Select all

322466618438
1289867461381
322467032612360629
Well, my answer is

Code: Select all

Case 1: 322466618438
Case 2: 1289867461381
Case 3: 322467032612360629
Surely you can see the difference :D
(In other words, the numbers are correct, but are you writing also the case numbers correctly?)

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Tue Mar 22, 2005 3:02 am

I obtain the same results,

What is the output for this, please:

Code: Select all

0
1
2000000000
1347838239
123848
137587
38495969
34888888
1234923
40
41
42
1000
2000
1000000
2000000
10000000
20000000
100000000
249999999
249999997
Thanks in advance

Diego Caminha
New poster
Posts: 5
Joined: Wed Mar 16, 2005 1:40 am
Location: Brazil

Post by Diego Caminha » Tue Mar 22, 2005 4:08 am

"Input is terminated by a line where the value of n=0. This line should not be processed."

I didn't read the problem very well the first time and got some WA because of this. The sample input doesn't have a 0 at the end :evil:

Input:

Code: Select all

1 
2000000000 
1347838239 
123848 
137587 
38495969 
34888888 
1234923 
40 
41 
42 
1000 
2000 
1000000 
2000000 
10000000 
20000000 
100000000 
249999999 
249999997
0
Output:

Code: Select all

Case 1: 0
Case 2: 1289868132101422932
Case 3: 585815512116088361
Case 4: 4945965530
Case 5: 6104124608
Case 6: 477876619598302
Case 7: 392517961466207
Case 8: 491771668356
Case 9: 483
Case 10: 483
Case 11: 536
Case 12: 321582
Case 13: 1288012
Case 14: 322466618438
Case 15: 1289867461381
Case 16: 32246696794797
Case 17: 128986798547827
Case 18: 3224670272194238
Case 19: 20154189031290875
Case 20: 20154188822204538

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Tue Mar 22, 2005 4:32 am

Ooops! :o
"Input is terminated by a line where the value of n=0. This line should not be processed."
You are right.
That was my problem.

Thanks!

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

Post by Larry » Tue Mar 22, 2005 4:32 pm

misof: thanks, actually, I wasn't on a machine I can code on, so I wrote it in PERL to see if my formula's working. Actually, I never submitted, because I thought it didn't match the sample output, but I finally read the sample input correctly, and it's 200 million, not 2 billion! Talk about stupid mistake!

Andrey
New poster
Posts: 16
Joined: Sat Mar 05, 2005 8:25 pm
Location: Ukraine,Vinnitsa

WHY WA?

Post by Andrey » Wed Mar 23, 2005 11:13 am

For this input

Code: Select all

1
2
3
4
5
6
7
8
9
10
0
I get this output:

Code: Select all

Case 1: 0
Case 2: 0
Case 3: 0
Case 4: 2
Case 5: 2
Case 6: 7
Case 7: 7
Case 8: 13
Case 9: 16
Case 10: 23
I think it's right, isn't it???
Last edited by Andrey on Wed Mar 23, 2005 4:10 pm, edited 1 time in total.

Post Reply

Return to “Volume 108 (10800-10899)”