OneClickAC's blog

Mystery with segment trees and problem 867 E
By OneClickAC, 7 years ago, In English

Hello CF community,

In this blog, I look to ask up two things which are somewhat related to my approach for yesterday's Div2 E problem Buy Low Sell High. But before asking about that I need to ask something about segment trees.

My approach for yesterday's problem - First I took all the stock values in a pair array with second index storing actual index. I sorted the array so as to get the least to highest prices keeping lowest index in mind first.

I built a segment tree (max query) then.

The basic idea was to now iterate over the pair array whose first index gives me the stock value (say val) and second index gives actual position (pos) of that stock in the real array. The next thing to do is find the maximum value of stock in array (using segment tree) from pos + 1 to n , say max. Since there is a possibility that there can be multiple position with value max in the array, I took up the closest one to pos. For this, I simply stored all the values of position a particular number in a set and just found the upper bound of pos. If that max value is greater than stock value, cool.. update it, add the difference to answer and keep moving, otherwise just simply continue.

The first submission I made got a runtime error and I wasn't able to understand why it happened. After the contest while trying to upsolve or possibly find out the error, what I just did was change all 2node + 1 to 2node and 2node + 2 to 2node + 1 in my segment tree implementation. Surprisingly the problem now got solved.

So my two questions for this problem and particularly my situation are that why the problem got solved with that little change or in-fact why I got that problem when everything was basically fine and same in my update and query function. Was it something related to memory issues?

Second obviously is why my algorithm is wrong as I am still getting wrong answer?

Problem Link - http://codeforces.me/problemset/problem/867/E

My runtime error submission - http://codeforces.me/contest/867/submission/30885275

No runtime error but WA submission - http://codeforces.me/contest/867/submission/30910560

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help me out?

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Two children of node u are 2u and 2u + 1, not 2u + 1 and 2u + 2. Then the maximum elements for segment tree is 4n, if you did right. That why you got RE.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Also try this test:

    Input:
4
1 7 2 9
Output:
13
    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I thought of the same thing about segment tree related problem, just wanted to confirm.. Thanks :)

    → Reply