You are not logged in. Please login at www.codechef.com to post your questions!

×

Wrong Answer in SPOJ Problem KQUERY2

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

asked 18 Jun '17, 00:18

mayank12559's gravatar image

5★mayank12559
936
accept rate: 0%

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

(18 Jun '17, 00:48) vijju123 ♦♦5★

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 :P Often a Java solution might timeout on SPOJ but the same algorithm will pass when implemented in C/C++.

Hope this helps :)

link

answered 18 Jun '17, 15:43

meooow's gravatar image

6★meooow ♦
7.3k720
accept rate: 48%

edited 19 Jun '17, 18:58

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){}.

(18 Jun '17, 16:15) mayank125595★
4

SPOJ is too biased to C++ :P

(18 Jun '17, 16:38) hikarico5★

@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 :)

(19 Jun '17, 18:56) meooow ♦6★
1

@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.

(19 Jun '17, 20:37) mayank125595★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,768
×1,359
×1,137
×856
×711
×74

question asked: 18 Jun '17, 00:18

question was seen: 599 times

last updated: 19 Jun '17, 20:37