11542 - Square

[kmh4500]

Any hint for this problem?

[Robert Gerbicz]

Gaussian elimination over GF[2].

[mrmbdctg]

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

Thanks in advance.

[wahaha]

Gaussian elimination over GF[2].

can you show me the detail ?

[L I M O N]

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]

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

what puzzle me most is how can i transform the problem into a "Gaussian elimination" problem ?

[kmh4500]

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]

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

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]

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

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

[wasi]

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

[newkid]

Getting WA as well.

Any critical test case?

[newkid]

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

[newkid]

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


[newkid]

Got AC

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