PROBLEM LINK:
Author: Kevin Atienza
Tester: Suhash Venkatesh and Kevin Atienza
Editorialist: Kevin Atienza
PREREQUISITES:
Eulerian cycles, combinatorics
PROBLEM:
You are given a very regular grid city:
- There are main roads: roads between (x,y) and (x+1,y) for all 0 \le x < N, 0 \le y \le 2.
- There are secondary roads: between (x,y) and (x,y+1) for all 0 \le x \le N, 0 \le y < 2.
- There are some tertiary roads: roads between (x,y) and (x+1,y+1), or (x,y+1) and (x+1,y), for all 0 \le x < N, 0 \le y < 2.
A configuration is inspection-friendly if one can start at (0,0), traverse all roads exactly once, and end up again at (0,0).
- The cost of building and destroying a tertiary road from (x,y) to (x+1,y+1) is H_b and H_d, respectively.
- The cost of building and destroying a tertiary road from (x,y+1) to (x+1,y) is L_b and L_d, respectively.
- One cannot build or destroy main or secondary roads.
What is the minimum cost needed to make the city inspection-friendly, and the number of ways to achieve this cost?
QUICK EXPLANATION:
We want to have an Eulerian cycle in our graph, which means that the degrees of all nodes must be even. One can show that the following things are necessary and sufficient for this to happen:
- There is a solution if and only if N is even.
- There must be no roads between the following pairs of intersections: \{(0,0),(1,1)\}, \{(0,2),(1,1)\}, \{(N,0),(N-1,1)\}, \{(N,2),(N-1,1)\}. This adds a fixed cost in our solution.
- For every odd 0 < x < N, either only roads A and D, or B and C, must be present: A = \{(x-1,1),(x,2)\}, B = \{(x,2),(x+1,1)\}, C = \{(x-1,1),(x,0)\}, D = \{(x,0),(x+1,1)\}. There can be one or two ways to do this, depending on whether the costs are equal or not.
- For every even 0 < x < N, either only roads A and C, or B and D, must be present: A = \{(x-1,1),(x,2)\}, B = \{(x,2),(x+1,1)\}, C = \{(x-1,1),(x,0)\}, D = \{(x,0),(x+1,1)\}. There can be one or two ways to do this, depending on whether the costs are equal or not.
To compute the answer, just add up all the costs, and multiply the number of ways for all x, 0 < x < N. Since N can be very large, you might need to exploit the periodicity of the configuration to compute the answer quickly.
EXPLANATION:
Eulerian cycles
We want to have a layout that has the property that there exists a path from (0,0) to (0,0) that passes through every edge exactly once. The starting point doesn’t really matter, because the path we want is actually a cycle. In other words, this property is equivalent to the property that there exists a cycle that passes through every edge exactly once. But this is exactly the definition of an Eulerian cycle.
There’s a well-known condition for the existence of an Eulerian cycle in a graph:
A graph has an Eulerian cycle if and only if it is connected and every node has degree two.
It’s easy to prove the forward direction. For the backward direction, we invite the reader to find a proof online (such as this one). But for the current problem, this characterization will help us in finding the answer.
Now, the problem itself can be solved with some clever dynamic programming and matrix exponentiation techniques, but in this editorial we’ll describe a more specialized solution that works for the kind of graph we’re working with.
The graph is already connected, so all we need to do is ensure that the degree of every node is two. To simplify, let’s first ignore the costs and assume we have complete control in placing the diagonal edges (or roads). Without the diagonal edges, our graph looks something like this:
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-- ...
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-- ...
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-- ...
With just this, it looks like most nodes have an odd degree, particularly the ones on the edges (but not the corners). So it’s our job to make those degrees even, by adding the diagonal edges.
Let’s look at the three leftmost nodes. Clearly, we can’t place any edge on the corner nodes, because doing so would make their degrees odd (and since there’s only one edge that can be placed on them, there’s no way to make them even again.) But on the middle node, we must place exactly one edge to make it even. We have two choices:
(A) (B)
+-----+-----+-----+-- ... +-----+-----+-----+-- ...
| /| | | | | | |
| / | | | | | | |
| / | | | | | | |
| / | | | | | | |
|/ | | | | | | |
+-----+-----+-----+-- ... +-----+-----+-----+-- ...
| | | | |\ | | |
| | | | | \ | | |
| | | | | \ | | |
| | | | | \ | | |
| | | | | \| | |
+-----+-----+-----+-- ... +-----+-----+-----+-- ...
Either one works, though our choice here will affect our choices later on. Let’s consider the choice (A), and look at the second column of (three) nodes. Note that the top two nodes already have even degrees, but the bottom one has an odd degree, which means we need to place an edge on it. It looks like we have two choices:
+-----+-----+-----+-- ... +-----+-----+-----+-- ...
| /| | | | /| | |
| / | | | | / | | |
| / | | | | / | | |
| / | | | | / | | |
|/ | | | |/ | | |
+-----+-----+-----+-- ... +-----+-----+-----+-- ...
| | /| | |\ | | |
| | / | | | \ | | |
| | / | | | \ | | |
| | / | | | \ | | |
| |/ | | | \| | |
+-----+-----+-----+-- ... +-----+-----+-----+-- ...
But actually, the second one doesn’t work, because it makes the middle node on the first column have an odd degree! Thus, we’re forced to add the edge in the first choice. Similarly, for choice (B) above, we must place this edge:
+-----+-----+-----+-- ...
| |\ | |
| | \ | |
| | \ | |
| | \ | |
| | \| |
+-----+-----+-----+-- ...
|\ | | |
| \ | | |
| \ | | |
| \ | | |
| \| | |
+-----+-----+-----+-- ...
So all in all we now have the following choices:
(A) (B)
+-----+-----+-----+-- ... +-----+-----+-----+-- ...
| /| | | | |\ | |
| / | | | | | \ | |
| / | | | | | \ | |
| / | | | | | \ | |
|/ | | | | | \| |
+-----+-----+-----+-- ... +-----+-----+-----+-- ...
| | /| | |\ | | |
| | / | | | \ | | |
| | / | | | \ | | |
| | / | | | \ | | |
| |/ | | | \| | |
+-----+-----+-----+-- ... +-----+-----+-----+-- ...
Now, let’s look at the third column. Notice that in both choices, the outcome for the third column is the same, which is that all nodes have an odd degree! For now, let’s ignore the top and bottom nodes and focus on the middle one. As before, we only have two choices for where we can place the edge:
+-----+-----+-----+-- ... +-----+-----+-----+-- ...
| | | /| | | | |
| | | / | | | | |
| | | / | | | | |
| | | / | | | | |
| | |/ | | | | |
+-----+-----+-----+-- ... +-----+-----+-----+-- ...
| | | | | | |\ |
| | | | | | | \ |
| | | | | | | \ |
| | | | | | | \ |
| | | | | | | \|
+-----+-----+-----+-- ... +-----+-----+-----+-- ...
And as before, this choice forces us again on our choice of edge for the next column of nodes:
+-----+-----+-----+-----+-- ... +-----+-----+-----+-----+-- ...
| | | /| | | | | |\ |
| | | / | | | | | | \ |
| | | / | | | | | | \ |
| | | / | | | | | | \ |
| | |/ | | | | | | \|
+-----+-----+-----+-----+-- ... +-----+-----+-----+-----+-- ...
| | | | /| | | |\ | |
| | | | / | | | | \ | |
| | | | / | | | | \ | |
| | | | / | | | | \ | |
| | | |/ | | | | \| |
+-----+-----+-----+-----+-- ... +-----+-----+-----+-----+-- ...
which leaves us again with a choice similar to the first one! This means that we can continue this process and end up with a series of choices that look like the following:
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-- ...
| /| | |\ | |\ | /| | |\
| / | | | \ | | \ | / | | | \
| / | | | \ | | \ | / | | |
| / | | | \ | | \ | / | | |
|/ | | | \| | \|/ | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-- ...
| | /|\ | |\ | | | /|\ |
| | / | \ | | \ | | | / | \ |
| | / | \ | | \ | | | / | \ |
| | / | \ | | \ | | | / | \ |
| |/ | \| | \| | |/ | \|
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-- ...
We can look at such a graph as a graph made by piecing together the following subgraphs in a sequence:
(P1) (P2)
+-----+-----+ +-----+-----+
| /| | | |\ |
| / | | | | \ |
| / | | | | \ |
| / | | | | \ |
|/ | | | | \|
+-----+-----+ +-----+-----+
| | /| |\ | |
| | / | | \ | |
| | / | | \ | |
| | / | | \ | |
| |/ | | \| |
+-----+-----+ +-----+-----+
This also gives us another piece of information: If N is odd, then we are forced to place an edge towards a corner, so we can immediately output “a kitchen nightmare”!
So we can assume that N is even, and proceed.
Note that our graph above still doesn’t have an Eulerian cycle, because some nodes still have odd degrees; namely the nodes in the following marked as #:
+-----+-----#-----+-----#-----+-----#-----+-----#-----+-- ...
| /| | |\ | |\ | /| | |\
| / | | | \ | | \ | / | | | \
| / | | | \ | | \ | / | | |
| / | | | \ | | \ | / | | |
|/ | | | \| | \|/ | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-- ...
| | /|\ | |\ | | | /|\ |
| | / | \ | | \ | | | / | \ |
| | / | \ | | \ | | | / | \ |
| | / | \ | | \ | | | / | \ |
| |/ | \| | \| | |/ | \|
+-----+-----#-----+-----#-----+-----#-----+-----#-----+-- ...
Clearly, regardless of which subgraphs (P1 or P2) we put together, this same set of nodes will have an odd degree.
To make our task easier, let’s look at which edges we still have control over whether to place or not:
+-----+-----#-----+-----#-----+-----#-----+-----#-----+-- ...
| | ?|? | ?|? | ?|? | ?|? |
| | ? | ? | ? | ? | ? | ? | ? | ? |
| | ? | ? | ? | ? | ? | ? | ? | ? |
| | ? | ? | ? | ? | ? | ? | ? | ? | ?
| |? | ?|? | ?|? | ?|? | ?|?
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-- ...
| |? | ?|? | ?|? | ?|? | ?|?
| | ? | ? | ? | ? | ? | ? | ? | ? | ?
| | ? | ? | ? | ? | ? | ? | ? | ? |
| | ? | ? | ? | ? | ? | ? | ? | ? |
| | ?|? | ?|? | ?|? | ?|? |
+-----+-----#-----+-----#-----+-----#-----+-----#-----+-- ...
Let’s look at the two leftmost #s. Clearly, exactly one edge must come out of each. However, we must also choose the edges so that the middle nodes remain of even degree! By checking all four possibilities, we are left with two viable ones:
+-----+-----#-----+-----+-- ... +-----+-----#-----+-----+-- ...
| | /| | | | | |\ | |
| | / | | | | | | \ | |
| | / | | | | | | \ | |
| | / | | | | | | \ | |
| |/ | | | | | | \| |
+-----+-----+-----+-----+-- ... +-----+-----+-----+-----+-- ...
| |\ | | | | | | /| |
| | \ | | | | | | / | |
| | \ | | | | | | / | |
| | \ | | | | | | / | |
| | \| | | | | |/ | |
+-----+-----#-----+-----+-- ... +-----+-----#-----+-----+-- ...
(the remaining two choices will leave the middle node in the second column of odd degree, with no way of making it even.)
Note that in both cases, we have made the two #s of even degree, and yet the middle ones remain of even degree!
Continuing, we see that for the next pair of #s, we also have the same set of choices. By doing the same reasoning for all pairs of #s, we end up with a graph that looks like this:
+-----+-----#-----+-----#-----+-----#-----+-----#-----+-----#-- ...
| | |\ | /| | /| | |\ | /|
| | | \ | / | | / | | | \ | / |
| | | \ | / | | / | | | \ | / |
| | | \ | / | | / | | | \ | / |
| | | \|/ | |/ | | | \|/ |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-- ...
| | | /|\ | |\ | | | /|\ |
| | | / | \ | | \ | | | / | \ |
| | | / | \ | | \ | | | / | \ |
| | | / | \ | | \ | | | / | \ |
| | |/ | \| | \| | |/ | \|
+-----+-----#-----+-----#-----+-----#-----+-----#-----+-----#-- ...
which looks like a graph made by piecing together the following subgraphs in a sequence (aside from the leftmost column):
(P3) (P4)
+-----#-----+ +-----#-----+
| /| | | |\ |
| / | | | | \ |
| / | | | | \ |
| / | | | | \ |
|/ | | | | \|
+-----+-----+ +-----+-----+
|\ | | | | /|
| \ | | | | / |
| \ | | | | / |
| \ | | | | / |
| \| | | |/ |
+-----#-----+ +-----#-----+
By “combining” this P3 - P4 sequence with our P1 - P2 sequence, we now have a graph where all nodes have even degree! Furthermore, since we have exhausted all possibilities, we have just shown that all such graphs can be obtained this way.
Let’s give an example. Let’s try to merge this P1 - P2 sequence:
+-----+-----#-----+-----#-----+-----#-----+-----#-----+-----#-----+-----+
| /| | |\ | /| | /| | |\ | |\ |
| / | | | \ | / | | / | | | \ | | \ |
| / | | | \ | / | | / | | | \ | | \ |
| / | | | \ | / | | / | | | \ | | \ |
|/ | | | \|/ | |/ | | | \| | \|
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | /|\ | | | /| | /|\ | |\ | |
| | / | \ | | | / | | / | \ | | \ | |
| | / | \ | | | / | | / | \ | | \ | |
| | / | \ | | | / | | / | \ | | \ | |
| |/ | \| | |/ | |/ | \| | \| |
+-----+-----#-----+-----#-----+-----#-----+-----#-----+-----#-----+-----+
with this P3 - P4 sequence:
+-----+-----#-----+-----#-----+-----#-----+-----#-----+-----#-----+-----+
| | |\ | /| | /| | |\ | /| | |
| | | \ | / | | / | | | \ | / | | |
| | | \ | / | | / | | | \ | / | | |
| | | \ | / | | / | | | \ | / | | |
| | | \|/ | |/ | | | \|/ | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | /|\ | |\ | | | /|\ | | |
| | | / | \ | | \ | | | / | \ | | |
| | | / | \ | | \ | | | / | \ | | |
| | | / | \ | | \ | | | / | \ | | |
| | |/ | \| | \| | |/ | \| | |
+-----+-----#-----+-----#-----+-----#-----+-----#-----+-----#-----+-----+
The result is the following graph:
+-----+-----#-----+-----#-----+-----#-----+-----#-----+-----#-----+-----+
| /| |\ |\ /| /| /| /| |\ |\ /| |\ |
| / | | \ | \ / | / | / | / | | \ | \ / | | \ |
| / | | \ | X | / | / | / | | \ | X | | \ |
| / | | \ | / \ | / | / | / | | \ | / \ | | \ |
|/ | | \|/ \|/ |/ |/ | | \|/ \| | \|
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | /|\ /|\ | |\ /| | /|\ /|\ |\ | |
| | / | \ / | \ | | \ / | | / | \ / | \ | \ | |
| | / | X | \ | | X | | / | X | \ | \ | |
| | / | / \ | \ | | / \ | | / | / \ | \ | \ | |
| |/ |/ \| \| |/ \| |/ |/ \| \| \| |
+-----+-----#-----+-----#-----+-----#-----+-----#-----+-----#-----+-----+
Take note of where the P1, P2, P3 and P4’s were placed, and why they don’t “interfere” with one another.
(Note that two diagonals crossing each other, even though it creates a new node, doesn’t affect our answer, because the newly generated node has an even degree.)
Computing the answer
Now that we know what “valid” graphs look like, it’s time to compute the minimum cost (and the number of ways) to turn our initial graph into a valid one. Note that our graph already has some diagonal edges placed, which means we must also consider the cost of deleting some edges when trying to find the minimum cost.
But due to the way “valid” graphs are formed from 2 by 2 “blocks”, we can figure it out “block by block”, i.e. we figure it out separately for the following choices:
+-----+-----+-----+-----+-----+-----+-- ...
| ?|? | | | | |
| ? | ? | | | | |
| ? | ? | | | | |
| ? | ? | | | | |
|? | ?| | | | |
+-----+-----+-----+-----+-----+-----+-- ...
|? | ?| | | | |
| ? | ? | | | | |
| ? | ? | | | | |
| ? | ? | | | | |
| ?|? | | | | |
+-----+-----+-----+-----+-----+-----+-- ...
+-----+-----+-----+-----+-----+-----+-- ...
| | ?|? | | | |
| | ? | ? | | | |
| | ? | ? | | | |
| | ? | ? | | | |
| |? | ?| | | |
+-----+-----+-----+-----+-----+-----+-- ...
| |? | ?| | | |
| | ? | ? | | | |
| | ? | ? | | | |
| | ? | ? | | | |
| | ?|? | | | |
+-----+-----+-----+-----+-----+-----+-- ...
+-----+-----+-----+-----+-----+-----+-- ...
| | | ?|? | | |
| | | ? | ? | | |
| | | ? | ? | | |
| | | ? | ? | | |
| | |? | ?| | |
+-----+-----+-----+-----+-----+-----+-- ...
| | |? | ?| | |
| | | ? | ? | | |
| | | ? | ? | | |
| | | ? | ? | | |
| | | ?|? | | |
+-----+-----+-----+-----+-----+-----+-- ...
+-----+-----+-----+-----+-----+-----+-- ...
| | | | ?|? | |
| | | | ? | ? | |
| | | | ? | ? | |
| | | | ? | ? | |
| | | |? | ?| |
+-----+-----+-----+-----+-----+-----+-- ...
| | | |? | ?| |
| | | | ? | ? | |
| | | | ? | ? | |
| | | | ? | ? | |
| | | | ?|? | |
+-----+-----+-----+-----+-----+-----+-- ...
...
Since these “diamonds” don’t interfere with one another, we can check them independently of one another. Note that for each “diamond”, there are two choices, but depending on the parity, it’s either “P1 - P2” or “P3 - P4”.
Therefore, to get the minimum cost and the number of ways:
- Initialize the “running” minimum cost C = 0 and “running” number of ways W = 1.
- For each diamond, check both choices. For each choice, figure out the cost of “turning” that diamond into that choice, and add the smaller choice to our running cost C.
- If both costs are the same, then we multiply W by two. (then reduce it modulo 10^9 + 7)
- After this process, the answer is now C and W.
This process clearly works, but there are a few blemishes. First, there are four “corner” edges that need to be taken care of separately:
+-----+-----+-----+-- ... --+-----+-----+-----+
|? | | | | | | ?|
| ? | | | | | | ? |
| ? | | | | | | ? |
| ? | | | | | | ? |
| ?| | | | | |? |
+-----+-----+-----+-- ... --+-----+-----+-----+
| ?| | | | | |? |
| ? | | | | | | ? |
| ? | | | | | | ? |
| ? | | | | | | ? |
|? | | | | | | ?|
+-----+-----+-----+-- ... --+-----+-----+-----+
If there are edges in those places, we have no choice but to destroy them and incur the costs.
Also, the algorithm above is only feasible when N is small. For large N, we must exploit the fact that the grid is a repeating sequence of blocks of length K. If K is even, we can perform the above steps for the block of length K and simply multiply the cost by N/K (and raise the number of ways to N/K), but we must also take into account the “blocks” formed by adjoining two length-K sequences. For example:
... -----+-----+-----+-----# #-----+-----+-----+----- ...
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
... -----+-----+-----+-----+ + +-----+-----+-----+----- ...
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
... -----+-----+-----+-----# #-----+-----+-----+----- ...
Adjoining them yields the following “diamond”:
... -----+-----+-----+-----#-----+-----+-----+----- ...
| | | ?|? | | |
| | | ? | ? | | |
| | | ? | ? | | |
| | | ? | ? | | |
| | |? | ?| | |
... -----+-----+-----+-----+-----+-----+-----+----- ...
| | |? | ?| | |
| | | ? | ? | | |
| | | ? | ? | | |
| | | ? | ? | | |
| | | ?|? | | |
... -----+-----+-----+-----#-----+-----+-----+----- ...
To adjust for this, we just compute the minimum cost for one such diamond and add it to C a total of N/K-1 times. W can be updated similarly.
The case where K is odd can be handled similarly.
Time Complexity:
O(K + \log N)
AUTHOR’S AND TESTER’S SOLUTIONS:
Will be added soon