11542 - Square

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

Moderator: Board moderators

kmh4500
New poster
Posts: 3
Joined: Sun Oct 26, 2008 12:30 am

11542 - Square

Post by kmh4500 » Sun Oct 26, 2008 12:33 am

Any hint for this problem?

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11542 Square

Post by Robert Gerbicz » Sun Oct 26, 2008 1:55 am

Gaussian elimination over GF[2].

User avatar
mrmbdctg
New poster
Posts: 18
Joined: Sun Mar 04, 2007 7:12 am
Location: Bangladesh
Contact:

Re: 11542 Square

Post by mrmbdctg » Sun Oct 26, 2008 8:07 pm

Hi,
any reference to learn (Gaussian elimination over GF[2].)

Thanks in advance.
Mizanur Rahaman Mizan
USTC, CHITTAGONG
BANGLADESH
Website:http://www.teronga.com

wahaha
New poster
Posts: 16
Joined: Mon Jul 14, 2008 6:18 pm

Re: 11542 Square

Post by wahaha » Wed Oct 29, 2008 11:12 am

Robert Gerbicz wrote:Gaussian elimination over GF[2].
:oops: can you show me the detail ?

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Location: Dhaka, Bangladesh
Contact:

Re: 11542 Square

Post by L I M O N » Wed Oct 29, 2008 12:34 pm

mrmbdctg wrote:Hi,
any reference to learn (Gaussian elimination over GF[2].)

Thanks in advance.
visit : http://en.wikipedia.org/wiki/Gaussian_elimination

http://www.youngprogrammer.com

wahaha
New poster
Posts: 16
Joined: Mon Jul 14, 2008 6:18 pm

Re: 11542 Square

Post by wahaha » Wed Oct 29, 2008 2:12 pm

L I M O N wrote:
mrmbdctg wrote:Hi,
any reference to learn (Gaussian elimination over GF[2].)

Thanks in advance.
visit : http://en.wikipedia.org/wiki/Gaussian_elimination

http://www.youngprogrammer.com
:oops: what puzzle me most is how can i transform the problem into a "Gaussian elimination" problem ?

kmh4500
New poster
Posts: 3
Joined: Sun Oct 26, 2008 12:30 am

Re: 11542 Square

Post by kmh4500 » Wed Oct 29, 2008 3:04 pm

10
10
2 2 3 3 5 5 2 2 3 3
3
552 1235 176
10
288 325 371 552 1235 176 288 144 276 138
3
1 1 1
3
1 1 2
2
1000000000000000 1000000000000000
4
1111 111 11 1
5
12 23 34 45 51
8
12 23 34 45 56 67 78 81
1
100000000000000

Answers are..
127
0
15
7
3
1
1
0
1
1

And I made table like this
For 4,6,10,15 case
4 6 10 15
2|0 1 1 0
3|0 1 0 1
5|0 0 1 1

And conducted GE

I'm getting WA.. I don't know why. I'll appreciate critical example.
Anyway, Thank you for explanation "GE over FP[2]"

wahaha
New poster
Posts: 16
Joined: Mon Jul 14, 2008 6:18 pm

Re: 11542 Square

Post by wahaha » Wed Oct 29, 2008 6:16 pm

kmh4500 wrote:10
10
2 2 3 3 5 5 2 2 3 3
3
552 1235 176
10
288 325 371 552 1235 176 288 144 276 138
3
1 1 1
3
1 1 2
2
1000000000000000 1000000000000000
4
1111 111 11 1
5
12 23 34 45 51
8
12 23 34 45 56 67 78 81
1
100000000000000

Answers are..
127
0
15
7
3
1
1
0
1
1

And I made table like this
For 4,6,10,15 case
4 6 10 15
2|0 1 1 0
3|0 1 0 1
5|0 0 1 1

And conducted GE

I'm getting WA.. I don't know why. I'll appreciate critical example.
Anyway, Thank you for explanation "GE over FP[2]"
:o what a surprise thing is that i can't pass all your tests, but i got AC.

it seems the test is too weak?

i think you should use long long or don't use pow ?

lyhung
New poster
Posts: 7
Joined: Tue Oct 28, 2008 7:20 am

Re: 11542 Square

Post by lyhung » Thu Nov 27, 2008 1:07 pm

I get wrong answer when I use this
result = 1 << result - 1;

-->change to for loop, I get AC. Hope that help!

wasi
New poster
Posts: 2
Joined: Mon Jul 30, 2007 12:10 am
Location: Dhaka, Bangladesh

Re: 11542 - Square

Post by wasi » Mon Dec 29, 2008 11:59 am

1<<x is basically left-shifting a 32-bit to x places. 1LL<<x should work.
Mir Wasi Ahmed

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

Re: 11542 - Square

Post by newkid » Sat Jun 18, 2011 12:08 pm

Getting WA as well.

Any critical test case?
hmm..

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

Re: 11542 - Square

Post by newkid » Sat Jun 18, 2011 9:39 pm

I tried with random generated input and a brute force algo. Although I tried brute force algo with N <= 30, I get correct result from my WA algo as well. :(

And yes I do shift with 1LL << shiftVal
hmm..

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

Re: 11542 - Square

Post by newkid » Sun Jun 19, 2011 2:27 am

Can anyone confirm if my output is correct for the following input set

Code: Select all

8

10
1 2 3 4 5 6 7 8 9 10
10
2 4 6 8 10 12 14 16 18 20
10
2 8 12 24 32 48 96 72 27 18
20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
30
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
40
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
50
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
60
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
output

Code: Select all

63
63
255
4095
1048575
268435455
34359738367
8796093022207
hmm..

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

Re: 11542 - Square

Post by newkid » Fri Jun 24, 2011 1:31 am

Got AC

The above results are correct. I got WA for different reason.
hmm..

sanzeee
New poster
Posts: 6
Joined: Tue Oct 19, 2010 9:56 pm

Re: 11542 - Square

Post by sanzeee » Wed May 28, 2014 10:36 pm

Need some testcases.getting WA
Please help.

Code: Select all

Found the mistake.
Last edited by sanzeee on Sun Jun 01, 2014 12:07 pm, edited 1 time in total.

Post Reply

Return to “Volume 115 (11500-11599)”