11191 - Square

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

11191 - Square

Post by arsalan_mousavian » 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?
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.

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

Re: 11191- Perfect Square

Post by emotional blind » Sun Mar 04, 2007 7:15 pm

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
Location: Vancouver, BC, Canada
Contact:

Post by sclo » 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.

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Post by sunny » 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.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sun Mar 04, 2007 8:28 pm

Be care of overflows too.

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » 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
In being unlucky I have the record.

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

input

Post by sohel » Sun Mar 04, 2007 9:41 pm

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

Post by darkos32 » 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..

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

Re: asd

Post by suhendry » Mon Mar 05, 2007 5:33 am

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)
Suhendry Effendy

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

Please help with some test cases.

Post by deepesh » 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.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » 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.. :-?
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
Location: Dhaka , Bangladesh
Contact:

Post by arif_pasha » 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..

Code: Select all

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

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

Post by sohel » Thu Mar 08, 2007 10:08 am

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Mar 08, 2007 4:16 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

Post by Observer » 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
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Post Reply

Return to “Volume 111 (11100-11199)”