11191 - Square

[arsalan_mousavian]

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?

[emotional blind]

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

is 15 a prime number

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

[sclo]

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.

[sunny]

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

[rio]

Be care of overflows too.

[arsalan_mousavian]

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

Code: Select all

removed after getting AC

[sohel]

Input:
1
5
0 0 0 1 1

Output:
10 10

[darkos32]

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

[suhendry]

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

sclo already give you the answer. Figure out what made a number perfect square. There should be only 2^10 different values (excluding -/+). And be careful with zero

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

C/C++: long long (%lld)

[deepesh]

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.

[Observer]

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

[arif_pasha]

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

Code: Select all

Code removed...

Thanx sohel. I should have noticed it...

[sohel]

twos += nonZero*zero+nC2(zero);

You have declared both nonZero and zero as int.
The product of these two values can exceed integer limit. So, converting them to long long should rectifiy the problem.

[little joey]

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

Are you sure? Most time for this problem is spent in reading the input and calculating the bitmasks, not in calculating the values (that's probably why rio's solution is so fast, he calculates the bitmasks efficiently). Pascals read() function is notably slow, but I think the 64-bit calculating code FPC produces is comparable in speed to GCC's code for C.

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.

[Observer]

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