Hi! In this post I'll be sharing an interesting idea of mine on solving this problem https://mirror.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://mirror.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.