11191 - Square

Moderator: Board moderators

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

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:

Re: 11191- Perfect Square

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

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
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
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET
i got so many WA's bcoz i didnt count the triples properly where any 2 or all 3 numbers are same.

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
Be care of overflows too.

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

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

input

Input:
1
5
0 0 0 1 1

Output:
10 10

darkos32
New poster
Posts: 27
Joined: Tue Jul 25, 2006 8:10 am
Location: Indonesia
Contact:

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

suhendry
New poster
Posts: 14
Joined: Sat Aug 31, 2002 6:55 am

Re: asd

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
darkos32 wrote: what type of variable that i have to used ?coz the value < 10^18..
C/C++: long long (%lld)
Suhendry Effendy

deepesh
New poster
Posts: 13
Joined: Sat Dec 23, 2006 5:57 am

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.

Thank you

Edit:
Got accepted. Removed the code.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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

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

Code: Select all

``````Code removed...
``````
Thanx sohel. I should have noticed it...
Last edited by arif_pasha on Thu Mar 08, 2007 12:45 pm, edited 1 time in total.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org