Kickstart: Ants on a stick

This is a twist of the well known ant problem, whereby we can view ants as walking through each other when they meet. In this case, we do not seek the latest time for an ant to fall off the stick, instead we want the order by which they fall off.

The first thing I noticed was that one of the leftmost or rightmost ants, $l$ and $r$ respectively, will fall off first. This is because they will either walk straight off, or they will walk into some ant and then walk towards the end of the stick. Now we just need to decide which of the two falls off first. 

Since, we can view the ants as walking past each other when meeting, we know that the $n$ ants fall off the stick at times $t(1),t(2),...,t(n)$, where $t(i)$ is the time that the $i$th ant falls off the stick when it is alone on the stick. Then the first ant will fall off at time $\min_{i}\{t(i)\}$. Let $x$ be the ant which has this minimum value of $t(x)$. If $x$ and $l$ are facing each other, then $l$ will fall off first since $x$ and $l$ will meet at some time, forcing $l$ to fall off the stick first. There are other cases to examine, but we have now made the main observations.

Binary string

 The problem link is here: https://codeforces.com/contest/1680/problem/C.

My approach and thoughts:

Let b start with $x$ zeros. We simplify the problem to only have deletions from the left side.

Let $s[i]$ denote the number of $1'$s in positions $[0,i)$. We want to delete prefix $[0,i)$ which minimises $\max\{x-(i-s[i]), s[i]\}$.

Say prefix $[0,i)$ meets these conditions, then we delete it. Let $b'$ be the remaining binary string but reversed, where the prefix array $s$ is recomputed as $s'$. We apply the exact same method to $b'$, taking into account that we have already deleted $s[i]$ $1$'s, so the cost after deletion of prefix $[0,j)$ will be $\max\{x-(i-s[i])-(j-s'[j]), s[i] + s[j]\}$. We can repeat the same process starting from deleting the right side of $b$ and then the left.

However, this fails on input $1000110110001$. In this case it is not the case that greedily deleting the prefix which yields the lowest score is best. This is because we may use our deletions inefficiently if we restrict ourselves first to the prefix and then the suffix. In some cases, it is best to delete a bit from both sides.

So we try a binary search over the set of possible costs $[0,x]$ since if we can achieve a cost of $c$, we can certainly achieve a higher cost. The problem then becomes: how can we efficiently check if a cost of $c$ can be achieved? For a cost of $c$, we need our remaining string to have $\leq c$ zeros in it and for this string to be reached with $\leq c$ deletions of ones. Therefore, we look at the substrings with $i$ ones deleted from the left and $c-i$ deleted from the right for every $0\leq i\leq c$ and check that for at least one of them, the number of zeros is $\leq c$.

If we pre-compute an array $p$, where $p[i]$ is the position of the $i$th one from the left, we can find the substring with $i$ ones deleted from the left and $c-i$ ones from the right between positions $p[i+1]$ and $p[c-i-1]$. Also pre-computing array $z$, where $z[i]$ is the number of zeros in positions $[0,i)$, we can check in $O(1)$ time if the substring $[p[i+1], p[c-i-1]]$ has $\leq c$ zeros by checking $z[p[c-i]]-z[p[i]]\leq c$. Thus we have a $O(n\log{x})$ solution since we need $O(n)$ time for this pre-computation of arrays $p$ and $z$, and then perform $O(\log{x})$ binary search rounds each taking $O(n)$ time.

To recap, the main observations used are that binary search is an option and that by pre-computing relevant information about the ones and zeros, we can determine in $O(n)$ time if $b$ can have cost $\leq c$. Perhaps there is a faster solution although I am unaware of it.