11260 - Odd Root Sum

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

Moderator: Board moderators

rossi kamal
New poster
Posts: 14
Joined: Mon Sep 03, 2007 10:11 am
Contact:

11260 - Odd Root Sum

Post by rossi kamal »

//PROBLEM ID 11260


I m getting TLE..... can i improve to do better?

#include<stdio.h>
#include<math.h>
int main()
{


//freopen("in11260.txt","r",stdin);
long n;
while(scanf("%ld",&n)&&n!=0)
{

double sum=0;
long int i;

if(n%2==0)
n-=1;

for(i=1;i<=n;i+=2)
{
long a;
a=(long)sqrt(i);
sum+=a;


}

sum-=100000000.0*( (long)(sum/100000000));



printf("%.0lf\n",sum);



}






return 0;


}

Piklu_sust
New poster
Posts: 23
Joined: Fri Sep 01, 2006 10:17 am
Location: CSE, SUST

Post by Piklu_sust »

There is no cause to pass the TLE. Because the complexity of your algorithm is O(n).
Just look at the line of the problem statement.

Code: Select all

Each line contains a single 64-nit signed integer which denotes the value of n.
Your can't pass TLE with complexity of O(sqrt(n)) or O(lg n).
You must find result in each case in O(1). That means, you should find a closed form the each input.
Just see first few result in the following series:
floor(sqrt(1))+floor(sqrt(3))+floor(sqrt(5))+.....+floor(sqrt(m))
Results are:
1+1+2+2+3+3+3+3+4+4+4+4+5+5+5+5+5+5+6+6+6+6+6+6+......
You can find a pattern then using summation formula you can find a closed for for the series.
Hence, You can given answer with constant time.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

Let me give a small hint:

Code: Select all

1 + 3 + ... + (2n-1) = n^2
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

pvncad
New poster
Posts: 27
Joined: Sun Feb 18, 2007 2:14 pm

Post by pvncad »

I am getting WA. Any problem with following code ?

Code: Select all

 
   long long N = 0, n, res, nn;

    while (1) {
		scanf("%lld", &N);
		
		if (N == 0) return 0;
		
		if (N % 2 == 0) N --;
		
		n = floor(sqrt(N)) - 1;
		
		res = (n *( n + 1)) / 2;
		
		if ( res % 3 == 0) {
			res = (res / 3 ) * ( 2 * n + 1);
		}
		else {
			res *= (2 * n + 1 ) / 3;
		}

		nn = (n + 1) / 2 ;
		res += nn * nn;

		n ++;

		nn = n * n;

		if (nn % 2 == 0 ) nn ++;
		
		printf("%lld\n", (res + n * (1 + ( N - nn) / 2))%100000000); 

Piklu_sust
New poster
Posts: 23
Joined: Fri Sep 01, 2006 10:17 am
Location: CSE, SUST

Post by Piklu_sust »

There is occur overflow. You should use modular theorem in each step of addition and multiplication.
Here is some input and output:

INPUT:

Code: Select all

1
2
3
1000000000
9223372036854775807
100000000000000000
99999999999999999
123654789
1234567890
9876543210
4611686018427387903
0
YOUR OUTPUT:

Code: Select all

1
1
2
75541908
-44674654
-3521044
-3521044
16899320
22630176
16080030
-85450240
CORRECT OUTPUT:

Code: Select all

1
1
2
75541908
83293346
28651756
28651756
16899320
22630176
16080030
82064896
I have edited the last one of the output. Hence here all of the output are correct.
Last edited by Piklu_sust on Wed Sep 12, 2007 4:41 pm, edited 1 time in total.

suhendry
New poster
Posts: 14
Joined: Sat Aug 31, 2002 6:55 am

Post by suhendry »

My AC code returns 82064896 for Piklu_sust's last input.

INPUT:

Code: Select all

4611686018427387903
0
CORRECT OUTPUT:

Code: Select all

82064896
Suhendry Effendy

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

My AC code returns same output as suhendry.
Ami ekhono shopno dekhi...
HomePage

Piklu_sust
New poster
Posts: 23
Joined: Fri Sep 01, 2006 10:17 am
Location: CSE, SUST

Post by Piklu_sust »

Code: Select all

My AC code returns 82064896 for Piklu_sust's last input.

INPUT:
Code:

4611686018427387903
0


CORRECT OUTPUT:
Code:

82064896 
I give the output from running my acc program. I debug my code and see you are right. But I get accepted because there is no input like that.
My problem is rounding error. But i add a condition and hence get the same output as yours.
Thank you and sorry for my unintentional mistake.

[/quote]

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Post by FAQ »

so could you edit the output above please ?

btw: I passed all your tests still WA :(

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho »

Same story with me.

My program outputs the correct answers (given above)
but it gets WA from the judge. Strange ... Maybe there
are some special (boundary cases).

I have no idea what's wrong.

Any ideas are welcome.

Below I am posting some sample input and also the output
from my program on that input. Could someone having
an AC program verify it and tell me if my answers are wrong.

I assume in my program that the correct inputs are integers
in the closed interval [1, 2^63-1]. We cannot have negative
numbers as input, right? In such cases I just output the
number 0 as answer ?! Is that OK ?

INPUT

Code: Select all

1
2
3
9
19
29
1000
1001
1002
1003
1334455667788
10000000001
10000000015
9223372036854775807
100000000000000000
99999999999999999
123654789
1234567890
9876543210
4111686018427387101
2223372036854771111
1223372036854771111
4223372036854771002
5223372036854771001
6223372036854771000
9223372036854775797
9223372036854775798
9223372036854775799
9223372036854775800
9223372036854775801
9223372036854775802
9223372036854775803
9223372036854775804
9223372036854775805
9223372036854775806
9223372036854775807
0

OUTPUT

Code: Select all

1
1
2
9
26
49
10300
10331
10331
10362
5930690
33450000
34150000
83293346
28651756
28651756
16899320
22630176
16080030
69193482
77177890
63675584
18804889
33788440
87246958
98290851
98290851
35291350
35291350
72291849
72291849
9292348
9292348
46292847
46292847
83293346

Piklu_sust
New poster
Posts: 23
Joined: Fri Sep 01, 2006 10:17 am
Location: CSE, SUST

Post by Piklu_sust »

I tested your input and output in my two different codes that both are accepted. And I found the same output as yours.

Code: Select all

We cannot have negative numbers as input, right? 
Yes. You are correct. In my accepted codes cannot handle negative numbers.

Code: Select all

I assume in my program that the correct inputs are integers in the closed interval [1, 2^63-1].
Yes. You are right.

Code: Select all

I have no idea what's wrong. Any ideas are welcome. 
If there is subtraction in your code, try to make this in terms of addition something. (I don't know what you do).
But Another of my friend found the same output as my accepted program as he tested. And can't find wrong anything but always got Wrong answer.
After some addition, at last he get accepted.

-------------------------------------------------------------------------------------
Sorry for my poor English.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho »

Hello, Piklu_sust and thanks for answering.

I didn't understand quite well what you mean here:
If there is subtraction in your code, try to make this
in terms of addition something. (I don't know what you do).

As far as I understand you are saying
that I should avoid doing subtractions in my code.

So I replaced all subtractions in my code
( a - b )
by
( a + (~b) + 1)
The second formula is another way to do subtraction.

But still WA...

I can send you my code via PM if you want ...
I have no idea what is wrong with my code in the
judge's environment. I made over 20 submissions for
this problem but still WA.

Weird.....

Piklu_sust
New poster
Posts: 23
Joined: Fri Sep 01, 2006 10:17 am
Location: CSE, SUST

Post by Piklu_sust »

Ok. No problem.
You can send me your code in the following address:
I will debug your code in my pc. Then I may find the problem in your code.
I think, I don't express what I want to say.
_______________________________________________________________________
I will try my best.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho »

I rewrote my program in Java.
It still produces the right answers on
my machine but the judge still gives me WA :o

suhendry
New poster
Posts: 14
Joined: Sat Aug 31, 2002 6:55 am

Post by suhendry »

Sedefcho wrote:I didn't understand quite well what you mean here:
If there is subtraction in your code, try to make this
in terms of addition something. (I don't know what you do).
Here is an example:

Supposed that we want to calculate (a-b)%m where a = 10, b = 5, and m = 3.

This is what we expect from the equation:
(10 - 5) % 3
= 5 % 3
= 2

Now let's do our equation with modular arithmetic theorem:
(10 - 5) % 3
= (10%3 - 5%3) % 3
= (1 - 2) % 3
= -1 % 3
= -1
It gives a different answer. I don't know what is the correct answer for -1%3 in math, is it -1 or 2 (well, i'm not good with math or number theory). I test it on C/C++ and I got -1 for -1%3.

So, we should adjust the equation into:
(a-b)%m == (a%m - b%m + m) % m
or something like this..
Suhendry Effendy

Post Reply

Return to “Volume 112 (11200-11299)”