Bungmint's blog

Help — OII 2021 Practice "Allenamento su ChinaForces"
By Bungmint, history, 3 years ago, In English

Problem Link: Link

Hi everyone.

I was just going through problems on USACO gold section trying to solve problems with difficulty tags of "Hard" and found myself stuck in the problem mentioned in the title. I was able to come up with a $$$O(nlogn)$$$ solution involving small-to-large merging technique, but I could not come up with an $$$O(n)$$$ solution that is required for the last two points. I looked up for tutorials online and came across a comment on codeforces: Thread under the OII 2021 announcement, but I still do not understand how to store the candidate minimums in an efficient way. Any help would be much appreciated :)

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

»
3 years ago, # |
← Rev. 3   Vote: I like it +13 Vote: I do not like it

Don't store the candidate minimums, just iterate over the minimums at the same time on the left and on the right (using the min stacks) until you run out of minimums on either side.

Link to the official editorial (more detailed, but in Italian), with implementation.

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

    Wow that makes so much sense. Thanks so much!

    TheScrasse ORZORZORZ

    → Reply