NeoYL's blog

By NeoYL, history, 2 months ago, In English

This is my personal note and might be some kind of user editorial/learning material for some people!

This is the first episode of this "note" series. I will write notes on problems (normally around 2400-ish problems), which are completely solved without looking at the editorial, that are both interesting and educational. I normally will spend a few hours on each problem so please be patient when reading the blog. The problem on these notes should give a very interesting solution and will likely be optimizations problems (I feel like these problems have an IOI-style, which requires you to find some incomplete solution first then find the final solution using it).

If you want to motivate me to write a continuation (aka note 2), a significant upvote from you would be well appreciated! If I received lots of downvotes (because I'm also spending a lot of time to write this and to learn latex only to express my ideas accurately to you guys), I'm probably not gonna continuing writing these blogs.

Problem link: ABC133F

Try to solve the task independently before continuing the blog.

Hint
Incomplete solution

That reduces the problem to $$$O(N ^ 2)$$$, lets optimize it!

optimization used

This allows an $$$O(N log N)$$$ solution

AC code link

Code

Feel free to ask anything about the task. I will try to respond them if I am free.

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

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by NeoYL (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by NeoYL (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

That's a great initiative, good luck!

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Try to solve this problem when the updates are permanent btw. Quite an interesting problem.

spoiler
  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    ?
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Time Complexity
      About DS involved

      I didn't find any judge for this. I tested my solution by reversing the updates in this version of the problem.