Tags: competitive-programming
This article was translated from my Japanese blog.
2442 ConvexCut
Assume there exists a point P such that every line passing through P bisects the area. Then the lines parallel to the x-axis and y-axis passing through P also bisect the area. We also know that, for every vertex, there is another vertex point-symmetric to it. Conversely, if such a point P exists, then every line passing through P bisects the area. Therefore, we only need to check whether each vertex has a point-symmetric counterpart with respect to P. Since the constraints are not tight, it’s possible to solve the problem by just iterating over points in O(N^4).
2382 King Slime
Considering the process backward from the moment the King Slime is formed, we see that a slime can only stay at an initial slime position or at a wall. If other slimes exist on the x-axis or y-axis, it is better to connect the slimes to them. If the slimes are connected in this way, there will be at most one slime in each x-coordinate and y-coordinate, and the slimes will be arranged like a diagonal line. Finally, it’s best to connect the slimes by moving them to the wall. Since there are 4 walls, we need to find the minimum number of moves for each wall. There are also some cases where it is not necessary to move the slime all the way to a corner (this was a little bothersome). Since the order of the connections also matters, it is better to treat them as connected components of undirected graphs. You can use Union Find. The runtime complexity is O(N * Ack(N) + W + H).
1350 There is No Alternative
Build an MST after removing each edge. If an MST cannot be built, or if its total weight is greater than the original MST, then that edge is a No Alternative Bridge. However, a straightforward implementation takes O(number of edges) * O(runtime complexity of the MST algorithm), which is too slow. Since any two MSTs share many edges, we only have O(N) edges to examine. In the end, we can solve in O(N * E log N).
2303 Marathon Match
Let’s define as follows:
- P[i][j] := the probability that player i will rest j times,
- G[i][t] := the probability that player i will reach the goal at time t,
- W[i][t] := the probability that player i will win at time t,
- Tij := L/V[i] + j * T[i] (the time it takes for an athlete i to finish, taking a rest j times)
And then,
- G[i][t] = Σ_{j} P[i][j] (t = Tij),
- W[i][t] = G[i][t] * (1 - Σ_{k != i, t’ <= t}G[k][t’])
and the probability that athlete i wins is ΣW[i][t]. The finishing time may not be an integer, but it depends only on the player’s speed, the number of rests, and the rest duration. G and W can be calculated simultaneously, giving an O(N2M2) solution. At first, I used std::cout but I got WA by the output format error. I ended up using printf to specify the number of digits, though std::cout could probably work too.
2741 Invisible
Passing the turn removes all the cards from the stack, so the stack is never placed in a row with cards from the same player and placed from Player 1 and Player 2 in turn. Therefore, with the number of cards remaining in each player’s deck and the information of the last player who placed a card on the stack, the cards in the stack can be reconstructed, including their order. Since the number of states is O(n * m * (n + m) * 4), you can solve it with memoization or dynamic programming.
2304 Reverse Roads
Since we never use two opposite edges in the maximum flow (they cancel each other out, there is no such increase path in both directions at the same time), we can find the maximum flow in the original graph with the opposite edges (or, alternatively, we can think of it as an undirected graph), and check if the opposite edges are used in the maximum flow obtained.
2425 A Holiday of Miss Brute Force
Since the sister’s instructions depend only on the coordinates and elapsed time modulo 6, the number of states can be reduced to O(lx * ly * 6). We can find the shortest path on the graph whose nodes are these states, using the number of ignored instructions as the cost. Note that the instructions also depend on the parity of the x-coordinate. The total runtime complexity is O(N log N) (where N = lx * ly).
2297 Rectangular Stamps
Notice that the part of the picture stamped last can be stamped after any previous stamp, so the number of possible picture states is only O(2^16). The minimum number of stamps required to reach a state can be determined from the minimum number of stamps required before stamping each cell as a corner, which gives a recurrence that can be computed by DP. For each state, we need to press each cell with one of the four corners of each stamp, so the runtime complexity is O(2^16 * N * 4 * 4). After I used memoization and got TLE, I switched to DP and got AC.
1236 Map of Ninja House
In short, the problem is: “Given a preorder traversal in a graph, reconstruct the graph.” Easy problem. You can solve it by either O(V + E) DFS or O(V^2) DFS. Since there are several possible rooms that have already been passed through to which the distance from the first room is the same, in such cases, connect to the one with more remaining door capacity.
2342 A Light Road
Considering the number of mirrors P and Q in each cell and the direction from which the cell was reached, we can see that no state returns to itself (which means the directed graph of states is a DAG). Therefore, it is sufficient to ignore the path and perform DP over these states, and the runtime complexity is O(A^2 * 4 * NM).
2595 Cookie Counter
Let’s define:
- f(d, c) = the number of ways to eat c cookies in total over d days, eating more than 1 cookie per day (including order),
We can then compute f(i, N) * DCi for each i (i ≤ min(D, N)).
2747 Curtain
Since the window perimeter is parallel to the x-axis or y-axis and the curtain is given counter-clockwise, the left sides of the window (the side that goes from the negative x-axis to the inside of polygon) and the right sides of the window (the side that goes from the positive x-axis edge to the inside of polygon) can be determined by iterating over the y-coordinates in the given order (left for downward edges, right for upward edges). By sweeping the plane along the x-axis with this information, we can calculate the area of the window not covered by the curtain. Cutting all perpendicular edges by the y-coordinates of the given vertices beforehand makes the implementation easier, because each rectangle that appears during the sweep is either fully covered by the curtain or not covered at all. Here, the runtime complexity is now O(N^2).
The official solution is to compress the coordinate system and look at each square with O(N^3), which is far easier to implement and very clever.
SPOJ WINDOW1 is a similar looking problem, and it can actually be solved with the same sweep-line method as above in amortized O(N^2).
2643 AI
Parsing. Be careful about infinite loops and recursions.
2784 Similarity of Subtrees
For a subtree, similarity is determined only by the sequence of the number of nodes at each relative depth from its root. This sequence can be represented by a polynomial-like hash where the coefficient of xd is the number of nodes at depth d. For a node v, the hash can be computed bottom-up as Hv = 1 + x∑Hchild. Counting equal hashes gives the answer. In practice, use a pair of moduli or another collision-resistant representation.
2720 Identity Function
First, if N is not square-free, there is no answer: for a prime power pe ∣ N with e ≥ 2, taking a = p changes the p-adic valuation after applying a ↦ aN, so no iterate can return every residue to itself.
If N is square-free, the zero residue modulo each prime factor is fixed. For non-zero residues modulo p ∣ N, we need aNk ≡ a (mod p), so p − 1 must divide Nk − 1. Thus, if gcd(N, p - 1) != 1 for some prime factor p, the answer is -1. Otherwise, the answer is the lcm of the multiplicative orders of N modulo each p − 1.
2726 Black Company
The two complaint conditions impose ordering constraints on every pair of employees whose distance in the given graph is at most 2. If two such employees have the same contribution, their salaries must be equal; otherwise, the salary order must be the same as the contribution order.
So the problem can be seen as difference constraints on the square of the graph: contract equal-contribution pairs that are connected within distance 2, then assign each contracted component the smallest positive rank that is consistent with all increasing-contribution edges. The answer is the sum of these ranks over the original employees. The main implementation issue is to avoid explicitly building all distance-2 edges; split high-degree and low-degree vertices and process each neighborhood in contribution order.