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


Codeforces Round 271 Problem E Pillars

How can we solve the problem using BIT ? After figuring out the basic dp we need a data structure to find best[i]=max(best[j])+1 with j<i,|h[j]-h[i]|>= D. We can find this using segment tree. Can we find this maximum using BIT ?

Link to the problem

asked 07 Oct '14, 12:51

nilmish's gravatar image

accept rate: 0%

edited 07 Oct '14, 12:52

BIT can be used for finding prefix maximum. So, we can use two BITs to find this maximum. If we remove the absolute function, we get two conditions h[j] <= h[i] - d or h[j] >= h[i] + d.

  • For first condition, we can directly use BIT on compressed values in ascending order
  • For second condition, we can use BIT on compressed values in descending order.

Now both the queries are in the form of prefix query.


answered 07 Oct '14, 22:30

anuraganand's gravatar image

accept rate: 21%

A single BIT can be used for general range max/min queries, see my submission below.

(07 Oct '14, 23:23) amitsaharana4★

Yes, it is possible: see for example this : BIT can be made to work for range max/min queries, with point updates.


answered 07 Oct '14, 23:21

amitsaharana's gravatar image

accept rate: 0%

edited 07 Oct '14, 23:26

I've read the problem, but haven't read your code properly. I'm worried by your generalization... As I see it, BIT can't be used for general Range Minimum Queries. It works for this problem because you only want prefix/suffix maximums, and more importantly, the updates are only increases.

ie, using BIT, you can find: 1. Prefix (or Suffix) Maximums, under the condition that the updates are only increases. ie. any update to A[i] can only increase it's value. 2. Prefix (or Suffix) Minimums, under the condition that the updates are only decreases

Can you do anything more general than this?

(08 Oct '14, 22:45) meteora6★
toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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:


question asked: 07 Oct '14, 12:51

question was seen: 1,922 times

last updated: 08 Oct '14, 22:45