ayushrocker92's blog

Help
By ayushrocker92, 10 years ago, In English

i have tried understanding the editorial of problem http://mirror.codeforces.com/contest/474/problem/E and understood some concepts but some of then are not clear.

Like how do you implement segment tree in this as it would require an array of size of max(h[i])

u can do it by normalization but then how could i get maximum dp value computed so far among all elements in an array having values between h[i]-d to h[i]+d in log(n)

Thanx

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You firstly normalize the values, and then you use binary search on the normalized values to find the bounds on the intervals you query for. Since binary search is first and query is afterwards you get roughly log N + log N = 2 * log N = O(log N)

I personally prefer just coding segment tree with dynamic memory, but it's not necessary.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if i normalize the values then what would be the normalized value of h[i]-d and h[i]+d . Can u please illustrate the procedure with an example.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      You can't simply subtract or add d; that's why you need to do a binary search.

      Example:

      n: 6, d: 2
Normalized : 1  2  3  6   4  5
Real       : 2  4  5  12  6  7

      When we come to 4th index (from zero), we would basically look for the range 1-4 and 8-12 if we were working on the real array. Since we're working on the normalized array, we need to do a binary search in the 1-3 range and 5-6 range. For the 1-3 range we will get 2; for the 5-6 range, we'll get 6. Then we will query 1-2 and 6-6 ranges on the segment tree.

      → Reply