11191 - Square
Moderator: Board moderators
-
- Experienced poster
- Posts: 111
- Joined: Mon Jan 09, 2006 6:19 pm
- Location: Tehran, Iran
- Contact:
11191 - Square
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?
Last edited by arsalan_mousavian on Sun Mar 04, 2007 8:55 pm, edited 1 time in total.
In being unlucky I have the record.
-
- A great helper
- Posts: 383
- Joined: Mon Oct 18, 2004 8:25 am
- Location: Bangladesh
- Contact:
Re: 11191- Perfect Square
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..]
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.
-
- Experienced poster
- Posts: 111
- Joined: Mon Jan 09, 2006 6:19 pm
- Location: Tehran, Iran
- Contact:
now i 've got WA, can somebody give me some tricky testcases, here is my code
Code: Select all
removed after getting AC
In being unlucky I have the record.
asd
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 * 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
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 zerodarkos32 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..
Suhendry Effendy
Please help with some test cases.
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.
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.. 

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
-
- New poster
- Posts: 42
- Joined: Fri Jun 13, 2003 3:47 pm
- Location: Dhaka , Bangladesh
- Contact:
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...

Last edited by arif_pasha on Thu Mar 08, 2007 12:45 pm, edited 1 time in total.
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
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.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.
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
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