Bungmint's blog

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 :)

Full text and comments »

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

By Bungmint, history, 3 years ago, In English

I was trying to solve this problem on CodeChef, QCHEF, using Mo's algorithm and realized it is not so simple to come up with a data structure that can save previous results, so that you can simply obtain the result after deletion. I looked up how to maintain previous results, and found this nice comment, link, where it describes this abstract notion on how one could have one function, snapshot(), for saving the current results, and another function, rollback() to go back to the previous state. I tried to implement this, code below, but it failed miserably. Any help would be appreciated.

UPD: Apparently I had a typo in one of the add functions, and fixing that immediately solved the problem lol.

Code

Full text and comments »

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