11260  Odd Root Sum
Moderator: Board moderators

 New poster
 Posts: 14
 Joined: Mon Sep 03, 2007 10:11 am
 Contact:
11260  Odd Root Sum
//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;
}
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;
}

 New poster
 Posts: 23
 Joined: Fri Sep 01, 2006 10:17 am
 Location: CSE, 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.
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.
Just look at the line of the problem statement.
Code: Select all
Each line contains a single 64nit signed integer which denotes the value of 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.
Let me give a small hint:
Code: Select all
1 + 3 + ... + (2n1) = n^2
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
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);

 New poster
 Posts: 23
 Joined: Fri Sep 01, 2006 10:17 am
 Location: CSE, SUST
There is occur overflow. You should use modular theorem in each step of addition and multiplication.
Here is some input and output:
INPUT:
YOUR OUTPUT:
CORRECT OUTPUT:
I have edited the last one of the output. Hence here all of the output are correct.
Here is some input and output:
INPUT:
Code: Select all
1
2
3
1000000000
9223372036854775807
100000000000000000
99999999999999999
123654789
1234567890
9876543210
4611686018427387903
0
Code: Select all
1
1
2
75541908
44674654
3521044
3521044
16899320
22630176
16080030
85450240
Code: Select all
1
1
2
75541908
83293346
28651756
28651756
16899320
22630176
16080030
82064896
Last edited by Piklu_sust on Wed Sep 12, 2007 4:41 pm, edited 1 time in total.
My AC code returns 82064896 for Piklu_sust's last input.
INPUT:
CORRECT OUTPUT:
INPUT:
Code: Select all
4611686018427387903
0
Code: Select all
82064896
Suhendry Effendy

 New poster
 Posts: 23
 Joined: Fri Sep 01, 2006 10:17 am
 Location: CSE, SUST
Code: Select all
My AC code returns 82064896 for Piklu_sust's last input.
INPUT:
Code:
4611686018427387903
0
CORRECT OUTPUT:
Code:
82064896
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]
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^631]. We cannot have negative
numbers as input, right? In such cases I just output the
number 0 as answer ?! Is that OK ?
INPUT
OUTPUT
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^631]. 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

 New poster
 Posts: 23
 Joined: Fri Sep 01, 2006 10:17 am
 Location: CSE, SUST
I tested your input and output in my two different codes that both are accepted. And I found the same output as yours.
Yes. You are correct. In my accepted codes cannot handle negative numbers.
Yes. You are right.
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.
Code: Select all
We cannot have negative numbers as input, right?
Code: Select all
I assume in my program that the correct inputs are integers in the closed interval [1, 2^631].
Code: Select all
I have no idea what's wrong. Any ideas are welcome.
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.
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.....
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.....

 New poster
 Posts: 23
 Joined: Fri Sep 01, 2006 10:17 am
 Location: CSE, SUST
Here is an example: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).
Supposed that we want to calculate (ab)%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:
(ab)%m == (a%m  b%m + m) % m
or something like this..
Suhendry Effendy