11260 - Odd Root Sum

rossi kamal · Post by **rossi kamal** » Sun Sep 09, 2007 8:15 pm

//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 · Post by **Piklu_sust** » Sun Sep 09, 2007 9:50 pm

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 · Post by **Observer** » Tue Sep 11, 2007 5:16 am

Let me give a small hint:

Code: Select all

1 + 3 + ... + (2n-1) = n^2

pvncad · Post by **pvncad** » Tue Sep 11, 2007 6:02 am

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 · Post by **Piklu_sust** » Tue Sep 11, 2007 5:04 pm

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

CORRECT OUTPUT:

Code: Select all

I have edited the last one of the output. Hence here all of the output are correct.

suhendry · Post by **suhendry** » Tue Sep 11, 2007 8:20 pm

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

INPUT:

Code: Select all

4611686018427387903
0

CORRECT OUTPUT:

Code: Select all

82064896

Jan · Post by **Jan** » Tue Sep 11, 2007 8:57 pm

My AC code returns same output as suhendry.

Piklu_sust · Post by **Piklu_sust** » Tue Sep 11, 2007 9:29 pm

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 · Post by **FAQ** » Wed Sep 12, 2007 11:39 am

so could you edit the output above please ?

btw: I passed all your tests still WA

Sedefcho · Post by **Sedefcho** » Wed Sep 12, 2007 12:30 pm

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

Piklu_sust · Post by **Piklu_sust** » Wed Sep 12, 2007 5:03 pm

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 · Post by **Sedefcho** » Wed Sep 12, 2007 6:19 pm

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 · Post by **Piklu_sust** » Wed Sep 12, 2007 7:43 pm

Ok. No problem.
You can send me your code in the following address:

piklu.cse@gmail.com

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 · Post by **Sedefcho** » Thu Sep 13, 2007 4:50 pm

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

suhendry · Post by **suhendry** » Fri Sep 14, 2007 1:25 pm

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