Wrong answer in XMAX Spoj question

I was solving XMAX question of Spoj using Gaussian elimination method to find the max subset xor of an array.
But it’s giving me WRONG answer after passing through few testcases,don’t to why? Most surprisingly XORSUB question of Codechef(which is nearly same as XMAX, just have difference of initializing ans=0 and ans=k) is giving me Right answer on codechef.

Here are links:
XMAX question: http://www.spoj.com/problems/XMAX/.
My XMAX solution: http://ideone.com/UbRCH9
XORSUB question: https://www.codechef.com/problems/XORSUB.
My XORSUB solution: https://www.codechef.com/viewsolution/14208798

Check the first answer here- https://discuss.codechef.com/questions/58422/xorsub-editorial

That guy also used Gaussian elimination, so you can compare the code for error. If that doesnt help, i will have a look at the codes later :slight_smile:

EDIT- I cannot see your XMAX solution on SPOJ (most probably as SPOJ keeps others solution hidden). Can you share it via ideone or something? :slight_smile:

I have edited my link.By the way I learned to implement Gaussian elimination from that same guy’s code :slight_smile: So, it’s exactly the same. So, I’m confused why is it producing wrong answer.

1 Like

Your code works wrongly for this test case-

Your Output
Expected Output

One question after another, its strange that one answer leads to another question. ^^

I think my Gaussian function is of time complexity O(nlogn* nlogn)=O(n^2* (logn)^2)=O(n^2) and n is upto 10^5. That’s why it is producing TLE.

This Gaussian implementation from hackerearth -https://www.hackerearth.com/practice/notes/gaussian-elimination/ has far better time complexity.

But I didn’t get the point that why swapping erase and insert instructions gave right answer, whereas previously it gave wrong answer.

Follow the question here - https://discuss.codechef.com/questions/101843/regarding-c-stl-set

It gave me a TLE on swapping even for small input :confused: . And lol, i notice that i missed out telling that the bug is fixed by swapping the two statements. Good job figuring that out ^^

No. I didn’t figure that out by myself. I read your edited history :slight_smile: and then I remembered that someone had pointed out to swap the instructions in comment section of XORSUB’s editorial.

Lol…why would anyone read the edited history?! XD

Well, i edited that part out because firstly, i myself cannot explain that thing, need help there myself, and secondly, i felt that it did not come out politely. I felt its better to skip that thing out.

Ok.I got that when m will be zero then the order of statements will matter. But what about TLE even on small inputs? Did you get that?

Yes, i got tle on small inputs. You want me to debug that?

Try it if you get time,I couldn’t figure out what is causing TLE even on small inputs as you said.

Hey!! By the way who are you? Are you in junior year or senior year? You are so active on Codechef discuss. Are you on Quora where I could follow you.

Okay, i think that tle was server issue, cause i am not getting tle now. I also kind of figured out the cause of error. When we erase first and insert next, then for some reason the iterator pointed at the end of set, which caused the loop to exit pre maturely.

It will be my 3rd semester this time. I am inactive on Quuora or FB, so you’ll most probably find me here :stuck_out_tongue:

From what i can conclude is, that since erasing element invalidates the iterator, its advisable to use erase() at last. What i feel is, that, since erase invalidates the iterator, the iterator picks up the value returned by s.insert() [which is the position of inserted element- here- end of set] and causes bug [it jumps to position of inserted element after insertion function]. But when insert first and erase in end, iterator goes to end of loop, and i++ makes it point to next element. [i made a custom loop with iterator to test it].

Also, this thing is not only limited to set. Its advised to insert first and delete later in every other STL of C++ , like vectors etc.

It is something with the iterators and them getting invalidated. Someone with in depth knowledge of working of these data structure can help you for sure. I will need a reference if i am to answer the Q satisfactorily.

OK. Thank you. Sorry for late reply.

Check for @meooow 's answer on the STL thread i created. He gave a very nice answer to it ^^

yeah!! That’s very good answer. Erasing element from these container should be done safely.