WrongAnswerOnTestcase1's blog

By WrongAnswerOnTestcase1, history, 4 days ago, In English

I have implemented as per the algorithm suggested in the EDU section (here), however it gets MLE for some reason. The memory complexity should be O(m log m) which shouldn't be too much.

Can anyone tell me how to optimize this code (for Step 3 Problem C — Dynamic Connectivity Offline) for memory. I believe my code is logically correct, however it get MLE on (hidden) testcase 2. I have tried all the optimizations I could think of.

Also I think that the pseudocode in the EDU section (here) is not correct. In the base case, we should apply the unions applicable over that leaf, since the query segment could have been split in such a way that it covers only the leaf. Please correct me if I am wrong.

Here is my code.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone?

»
4 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Try to came up with $$$stack<int>$$$ approach of persistent DSU.

$$$map<pii, vector<pii> >$$$ is also bad, it's possible to do it with $$$map<pii, int>$$$

  • »
    »
    4 days ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    I did both the optimizations, still the same MLE.

    updated code

    • »
      »
      »
      4 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ML in this problem is really tough. My submission uses ~183/256 mb.

      Try another two optimizations:

      first
      second

      You can check my OK submission to understand details.

      • »
        »
        »
        »
        4 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Something weird is happening. I thought it was MLE, but actually it shows "Runtime Error on test 2" with memory used = 262100 KB, so I thought it was MLE.

        I changed my approach to segment tree like method where I precompute all the segments where add/remove queries happen. Weird enough, this submission still shows "Runtime Error on test 2" with memory used = 28200 KB. I have no idea how runtime error is happening.

        segment tree like code

        • »
          »
          »
          »
          »
          4 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Btw, you may still have MLE, but your code falls with seg fault earlier ,than you used all the memory.

          So, I guess, you code doesn't work logically correct, as you wish)

          I don't see any serious errors in your code, try stress-testing, maybe you can catch seg fault. You may also you -fsanitize flags to help you.

          • »
            »
            »
            »
            »
            »
            4 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks a lot for the help. It ended up being a minor mistake, i was not considering edge (u,v) and (v,u) to be same. Anyway, I ended up getting 28300 KB memory.

            submission