online-judge.uva.es

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;

}

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.

by **Observer** » Tue Sep 11, 2007 5:16 am

Let me give a small hint:

Code: Select all: 1 + 3 + ... + (2n-1) = n^2

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);

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

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

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

My AC code returns same output as suhendry.

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]

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

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

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.

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

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.

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

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

online-judge.uva.es

11260 - Odd Root Sum

11260 - Odd Root Sum

Who is online