Wrong Answer in SPOJ Problem KQUERY2

general
, , , , ,
1

I am getting Wrong Answer in SPOJ Problem KQUERY2. Link to the problem is : KQUERY2

I am creating BST in every Node of Segment Tree. Can anyone help me with this question? Link to my solution : Solution

2

Ran it on as many inputs i could think of :confused: . It must be a slimy edge case…

3

Hey @mayank12559, there were 2 bugs in your solution. The first is that you are deleting a[ind] at each update, but you are not updating the value of a[ind] itself. So for every update at any index, you are always attempting to delete the original value at that index.

The second bug is trickier. In your delete operation, you are replacing the node to be deleted with the node of next largest value by picking it from the right subtree by setting root.val = getSuc(root.right), but you are forgetting that you need to copy the count too. After you fix this, you will face another issue. After you have cloned the next largest node into the current one, and you call root.right = delete(root.right,root.val), the next largest node will only be deleted if it has count = 1! To overcome this, an extra flag can be used that indicated whether the node should be deleted regardless of its count.

I have fixed these bugs here. Unfortunately I am getting TLE on submission, so I cannot be sure if there are other bugs, but it’s unlikely. The TLE may be due to the fact that you are not balancing your BSTs. You can look into self-balancing BSTs such as treap, red-black tree, AVL tree, etc. The TLE may also be simply because it’s SPOJ, and SPOJ is not kind to slow languages :stuck_out_tongue: Often a Java solution might timeout on SPOJ but the same algorithm will pass when implemented in C/C++.

Hope this helps :slight_smile:

3 Likes
4

Hello @meooow, Thank you for the reply. I got the first bug, it was really a silly mistake. But I am not able to understand the second bug. Will that not be handle by the backtrack? Moreover changes made by you in getSuc() functions seems incorrect. You are getting TLE because I guess now the solution had stuck in the infinite loop.
Please check the code of getSuc() function. There is no break condition for While(true){}.

5

SPOJ is too biased to C++ :stuck_out_tongue:

4 Likes
6

@mayank12559, I was unable to understand your delete function properly earlier, sorry about that. The backtrack does maintain the sum and count. I have updated the answer with the real bug :slight_smile:

7

@meooow Thank you for correcting the code. Now I got the second bug. Yes, it was tricky one. But you were able to solve it so easily. I have implemented the balanced BST also, but still getting the TLE. @hikarico is right I guess. “SPOJ is too biased to c++ :P.” Anyways thank you once again for correcting my mistakes.

1 Like