Page 1 of 2

11191 - Square

Posted: Sun Mar 04, 2007 6:31 pm
by 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?

Re: 11191- Perfect Square

Posted: Sun Mar 04, 2007 7:15 pm
by emotional blind
arsalan_mousavian wrote: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..]

Posted: Sun Mar 04, 2007 7:16 pm
by 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.

Posted: Sun Mar 04, 2007 8:09 pm
by sunny
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
by rio
Be care of overflows too.

Posted: Sun Mar 04, 2007 8:55 pm
by 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

input

Posted: Sun Mar 04, 2007 9:41 pm
by sohel
Input:
1
5
0 0 0 1 1

Output:
10 10

asd

Posted: Mon Mar 05, 2007 4:46 am
by 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..

Re: asd

Posted: Mon Mar 05, 2007 5:33 am
by suhendry
darkos32 wrote: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 :D
darkos32 wrote: what type of variable that i have to used ?coz the value < 10^18..
C/C++: long long (%lld)

Please help with some test cases.

Posted: Mon Mar 05, 2007 6:29 pm
by 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.

Posted: Thu Mar 08, 2007 5:41 am
by 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.. :-?

Posted: Thu Mar 08, 2007 8:25 am
by 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... :oops:

Posted: Thu Mar 08, 2007 10:08 am
by 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.

Posted: Thu Mar 08, 2007 4:16 pm
by little joey
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.. :-?
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.

Posted: Thu Mar 08, 2007 6:04 pm
by 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