Pankin's blog

By Pankin, 4 years ago, translation, In English

Hi! In this post I'll be sharing an interesting idea of mine on solving this problem https://codeforces.com/contest/1101/problem/F, that can be used to solve some other problems as well.

If any of you have seen this approach before, or know other problems that can be solved using it, please share them below.

Binary search solution

In the problem the most obvious solution is to binary search $$$V$$$ by checking a possible answer with a greedy algorithm. This solution has $$$O(n$$$ $$$m$$$ $$$log_2$$$ $$$10^{18})$$$ complexity, which is too much, but we can optimize it a little bit so it could fit into the time limit.

Greedy optimization

Let's assume that we checked i tracks for a specific $$$V$$$ and the truck number $$$i$$$ couldn't reach his city for that $$$V$$$. Obviously we don't need to check the tracks coming after $$$i$$$, the answer will be more than $$$V$$$ and we will have to increase the left border of our current segment in the binary search. Therefore, all the values we will check later will be bigger, so we won't have to check any trucks with numbers less than $$$i$$$, as they already managed to get to their destination with a smaller $$$V$$$. After that we will start checking the trucks starting from $$$i$$$ and so on.

This is an optimization, but it doesn't change the complexity. If the answer is very small, each time we will check all the trucks and all of them will fit, so every iteration of the binary search will still work in $$$O(nm)$$$. However, if the answer was very big, we would always increase the left border of the binary search segment, deleting the truck number $$$i$$$ or checking $$$V$$$ for this truck only. In that specific case the complexity would be $$$O(n$$$ $$$m + n$$$ $$$ log_2 $$$ $$$10^{18})$$$. Now let's change the way we search for the correct answer, so that decreasing the right border of the segment would work a little faster, but increasing the left border — a little slower.

Make it less binary

Usually when we use binary search, we split the segment into two subsegments of the same length, check the middle and continue in one of the halfes depending on the result. Now instead of splitting the segment in $$$1:1$$$ ratio, let's split it in some $$$1:D$$$ ratio, where $$$D$$$ is a constant, that we will define later. If we do it this way, the segment will reach its left border in $$$log_{D + 1}$$$ iterations, and the right border in $$$log_{(D + 1) / D}$$$ iterations. This is exactly what we need, to speed up the proccess of decreasing the right border by slowing down the way we increase the left one. This way we can find a balance between the two. The complexity will be $$$O(n$$$ $$$ m $$$ $$$ log_{D + 1}$$$ $$$ 10^{18} + n$$$ $$$ log_{(D + 1) / D}$$$ $$$ 10^{18})$$$. If we pick $$$D$$$ to be about $$$20000$$$, both parts will take about the same amount of operations for maximum $$$n$$$ and $$$m$$$. Here is my submission where you can see how it works: https://codeforces.com/contest/1101/submission/77055660

If, on the other hand, increasing the left border would have worked slower than decreasing the right one, we could have split the segment in some $$$D:1$$$ ratio instead. This is an interesting trick that can be used to solve other problems with these conditions. What do you think about it?

Please share your ideas and similar problems below!

UPD: It turns out, the optmal $$$D$$$ is such that $$$D \ln D = K$$$, where $$$K$$$ is the ratio between the two parts of binary search. It's optimal when both parts take about as much time. Knowing that here's some mathematical proof:

$$$K = \ln(D+1)/(\ln(D+1)-\ln D) = 1 + \ln(D) * ( 1/(\ln(D+1) - \ln(D)) = 1 + \ln(D) * (D + O(1))$$$

This fact was found thanks to gepardo.

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

»
4 years ago, # |
  Vote: I like it +43 Vote: I do not like it

Superb Quarantine feature i think :)

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

OH MY GOD

»
4 years ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

Is there a way to pre-calculate fast on each test what type of division (D:1 or 1:D) will be useful?

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

    Just check what part of binary search (going left or going right) works slower and if it's going left — 1:D, otherwise D:1. Or if you're trying to find the right D constant for a specific test you can use ternary search and insert it into the complexity formula when checking a speciefic value, but I personally didn't try going to such extremes.

»
4 years ago, # |
Rev. 2   Vote: I like it +32 Vote: I do not like it

Well it's an interesting trick but I don't see where could we practically use it, when we have Blogewoosh #6. One can argue that what you described is deterministic in comparison to the trick mentioned by Radewoosh, but those are all benefits I can think of.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Yeah, you're right. Both techniques do the same thing, this one can serve as a determined alternative. Now people can just choose a trick they like from the two)

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Pretty sure the math for the optimal $$$D$$$ is wrong. When you take the ration $$$K$$$, you forgot the factor $$$m$$$, since that factor only appears in the first term, and not in the second.

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

That's amazing, thanks for sharing.

However, i am not sure how to pick a reasonable D in contest, like i have to solve this D*lnD=K equation? or there exists a rule of thumb that i can quickly use