11542 - Square

Moderator: Board moderators

11542 - Square

Any hint for this problem?
kmh4500
New poster

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

Re: 11542 Square

Gaussian elimination over GF[2].
Robert Gerbicz
Experienced poster

Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek

Re: 11542 Square

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

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

mrmbdctg
New poster

Posts: 18
Joined: Sun Mar 04, 2007 7:12 am

Re: 11542 Square

Robert Gerbicz wrote:Gaussian elimination over GF[2].

can you show me the detail ?
wahaha
New poster

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

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
L I M O N
Learning poster

Posts: 58
Joined: Wed Dec 31, 2003 8:43 am

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 ?
wahaha
New poster

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

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]"
kmh4500
New poster

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

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 ?
wahaha
New poster

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

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!
lyhung
New poster

Posts: 7
Joined: Tue Oct 28, 2008 7:20 am

Re: 11542 - Square

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

Posts: 2
Joined: Mon Jul 30, 2007 12:10 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
`8101 2 3 4 5 6 7 8 9 10102 4 6 8 10 12 14 16 18 20102 8 12 24 32 48 96 72 27 18201 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20301 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 30401 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 40501 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 50601 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
`636325540951048575268435455343597383678796093022207`
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..
newkid
Learning poster

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