Educational Codeforces Round #105 1D Sokoban - Binary Search


Classic binary search problem. We only consider the positive part. The negative part can be similar.

Let's consider to push boxes to $b_i$. We binary search $a$ with $b_i$ to find the largest $j$ so that $a_j\leq b_i$.

If there is a box at $b_i$. Which means $a_j=b_i$. Then we plus one to the basic result (base_ans++). No need for other things because push all boxes to here can't be the best solution.

If there is no box at $b_i$. Which means $a_j<b_i$. Then for all boxes between 0 and $a_j$, we push it to $b_i, b_i-1,b_i-2,...$. And then we binary search $b$ with the number of boxes between 0 and $a_j$ (Which is $j+1$). Find the smallest $k$ so that $b_k\geq j+1$. So the result of pushing all boxes to $b_i$ is $i-k+1+base\_ans$.

Enumerate $i$. We pick the maximum of results.


Submission #114380700 - Codeforces
Codeforces. Programming competitions and contests, programming community


Convert the negative part to the positive. And run the solution again. It can make the implementation easier.

Show Comments
DigitalOcean Referral Badge