Please help me with tle error in XORSUB using gaussian elimination

general
1

i have tried to implement XORSUB with gaussian elimination. I saw almost a similar code in c which got accepted but i am getting tle for it(i am using c++). Though most of testcases in subtask 2 are getting executed correctly in time but none of the testcase in subtask 1 is getting executed in time.

My code

2

try using scanf, printf instead of cin, cout.
cin, cout is slower.

1 Like
3

a LOT slower! enough to get you TLE’d

4

Try this input:

Input:
1
1 10
10

Output:
10

Your keep on running and fails to produce any output…!

On testing i found in this input your code enters an infinite loop and problem is in while loop 

while(m) {

Debug your while loop…!
2 Likes
5

I tried that too but that also resulted in tle. test case 1 to 8 are getting tle while 9 to 16 are getting accepted correctly

6

Thanks. got accepted. I had seen on internet that this problem could be solved using gausian elimination. so i used it but i still cant understand how the reduced matrix is equivalent to the original matrix.could you please explain me how gaussian elimination is valid in solving this problem?.

7

Welcome bro…

Ahh i am really sorry i am very bad at algorithms and i used brute force to solve above problem for 30 points only so for gausian elimination i have to go through it before answering to your question… :frowning: Sorry…

8

Because as a result of this elimination, you have lineary independent rows - in other words combination of any two columns cannot result as some third row. Using this property you can use XOR and find requested maximum.

1 Like
9

Thanks @betlista for explanation…! :slight_smile:

10

@betlista can you please explain somewhat more. i still can’t get it. i can understand how gaussian algorithm can be used to solve system of linear equations , but in above case i cant understand what we are doing.

1 Like
11

@baljitsingh You may like to refer this(the last answer by me I explained the working of gaussian elimination taking an example) : http://discuss.codechef.com/questions/58752/xorsub-dec14

12

@baljitsingh:

every line of the matrix is a number A[i], where each number in the related column is the bit of the binary representation of this number. you can observe that A[i] xor A[i] xor A[i] … xor A[i] equals 0 if there is an even number of A[i] in the xorsum, or A[i] if there is an odd number of A[i] in the xor sum. it means you can multiply every line by a constant (sum is a distributive operation) without modifying the outcome. the max of xor of all lines is invariant by multiplying any A[i] by a constant of the right parity. thus, you can reduce the original A[i] matrix to a triangular equivalent matrix by gaussian elimination (but you still haven’t solved the problem). now, you sort your A[i]'s by decreasing order. you know now that each A[i] has one significant bit less than the previous one (at least one in fact). it means you can test if adding that number to the current xorsum improves your result or not, and then decide if you add it or not. you do this for all number, and get the final answer.

http://www.codechef.com/viewsolution/5505732

hope it helps ! :slight_smile: