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

×

Can someone help me debug my Segment Tree(lazy propagation)?

Hi!

I've been trying to solve this problem from CF lately: Circular RMQ

I implemented a Segment Tree and used lazy propogation for solving this problem. But two different implementations I've made both fail on the 5th case. The 1st one failed to correctly answer the 30th query, the second, even though answers the 30th query correctly(local manual testing) doesn't answer the 25th query correctly.

My code is here. Does anyone know how I can debug such a data structure easily, as all test cases(small ones) seem to get answered correctly. Any clues/ideas would be appreciated.

Thanks and regards!

NibNalin

asked 27 Aug '15, 17:40

nibnalin's gravatar image

6★nibnalin
1611515
accept rate: 0%


Try negative values for the array, in particular -1 (they are within the constraints).

It's a bad bad idea to have a valid value as a signal for an empty segment.

link

answered 27 Aug '15, 20:37

ceilks's gravatar image

7★ceilks
1.8k9
accept rate: 36%

Hello, thans for looking into this, but this doesn't seem to resolve the issue, even though your point is entirely valid: http://codeforces.com/contest/52/submission/12721828

(27 Aug '15, 21:49) nibnalin6★
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,669
×624
×155
×41

question asked: 27 Aug '15, 17:40

question was seen: 985 times

last updated: 27 Aug '15, 21:49