11542 - Square
Moderator: Board moderators
11542 - Square
Any hint for this problem?
-
- 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].
Re: 11542 Square
Hi,
any reference to learn (Gaussian elimination over GF[2].)
Thanks in advance.
any reference to learn (Gaussian elimination over GF[2].)
Thanks in advance.
Re: 11542 Square
Robert Gerbicz wrote:Gaussian elimination over GF[2].
![:oops:](./images/smilies/icon_redface.gif)
-
- Learning poster
- Posts: 58
- Joined: Wed Dec 31, 2003 8:43 am
- Location: Dhaka, Bangladesh
- Contact:
Re: 11542 Square
visit : http://en.wikipedia.org/wiki/Gaussian_eliminationmrmbdctg wrote:Hi,
any reference to learn (Gaussian elimination over GF[2].)
Thanks in advance.
http://www.youngprogrammer.com
Re: 11542 Square
L I M O N wrote:visit : http://en.wikipedia.org/wiki/Gaussian_eliminationmrmbdctg wrote:Hi,
any reference to learn (Gaussian elimination over GF[2].)
Thanks in advance.
http://www.youngprogrammer.com
![:oops:](./images/smilies/icon_redface.gif)
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
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]"
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]"
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
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](./images/smilies/icon_eek.gif)
it seems the test is too weak?
i think you should use long long or don't use pow ?
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!
result = 1 << result - 1;
-->change to for loop, I get AC. Hope that help!
Re: 11542 - Square
1<<x is basically left-shifting a 32-bit to x places. 1LL<<x should work.
Mir Wasi Ahmed
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. ![:(](./images/smilies/icon_frown.gif)
And yes I do shift with 1LL << shiftVal
![:(](./images/smilies/icon_frown.gif)
And yes I do shift with 1LL << shiftVal
hmm..
Re: 11542 - Square
Can anyone confirm if my output is correct for the following input set
output
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
Code: Select all
63
63
255
4095
1048575
268435455
34359738367
8796093022207
hmm..
Re: 11542 - Square
Need some testcases.getting WA
Please help.
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.