You are not logged in. Please login at www.codechef.com 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 http://codeforces.com/contest/474/problem/E

asked 07 Oct '14, 12:51

nilmish's gravatar image

2★nilmish
1614
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.

link

answered 07 Oct '14, 22:30

anuraganand's gravatar image

5★anuraganand
21128
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 : http://codeforces.com/contest/474/submission/8133621 BIT can be made to work for range max/min queries, with point updates.

link

answered 07 Oct '14, 23:21

amitsaharana's gravatar image

4★amitsaharana
5732611
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
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:

×146

question asked: 07 Oct '14, 12:51

question was seen: 1,904 times

last updated: 08 Oct '14, 22:45