Chasing Rats

Subtask 1

Do a graph search algorithm with state (me, rat position) for every query. \(O(QM^2)\).

Subtask 2

The only states that matter are those where me and the rat are adjacent. There are exactly \(2M\) such states. However, our transitions are a little different:

• Move into the rat, chasing it away
• Walk to some other node adjacent to the rat without chasing it

Let's build a new graph called the \(\textit{rat graph}\), where every node is a pair (me, rat), representing our DP. Unfortunately, this graph will contain \(O(M^2)\) edges because of the second transition (imagine a single high-degree node).

The white edges are the edges in the original graph, and the blue ones are the ones in the rat graph.

However, we can realize that if we can go from \(a \rightarrow b\) and \(b \rightarrow c\), then we can go \(a \rightarrow c\). Basically, the neighbours will be partitioned into groups where every node can go to every other node. A common trick when faced with such subgraphs (cliques) is to model them via a spanning tree. We will introduce a single node for each group called the \(\textit{leader}\), and everything in the group can to and from said node. For the above graph:

If we add more neighbours:

With this, we have a linear amount of edges and states, so we can answer each query in \(O(M)\) time. Building this graph naively takes \(O(M^2)\) time, so our complexity becomes \(O(MQ+M^2)\).

Subtask 3

Note: this is the only subtask where using block-cut trees is necessary, so you can skip that part if you want to (although it's nice to be able to solve the CSES task).

Let's speed up building the rat graph to \(O(M \deg_{max}^2 \log(M))\). The slow part is currently finding how to connect leader nodes. We will speed this up by being able to check in \(O(\log(M))\) (or \(O(deg_{max})\)) time whether two nodes belong to the same leader group. The exact query we're answering is "if we remove the rat node, is there still a path from node \(a\) to node \(b\)"? This task is classical, and can be found in cses. The idea is to convert our graph into a tree. The solution to this subproblem is as follows. Note that there unfortunately aren't many good tutorials online about this (in fact, I never really understood biconnected components before solving this problem).

We say that a vertex is a cut vertex (also known as articulation point) if removing it disconnects the graph (increases the number of connected components). Note that the rat is not on a cut vertex, then all its neighbours trivially have the same leader.
One nice way to model cut vertices is by biconnected components. We say that two edges are related if there exists a simple cycle (no repeated vertices) containing both edges. Let \(a\) ~ \(b\) denote \(a\) and \(b\) being related. It turns out that this is an equivalence relation, meaning that if \(a\) ~ \(b\) and \(b\) ~ \(c\), then \(a\) ~ \(c\). Classifying edges based on this partitions the graph into so-called biconnected components.

In the following image, every edge with the same color is in the same biconnected component.

Some websites (like wikipedia) will have drawings where the biconnected components are placed "on the nodes":

However, for this task (and in general?) it's more productive to think of each edge as being in some BCC (biconnected component). Now, how can we check if removing some cut vertex allows us to still go from \(a\) to \(b\)? I have drawn the graph again, marking the cut vertices orange:

We can realize that removing some cut vertex splits the graph into multiple parts (by definition), and our problem is now to find out if node \(a\) and \(b\) are in the same part of the graph after the split. Let's create the following tree: every cut vertex becomes a node and every biconnected component becomes a node. We connect then every pair of cut vertex and BCC (not cut vertex with cut vertex or BCC with BCC) if they share an edge in the original graph:

Take a second to convince yourself of how the two graphs relate: each BCC has become a node with the same color. This new graph has many nice properties: it is bipartite, with the left half being cut vertices, and it is a tree, and carries all the information we need to answer our queries. Take a moment to convince yourself that solving the "remove vertex \(x\), is \(a\) and \(b\) still connected?" on this tree solves the problem on the original graph. This graph is known as the \(\textit{block-cut tree}\) of our graph.

Now, we have a tree, and we want to answer "if remove vertex \(x\), is \(a\) and \(b\) still connected?". This can done in \(O(deg(x))\) in the following way: use the euler to be able to check in \(O(1)\) if some vertex is an ancestor of another. Iterate through all the edges of \(x\) and find which subtree \(a\) and \(b\) belong to. If they do not belong to any, they are in the parent "subtree". Then, we simply need to check if they are in the same subtree.

In this example, \(a\) and \(b\) are in different subtrees, so if we remove the rat node, there is no path between them anymore.

So our algorithm is: first, find all biconnected components and cut vertices. Second, construct the block cut tree. Third, do an euler tour of the block cut tree. There are some special cases when answering the queries, so take care there.

References:

• A cses problem asking the subqueries we have cses
• A lecture on how to find biconnected components via the DFS tree https://www.youtube.com/watch?v=K44iikEue4Y
• More on BCC and the block-cut tree https://usaco.guide/adv/BCC-2CC?lang=cpp
• https://cp-algorithms.com/graph/lca_binary_lifting.html on using the euler tour to implement the "is ancestor" function.

To actually solve the cses problem, we need to answer queries in \(O(\log(M))\) instead. To do this, we can check if \(a\) and \(b\) are in the subtree of the rat. If they are not the same (i.e., one in the subtree, one not), then the answer is no. If they are both above, the answer is yes. Otherwise, we will use binary lifting to get them to the node just below the rat and check if they are equal.

Note that we don't need the insight that we can sparsify the rat graph using "leader nodes" to solve this subtask.

Subtask 4

Let's extend the ideas of the previous subtask. In fact, to build the rat graph, we don't need to naively query which neighbours can reach each other: the BCC's form the exact division into groups with leaders we're constructing. Now, we can construct the graph in \(O(M)\) time, and can then simply do a graph traversal in it to answer query.
Note that your BCC implementation also needs to compute which BCC each edge belongs to.

Subtask 5

\(S\) and \(R\) are the same for all queries. Let's first build the rat graph in \(O(M)\) time. Then, find out which states (me, rat) can be reached from the start. Using these, do a multisource BFS in the rat graph to find which \(T\) vertices can be reached. With this, we can precompute which \(T\) have answer "yes".

Subtask 6

Do a multisource BFS from \(T\), where we start with every node adjacent to it. Doing this, we can compute all pairs (me, rat) that lead into the goal. Now, our subproblem is "if we start at \(S\), which "side" of \(R\) do we end up on?". Any node suffices. To solve this, take any spanning tree of the graph. If the starting position is not in the subtree of the rat, the parent of the rat suffices. Otherwise, binary lift the starting position to one node below the rat.

Subtask 7

From subtask 6, we can in \(O(\log(M))\) time reach a state (me, rat) where me and rat are adjacent. So the only slow part is asking "can (me, rat) reach any state (*, \(T\))?" (* here represents any node). The authors believe that it might be possible to solve this in \(O(M\log(M))\) by considering the block-cut tree carefully. However, we didn't manage to actually solve it using this. Instead, we consider the rat graph and solve the problem "is there a path from node \(a\) to node \(b\)"? Note that this is hard to answer naively: we want to answer "is there any (me, \(T\)) reachable?". But there can be many valid me for a given \(T\). To make it a single node reachability query, for every node we add a "target node". Every pair (me, \(T\)) can go to the target node for \(T\). We do this for every possible node \(T\). Also note that this edge must be one-way, otherwise we mess up the rat graph.

Now, we have the problem "given a directed graph, is there a path from \(a\) to \(b\)?".
It is an open problem to solve this in better than \(O(NM)\) time, so we will settle for \(O(\frac{NM}{64})\) using bitsets.

There is another CSES problem for this exact subproblem. To solve this problem, we first need to find all SCC's (strongly connected components) in the rat graph, and compress each one into a single node. We then end up with a DAG (directed acyclic graph). We will topologically sort this graph and then use bitsets. In the beginning, bitsets[u][u] = 1. To update along an edge \(u \rightarrow v\), we do bitsets[u] |= bitsets[v].

How big can the rat graph be? It can be shown that if \(N=M\), then it has at most \(3N\) nodes and \(4N\) edges, which easily passes using bitsets if \(N=M=25000\).

Subtask 8

The previous solution uses way to much memory. We will use trick number 1 from this codeforces article.

However, doing this exactly as described kind of sucks. We will basically get a cache miss every time we do a lookup. Instead, we will do it in bigger groups so we process lots of nodes sequentially. The judge solution processes \(680*64=43520\) target nodes per round. The judge solution uses SIMD for maximum performance, but bitsets are fast enough (the generated assembly is very similar).

Note in CSES reachability queries: don't use your runtime on this problem as a proxy for runtime on chasing rats. Tl;dr: the optimal number of bits per iteration is different on Kattis and CSES.
Full version: I have the fastest solution, and the optimal number of bits per iteration is about 256, while on modern hardware, it would be pretty much optimal to do everything in one iteration if memory would allow it. My best guess is that if we increase the number of bits per iteration, we exceed cache size, and the RAM is too slow to keep up with the CPU.

Eating Chocolate

Let us first consider how the game will play out on a single chocolate rectangle. We can simulate it by greedily picking between slicing in W or H direction depending on which one is best for us right now:

int W = 123, H = 321; // original width and height of chocolate
vector<int> eat;
while (W * H > 1) {
    if ((W/2)*H < W*(H/2)) swap(W, H);
    eat.push_back((W/2)*H);
    W = (W+1) / 2; 
}
eat.push_back(1);

In that case, we can simply simulate the game according to the code above, and then they will eat every other thing out of the "eat" vector. Python code:

olle = sum(eat[i] for i in range(0, n, 2))
lisa = sum(eat[i] for i in range(1, n, 2))
ans = abs(olle - lisa)

This method also extends into solving the problem for an arbitrary number of chocolate cakes: We can simulate each of them separately, then merge all "eat" vectors, sort them in reverse order, and we will once again have a vector where we can look at the difference between sum of things on even indices and sum of things on odd indices.

How do we handle the fact that there are lots of copies?

Imagine the case where there are 2 identical pieces of chocolate, A and B. If at some move Lisa chooses cake A and eats a certain part of it, Olle can perform the identical move on cake B. In the end, they will have eaten an identical amount of chocolate.

In fact, any even number of identical copies will "cancel out" in this way.

So for the game, an even number of chocolate cakes will not have any impact on the resulting difference. Implementation wise, we still want to be able to handle throwing out a chocolate that has an even number of copies. So for even k, we will add just two copies (and for odd k, we will add just one copy).

How do we handle throwing chocolate in the trash?

The difficult part of this problem is to see what happens to the difference when we remove one cake from the game.

An easy way to solve it is to iterate over all possible things to remove, remove one object of that type, and then sort together all lists except for the one belonging to that object. However, this is too slow.

To speed it up, the main idea is to try to delete things after we already simulated.

First, simulate everything as before. Sort together the lists, and keep track of which chocolate cake every element comes from. In the image, this is done through color: Everything that comes from cake A is colored red.

We notice that the person who goes first will always eat at least as much as the person who goes second, so we know that the difference will always be sum(first person eats) - sum(second person eats). Let's flip the sign of everything the second person eats, and create a prefix sum of this (see image above).

Now, how can we use this info to remove something?

In order to ask "What is the result if we remove all the blue colored things?", we realise that every element that has an even number of blue things before it will count the same as before (because the same person eats it), whereas every element that has an odd number of blue things before it will be negated (now, the opposite person eats this element).

So we can iterate over all blue elements in our list, and find the current sum of things between them (by taking prefix_sum[next_blue_thing-1] - prefix_sum[this_blue_thing]). If we have gone through an even number of blue things, we add the sum directly, and if we have gone through an odd number, we instead subtract the sum.

We can iterate over all colors, and then do this. Since every element has one color, we will in total look at each element once, so the time complexity of this part is O(#elements) (which is faster than the bottleneck of sorting all elements).

Five Rats at Gustav's

The structure of the manholes and the pipes form a tree structure. Let us always consider the tree to be rooted in manhole 0.

To simplify the problem we can remove some nodes from the tree. We can remove the rats that lie in the subtree of some other rat. This is because a rat that is in the subtree of another rat will go to the same nodes, but reach them later. We can also remove nodes that are further than \(T\) seconds from the root, and finally we can remove all nodes that do not have a rat in their subtree. Doing this we get a tree where the leaves correspond precisely to the rats that we actually have to care about.

Subtask 1

In this Subtask, all \(e_i\) are the same. Something to note is that each rat will need to be stopped a certain amount of time no matter which manholes we keep closed to stop it. This time is 0 if the rat doesn't have time to reach us in \(T\) seconds, and \(T\) minus the distance from the rat to node 0 otherwise.

When all \(e_i\) are equal, it is always optimal to keep the manholes adjacent to manhole 0 closed. For each such manhole, we just have to find the time when the first rat reaches that manhole, and then keep it closed until the time remaining is equal to the distance between it and the root (manhole 0). This can be done with a BFS or DFS in \(\mathcal{O}(N)\).

Subtask 2

In this subtask there is exactly one rat. Since this rat will need to be stalled for a fixed amount of time, we should just find the cheapest ancestor (the one with the lowest \(e_i\)) to the rat and keep it closed for the necessary amount of time. This again takes \(\mathcal{O}(n)\).

Subtask 3

In this case there are at most 2 rats. We know how to handle just 1 rat, so suppose there are exactly 2. This can be solved with a bit of casework, but we will formulate a solution that can be generalised to more rats.

Suppose that if no manholes are closed during the night, one of the rats would arrive at the root at time \(T_1\) and the other at time \(T_2\) with \(T_1 < T_2\). Not only would the first rat arrive first at the root, it would also arrive at every manhole (on the intersection of the paths between the rats and the root) \(T_2-T_1\) seconds before the second rat. This means that untill we have stalled the first rat for at least \(T_2-T_1\) seconds, the 2 rats will never be at the same manhole at the same time. We can therefore choose where we first stall the first rat completely independently from the second rat. This is of course done in the same way as in subtask 2: by choosing the cheapest ancestor of the rat.

Once we have stalled the first rat for \(T_2-T_1\) seconds, they will be synced. With this we mean that they will reach the root at the same time if we don't close any more manholes. When the two rats are synched it will be best to either keep the cheapest manhole that is a common ancestor to both rats closed or to keep the 2 cheapest manholes on each individual rats path towards the root closed. The time we should do this can again be determined by the time the rats would reach the root if nothing was done.

This can again be implemented in \(\mathcal{O}(n)\).

Subtask 4

In this case \(T\) and \(N\) are both quite small. We can solve this case with a dp. We will let \(dp(i, t)\) represent the least total energy to keep all the rats in the subtree of node \(i\) from getting past node \(i\) untill \(t\) seconds have passed. When node \(i\) contains a rat, this is simply \(t \cdot e_i\).
When \(t \leq 0\), \(dp(i, t) = 0\). Otherwise, we can use the recursive formula

\[dp(i, t) = \min_{k \in [0, t]}(k\cdot e_i + \sum_j dp(j, t-k-w_j))\]
where the sum goes over all \(j\) that are children to \(i\) and where \(w_j\) is the time to travel between \(i\) and \(j\). Here \(k\) represents the length of time we choose to keep manhole \(i\) closed.

The state space has size \(N\cdot T\) and the transition is in \(\mathcal{O}(T)\) which yields the time complexity \(\mathcal{O}(N\cdot T^2)\). Challenge: prove that the transition can be done in \(\mathcal{O}(\log(T))\) instead.

Subtask 5

For this subtask, we will actually go back to the ideas from subtask 3. We can solve the problem like this:

1. First, sort the rats according to the time they will reach the root (if no manholes are closed).
2. Find the cheapest way to stall the first rat untill the first two rats become synched (they are synched if they will arrive at the root at the same time). Then, after the first two rats are synched, find the cheapest way to stall the first two rats untill they become synched with the third rat. Continue doing this untill all rats are synched.
3. Finally, after all rats are synched. Calculate the cheapest way to stall them from reaching the root untill \(T\) seconds have passed.

This might not seem much easier, but it is. The reason is that the problem is much easier when only considering a set of synched rats. To see why, we will introduce some new notation:

Let us define a covering of a tree to be a subset \(S\) of its nodes such that each rat has an ancestor in \(S\). Let us denote the cost of a covering as \(C(S) = \sum_{i \in S} e_i\) and let us denote the cost of a tree \(G\) as \(D(G) = \min( C(S))\) taken over all coverings \(S\) of \(G\). If we have sorted the rats by increasing distance from the root, let \(G_i\) be the tree consisting of all ancestors of the first \(i\) rats in the sorted list.

We now claim that if the first \(i\) rats are synched, the cheapest way of stalling these \(i\) rats for \(t\) second is \(D(G_i)\cdot t\). The main idea behind this is that stalling a set of synched rats for 1 second corresponds exactly to picking a covering of \(G_i\) and keeping the nodes in the covering closed for 1 second. It is perhaps not obvious that we want to use the same covering for all \(t\) seconds, but it is indeed the case.

To actually compute the answer let \(T_i\) be the time that the \(i\):th rat would arrive at the root. If there are \(M'\) rats (after removing rats too far away from the root), let \(T_{M'+1}=T\). The answer to the problem can then be computed as
\[\sum_{i=1}^{M'} D(G_i)\cdot (T_{i+1}-T_i).\]

One can note that when \(M' \leq 2\), this corresponds exactly to our solution for subtask 3.

Now we turn to computing the values \(D(G_i)\). If \(j\) is a node in \(G_i\) we define \(G_{i, j}\) to be the subtree of \(j\) in \(G_i\). We can find that
\[D(G_{i, j}) = \begin{cases} e_j & \text{if $j$ contains a rat} \\ \min(e_j, \sum_{k} D(G_{i, k})) & \text{otherwise} \end{cases}\]
where \(k\) goes over the children of \(j\) inside \(G_i\).

As \(G_{i, i} = G_{i}\), we can compute \(D(G_i)\) recursively in \(\mathcal{O}(N)\). As we need to calculate at most \(M\) such values, this solution takes \(\mathcal{O}(N\cdot M)\) time.

Subtask 6

We have now done a lot of the heavy lifting and at this point we just have to speed up the computation of the values \(D(G_i)\). Looking at the recursive formula for \(D(G_{i, j})\) We see that it only depends on the children of \(j\). Thus we can do the following:

Start with the tree \(G_1\) that contains all ancestors of the first rat and calculate \(D(G_{1, j})\) for all nodes \(j \in G_1\). Save these values in the variables \(D_j\). In particular, \(D_0\) will hold the value \(D(G_1)\) that we need.

Now, add the next rat and its ancestors to the tree \(G_1\) to get \(G_2\). The only nodes where \(D(G_{1, j}) \neq D(G_{2, j})\) will be nodes \(j\) that are ancestors of the second rat. Now we just update the values of \(D_j\) for the ancestors of the second rat by setting \(D_j = D(G_{2, j})\).

To update \(D_j\) quickly, we do not want to loop over all the children of \(j\). Instead we can save the value \(S_j\) which holds \(\sum D_k\) over all children \(k\) of \(j\). After updating \(D_k\), we can update \(S_j\) and then \(D_j\) accordingly in \(\mathcal{O}(1)\).

Now, after updating all \(D_j\) we again have \(D_0 = D(G_2)\) which is one of the values we need. We can now add the third rat in much the same way to calculate \(D(G_3)\) and keep going until we have added all the rats to the tree. Whenever we add a rat, we just need to update its ancestors and extract the value \(D_0\).

The time complexity of this algorithm will be \(\mathcal{O}(M\cdot d)\) where \(d\) is the depth of the tree.

Subtask 7

Now we need to speed up the computations even more. It seems difficult as it seems like we need to keep all the \(D_j\) updated to accurately compute \(D(G_i)\). We can however avoid this by being a bit tricky.

First. Let us do the same algorithm as in subtask 6, but we calculate the \(D(G_i)\) in reverse order, starting with the full tree and removing rats (and updating their ancestors D_j) from the tree as we go. This by itself does not improve anything, but does allow us to do a few optimisations.

We call a node \(j\) good if \(D_j = e_j\), that is: if the cheapest way to cover its subtree is by using the node itself. If a node is not good we call it bad. It is important to note that we only care about good nodes. The cheapest coverings of subtrees, which are the ones we care about, will only contain good nodes, and the value of $D(G_{i, j}) for any node \(j\) will only depend on the good nodes in \(j\):s subtree. Another nice thing is that as we remove rats from the tree, the values of \(D_j\) can only decrease. Thus, a node can only go from being good to being bad and not the other way around.
Thus, we actually do not have to update bad nodes, as they will never become good, and will never be relevant to the answer.

Suppose that we can magically find, for any node \(j\), the lowest ancestor \(g(j)\) of \(j\) that is good. Whenever we remove the rat from node \(j\), we can find \(g(j)\) and subtract \(e_j\) from \(S_{g(j)}\). We can then update \(D_{g(j)}\). If \(g(j)\) is still good, we don't have to update any other nodes, as \(D_{g(j)}\) hasn't changed. If instead, \(g(j)\) becomes bad, we have to update the next good node, \(g(g(j))\) by decreasing \(S_{g(g(j))}\) by the change that happened to \(D_{g(j)}\). We have to keep updating the next good ancestor until we reach the root or until we update a node that stays good after the update. Since each node can only go from good to bad once, this will run in \(\mathcal{O}(n\cdot t)\), where \(t\) is the time it takes to find \(g(j)\) for a node \(j\).

We can calculate \(g(j)\) in \(\mathcal{O}(\log(n)^2)\). One way to do this is by saving a compressed version of the tree. Whenever a node \(j\) becomes bad, merge it and its parent, \(p\) into a new node whose parent is the parent of \(p\) and whose children are the children of \(p\) and the children of \(j\). This merging can be done in amortized \(\mathcal{O}(\log(n)^2)\) with smaller to larger merging. Each node in this compressed tree contains exactly one good node from the original tree. To find \(g(j)\), we just have to pick out the unique good node in the compressed node containing \(j\).

Finally, we have a solution that runs in \(\mathcal{O}(n \log(n)^2)\), which is good enough to solve the problem.