Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

NeoYL's blog

By NeoYL, history, 12 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 second episode of this "note" series. I will write notes on problems (normally around 2400-ish problems), 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 3), 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

Problem summary:

Given a set of edges connecting two nodes each, and we must take at least one node from each edge's end.

Let the taken nodes to be $$$a_{1}, a_{2}, ..., a_{p}$$$ in sorted order.

Maximize $$$\min_{1 \leq i \leq p-1}(|a_{i}-a_{i+1}|)$$$. If $$$p=1$$$, the value would be $$$N$$$.

Again, attempt the problem yourself before continue reading this blog.

Prerequisites
If you don't know the second tag in the Prerequisites
first observation
second observation
optimization

AC code

Code

Comment on this problem and my feelings:

Feelings

Tips for implementation:

Tips

Hope you guys learnt something from this blog.

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

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Also, I submitted like 7 times like a dumbass before ACing.

is that the reason you ACed 3 times

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hahaha, yea I removed some useless code and some weird formatting

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow, how are you solving 2500s by yourself with such a huge rating gap?

  • »
    »
    12 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Ehhh, I just don't do rounds because the contest time is like until 12.30 midnight in my country. Also, you can also notice that my problems solved are mostly dp/greedy/graph. My maths is quite poor (I will most likely miss that problem if its a maths problem)

»
12 months ago, # |
  Vote: I like it +45 Vote: I do not like it

There is one sentence that is so wrong that I have to warn everyone reading this blog to not accidentally absorb this to their problem solving strategies: Making incorrect pruning is so much more damaging than not finding the correct solution.

"When you see a problem that maximize minimum ... or minimize maximum ... , it's 99.999% binary search.".

Maximise minimize is such a common keyword pairs in so many context that it is not a good idea to just automatically associate it to binary search.

In the not so bad case, you would have taken an extra time cost of log for no reason. In rare cases, you will not explore other approaches at all.

Here are a few kinds of solutions to problems with these keywords.

  1. Basic sufficient condition = necessary condition. Guess that the min-max is achieved by some formula and prove it directly.

  2. Sweepline: Typically done in DSU-like problems. Example problem: Given an undirected graph where each edge has weight. calculate for $$$q$$$ pairs, the minimum of maximum cost of path between the points. A direct sweep line used a basic dsu that also maintains the queries. You could do binary search but you need persistent DSU. Another approach is of course just construct minimal spanning tree.

  3. DP or Greedy. DP is self explanatory. One type of greedy is the following: repeatedly take all actions that does not increase the min-max. When no further action can be taken, take an action that increase the min-max least. This needs many more assumptions to hold true.

and so much more

This is not directed to the author. It could be beneficial to make simple rules that are correct at least some of the time, especially if it seems to be always true for your situation — you can correct it later when necessary. Yet, this is different when published. This is simply a caution for readers of different ratings.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, you are correct. I actually got this sentence from a GM some time ago. A very obvious type of problem will also be DP and I personally saw one of them before writing this blog. While this is true, I have only seen this type of problem without binary search once (that's why I said that sentence). Now I changed my mind about it, thanks for pointing it out.