### 11191 - Square

Posted:

**Sun Mar 04, 2007 6:31 pm**i have no idea how to calculate Y in O(N), i have solved the problem for the value of X already, can anybody give me a hint without spoiling the problem?

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=37&t=15236

Page **1** of **2**

Posted: **Sun Mar 04, 2007 6:31 pm**

i have no idea how to calculate Y in O(N), i have solved the problem for the value of X already, can anybody give me a hint without spoiling the problem?

Posted: **Sun Mar 04, 2007 7:15 pm**

is 15 a prime numberarsalan_mousavian wrote:int prime [11] = {2,3,5,7,11,13,15,17,19,23,29};

i think there is an O(2^20) algorithm for calculating Y. [but i m getting WA..]

Posted: **Sun Mar 04, 2007 7:16 pm**

Think about how could you multiply 3 numbers to get perfect square.

Hint: My solution for computing Y is O(n^2), for this problem, n is 2^10, so it is still feasible.

Why are you using MAP anyway, it maybe to too slow. Just use an size 2^11 array. (one of the bit indicates whether it is negative or positive.)

Carefully work out the cases for Y. There are a few of them.

Hint: My solution for computing Y is O(n^2), for this problem, n is 2^10, so it is still feasible.

Why are you using MAP anyway, it maybe to too slow. Just use an size 2^11 array. (one of the bit indicates whether it is negative or positive.)

Carefully work out the cases for Y. There are a few of them.

Posted: **Sun Mar 04, 2007 8:09 pm**

i got so many WA's bcoz i didnt count the triples properly where any 2 or all 3 numbers are same.

Posted: **Sun Mar 04, 2007 8:28 pm**

Be care of overflows too.

Posted: **Sun Mar 04, 2007 8:55 pm**

now i 've got WA, can somebody give me some tricky testcases, here is my code

Code: Select all

`removed after getting AC`

Posted: **Sun Mar 04, 2007 9:41 pm**

1

5

0 0 0 1 1

10 10

Posted: **Mon Mar 05, 2007 4:46 am**

hi,can anybody help me..i use O(n^3) algo...

for(int a = 0;a<n;a++)

for(int b = a+1;b<n;b++)

for(int c = b+1;c<n;c++)

result = x[a] * x** * x[c];**

n i got TLE ( of course )..Can anybody help me give me the solution please ?

n what type of variable that i have to used ?coz the value < 10^18..

thanks..

for(int a = 0;a<n;a++)

for(int b = a+1;b<n;b++)

for(int c = b+1;c<n;c++)

result = x[a] * x

n i got TLE ( of course )..Can anybody help me give me the solution please ?

n what type of variable that i have to used ?coz the value < 10^18..

thanks..

Posted: **Mon Mar 05, 2007 5:33 am**

darkos32 wrote:hi,can anybody help me..i use O(n^3) algo.

C/C++: long long (%lld)darkos32 wrote: what type of variable that i have to used ?coz the value < 10^18..

Posted: **Mon Mar 05, 2007 6:29 pm**

I am using a order 2^22 algorithm. But I am getting a run time error signal 11.

Can some one tell me as to how I go about fixing the bug. I am getting valid answers on Sohel's test case and all the sample test cases.

Please help, with a few critical test cases.

Thank you

Edit:

Got accepted. Removed the code.

Can some one tell me as to how I go about fixing the bug. I am getting valid answers on Sohel's test case and all the sample test cases.

Please help, with a few critical test cases.

Thank you

Edit:

Got accepted. Removed the code.

Posted: **Thu Mar 08, 2007 5:41 am**

Well, with the same algorithm I get TLE in PASCAL, and Accepted in around 3 seconds in C. Which is not surprising since int64 computations are very slow in PASCAL..

Posted: **Thu Mar 08, 2007 8:25 am**

Hi all, Can someone please tell me what wrong i am doing here. I tested with my own generated test data and compared with the output of Brute force algo. But getiing WA all the time..
Thanx **sohel**. I should have noticed it...

Code: Select all

```
Code removed...
```

Posted: **Thu Mar 08, 2007 10:08 am**

You have declared bothtwos += nonZero*zero+nC2(zero);

The product of these two values can exceed integer limit. So, converting them to

Posted: **Thu Mar 08, 2007 4:16 pm**

Are you sure? Most time for this problem is spent in reading the input and calculating the bitmasks,Observer wrote:Well, with the same algorithm I get TLE in PASCAL, and Accepted in around 3 seconds in C. Which is not surprising since int64 computations are very slow in PASCAL..

I can't try myself, because it's too long ago since I programmed in Pascal and I don't have FPC installed, but I think if you build your own code to read the input, a Pascal solution can avoid TLE. Just a thought, can't be sure.

Posted: **Thu Mar 08, 2007 6:04 pm**

Hmm... I sent a code that only reads in the input numbers (with read()) and factorize them with 2, 3, 5, 7, ..., 29. And that gives a TLE...

Also see my old post at: http://online-judge.uva.es/board/viewto ... 4&start=11

Also see my old post at: http://online-judge.uva.es/board/viewto ... 4&start=11