## 11260 - Odd Root Sum

Moderator: Board moderators

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

}
rossi kamal
New poster

Posts: 14
Joined: Mon Sep 03, 2007 10:11 am

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.
Piklu_sust
New poster

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

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
Observer
Guru

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

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: 27
Joined: Sun Feb 18, 2007 2:14 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
`12310000000009223372036854775807100000000000000000999999999999999991236547891234567890987654321046116860184273879030`

Code: Select all
`11275541908-44674654-3521044-3521044168993202263017616080030-85450240`

CORRECT OUTPUT:
Code: Select all
`1127554190883293346286517562865175616899320226301761608003082064896`

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.
Piklu_sust
New poster

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

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

INPUT:
Code: Select all
`46116860184273879030`

CORRECT OUTPUT:
Code: Select all
`82064896`
Suhendry Effendy
suhendry
New poster

Posts: 12
Joined: Sat Aug 31, 2002 6:55 am
Location: Indonesia

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

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

Code: Select all
`My AC code returns 82064896 for Piklu_sust's last input.INPUT:Code:46116860184273879030CORRECT 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]
Piklu_sust
New poster

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

so could you edit the output above please ?

btw: I passed all your tests still WA
FAQ
Learning poster

Posts: 84
Joined: Wed Jan 28, 2004 6:23 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
`1239192910001001100210031334455667788100000000011000000001592233720368547758071000000000000000009999999999999999912365478912345678909876543210411168601842738710122233720368547711111223372036854771111422337203685477100252233720368547710016223372036854771000922337203685477579792233720368547757989223372036854775799922337203685477580092233720368547758019223372036854775802922337203685477580392233720368547758049223372036854775805922337203685477580692233720368547758070`

OUTPUT
Code: Select all
`11292649103001033110331103625930690334500003415000083293346286517562865175616899320226301761608003069193482771778906367558418804889337884408724695898290851982908513529135035291350722918497229184992923489292348462928474629284783293346`

Sedefcho
A great helper

Posts: 375
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

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.
Piklu_sust
New poster

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

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

Sedefcho
A great helper

Posts: 375
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Ok. No problem.
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.
Piklu_sust
New poster

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

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

Sedefcho
A great helper

Posts: 375
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

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
suhendry
New poster

Posts: 12
Joined: Sat Aug 31, 2002 6:55 am
Location: Indonesia

Next