## 11542 - Square

Moderator: Board moderators

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

### 11542 - Square

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

Gaussian elimination over GF[2].

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

### Re: 11542 Square

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

Mizanur Rahaman Mizan
USTC, CHITTAGONG
Website:http://www.teronga.com

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

### Re: 11542 Square

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

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

### Re: 11542 Square

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

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

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

visit : http://en.wikipedia.org/wiki/Gaussian_elimination

http://www.youngprogrammer.com
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

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

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

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

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

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

### Re: 11542 - Square

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

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

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

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

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

Need some testcases.getting WA
``````Found the mistake.