Thanks, it makes perfect sense — now I'm not sure why I had to go with the flow :)

If I understand unit network correctly, the network Petr proposes is not a unit network. Maybe this is the reason why flow is slower?

However, this network is pretty similar to the one in 311E - Biologist but Dinic is fast on that one. Thus I am not sure if I really have the correct explanation.

his id is just snarknews...

Mine is pretty similar (also with many facts I don't know how to prove).

For the second part instead of run length encoding, for each hole, I find the number of times it should be used (such that we have $$$m$$$ elements in total, and the maximum element is the smallest possible). And then match them greedily with similarly constructed elements for returning ants. In terms of implementation, it is just sorting and checking the balance is never negative.

A proof can be like this:

1. Binary search on the total time $$$t$$$.

2. At the $$$x$$$-th second, through hole $$$i$$$ (whose distance is $$$a_i$$$), there can either be an ant coming in or an ant coming out. For the first case, it must steal the food by the end of the $$$(x-a_i-1)$$$-th second. For the second case, it can steal the food by the end of the $$$(x+a_i)$$$-th second. We can put a ')' at the $$$(x-a_i-1)$$$-th position for the former case and put a '(' at the $$$(x+a_i)$$$-th position for the later case. We want to choose one between the '(' case and the ')' case for each second for each hole and form a bracket sequence. Then the maximum number of ants (that successfully steal some food) is equal to the maximum length valid bracket subsequence. Note that we can have multiple '(' and/or multiple ')' at the same position. These '(' and ')' can match each other.

3. Since the bracket sequence can be asymmetric, we apply the following trick. Let X be an optimal solution (a bracket sequence). We construct X' such that if in X, the $$$x$$$-th second of the $$$i$$$-th hole chooses '(', then in X', the $$$(t-x+1)$$$-th second of the $$$i$$$-th hole chooses ')'. In other words, X' is the reversed version of X. Let Y be the sum of X' and X, i.e., if X has $$$a$$$ '('s at position $$$i$$$ and X' has $$$b$$$ '('s at position $$$i$$$, then Y has $$$a+b$$$ '('s at position $$$i$$$.

4. This Y is symmetric. We know that the maximum length valid bracket subsequence of Y ($$$len_Y$$$) is at least twice as long as that of X ($$$len_X$$$). If we can also show $$$len_Y$$$ is at most $$$2len_X+1$$$, then we can just solve for the 'doubled version' and divide the answer by $$$2$$$. (Because Y is a solution of the 'doubled version' in which each hole can allow one ant coming in and one ant coming out, or two ants in the same direction.)

5. Let's consider how the brackets in Y match each other in the maximum length valid bracket subsequence of Y. By an inductive argument (from endpoints to the middle), we can assume this matching is symmetric, i.e., there is a 1-1 onto mapping between the matched pairs of '(' and ')' such that a pair at positions $$$x$$$ and $$$y$$$ is mapped to a pair at positions $$$t-y+1$$$ and $$$t-x+1$$$.

6. Another important property of the optimal solution of the original problem (not the doubled version) is that for the first half, the first to the $$$\lfloor t/2\rfloor$$$-th seconds, ants only go out from the holes and for the second half, ants only go back into the holes. (If $$$t$$$ is odd, we know nothing for the $$$((t+1)/2)$$$-th second.) Because otherwise, WLOG suppose at the $$$x$$$-th ($$$x\le t/2$$$) second, an ant go back into hole $$$i$$$. It contributes a ')' at position $$$x-a_i-1$$$ and a '(' at position $$$t-x+1+a_i$$$ to Y. But we can choose the other way, which contributes a '(' at position $$$x+a_i$$$ and ')' at position $$$t-x+1-a_i-1$$$, to match more (or equal number of) pairs. The other way is not worse because it makes the position of the contributed '(' move to the left and the position of ')' move to the right (note that $$$x\le t/2$$$). Assuming this property, we can see that for any $$$1\le x \le t/2$$$ and any hole $$$i$$$, the $$$x$$$-th second and the $$$(t-x+1)$$$-th second contributes two '('s to position $$$x+a_i$$$ and two ')'s to position $$$t-x+1-a_i-1$$$. For simplicity of argument, we assume the two '('s are created by the $$$x$$$-th second and the two ')'s are created by the $$$(t-x+1)$$$-th second. In the original version, each second can only keep one bracket from the pair. When $$$t$$$ is odd and $$$x$$$ is $$$(t+1)/2$$$, the $$$x$$$-th second contributes a ')' to position $$$x-a_i-1$$$ and a '(' to position $$$x+a_i$$$.

7. We first consider the easy case -- $$$t$$$ is even. Each pair of '('s are matched to two ')'s. The two ')'s may or may not be in the same pair. If we consider the pairs as vertices and the matches as edges, we have a bipartite graph consists of cycles. For each cycle, we erase the even-numbered edges (or odd-numbered edges). Exactly half of the edges remain. The remaining edges matches exactly one bracket from each pair. In other words, the remaining edges and the brackets matched by them form an answer of the original problem. $$$len_X\ge len_Y/2$$$.

8. If $$$t$$$ is odd, the graph consists of paths and cycles. We still want to erase some edges and their corresponding brackets such that each second of each hole keeps only $$$1$$$ bracket. For each cycle, we can do the same thing. For each path, it must connects a bracket ('(' or ')') created by some hole $$$i$$$ at the $$$((t+1)/2)$$$-th second and a bracket ('(' or ')') created by some hole $$$j$$$ at the $$$((t+1)/2)$$$-th second. If $$$i\neq j$$$, because the matching is symmetric, we can find the mirror image of this path. We keep odd-numbered edges in the original path and even-numbered edges in the mirror path. Then exactly one bracket created by the $$$i$$$-th hole at the $$$((t+1)/2)$$$-th second is kept. The same holds for $$$j$$$. (Thus, it is possible to create the remaining brackets from the original problem.) The number of edges in these two paths are cut by exactly half. (This case actually contains two cases -- when both paths has an endpoint of ')' an endpoint of '(', and when one path has two endpoints of ')' and the other has two endpoints of '('. But the same argument applies to both cases.) If $$$i=j$$$, the mirror of the path is itself and this path has an odd length. We can't keep more than half of the edges in this path because we can keep only one the two endpoints of this path (because they are both created by the $$$i$$$-th hole at the $$$((t+1)/2)$$$-th second). We collect this kind of paths and pair these paths up. We modify each pair of such paths so that they become two different paths that are the mirror image of each other, i.e., the previous case. (This is always possible because at the middle of each such path, we have a pair of '(' and ')' whose positions are symmetric. The two pairs from two such paths can be exchanged.) Then at most $$$1$$$ such path has no partner. If its length is $$$l$$$, we can only keep $$$(l-1)/2$$$ edges. This is the only case where we can't keep exactly half of the edges. We have $$$len_X\ge (len_Y-1)/2$$$.

9. In either case (7 or 8), $$$len_X\in [(len_Y-1)/2, len_Y/2]$$$. $$$len_X=\lfloor len_Y/2\rfloor$$$.

Thanks! Can you elaborate how to solve the case when there are only two neighbouring arrays of size $$$c$$$? For some reason I thought this was not possible.