This article was translated from my Japanese blog.
2442 ConvexCut
Assuming that there exists a point P by any lines on which the area is bisected, a line parallel to the x-axis and y-axes passing through the point can also bisect the area. We also know that, for every vertex, there is another vertex that is point-symmetric to it. Conversely, if such a point P exists, then any line passing through it will bisect its area. Therefore, we only need to check if each vertex pair is point-symmetric with respect to a point. 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 going backward from the point where it becomes the King Slime, we see that the slime can only stay at the initial point of each slime or at the 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. Also there are some cases where you aren’t necessary to drive the slime to the corner (it 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 MST with the graph without each edge, and if you can’t build MST or the sum of the MST edges is greater than the original MST (the case you don’t exclude any edges), then you can determine that the edge is No Alternative Bridge. However, if you implement it in a straightforward way, the runtime complexity is O(number of edges) * O(runtime complexity of MST Algorithm), which doesn’t make in time. As you notice, any two MSTs have many common edges, we have only 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 will win will be ΣW[i][t]. The time to finish may not be an integer, but the time depends only on the speed of the player and the number of rest time and rest time of the player, G and W can be calculated simultaneously and solved in O(N2M2). At first, I used std::cout but I got WA by the output format error. Although I ended up using printf to specify the number of digits, maybe we could use std:cout (I didn’t come up…)
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 instructions of the sister depend only on the remainder divided by 6 of the coordinates and elapsed time, the number of states can be reduced to O(lx * ly * 6). We can find the shortest path on the graph with that states as nodes and with the number of times the sister will be ignored as the cost. Note that the instructions also depends on the parity of x-coordinates. The total runtime complexity is O(N log N) (where N = lx * ly).
2297 Rectangular Stamps
Notice that the part of the picture that was last stamped can be stamped with any previous stamps, the number of possibilities is only O(2^16) if we consider any part of the picture. The minimum number of stamps required to reach a state is determined by the minimum number of stamps required to complete the state before each cell is stamped as a corner, we can get a recurrence and compute it 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
The problem is, in short, “Given a preorder traversal in a graph, so 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 with the one that has more vacancy in the number of doors.
2342 A Light Road
Considering the number of mirrors P and Q in each cell and the direction from which the square was reached, we can see that each state does not return to its own state (which means the directed graph of states is DAG). Therefore, it is sufficient to ignore the path and perform DP considering only that states, and the runtime complexity is O(A^2 * 4 * NM).
2595 Cookie Counter
Let’s define:
- f(d, c) = In d days, the total number of ways to eat more than 1 cookie a day and eat c cookies in total (including the order),
We can then compute f(i, N) * DCi for each i (i ≤ min(D, N)).
2747 Curtain
Since the perimeters of window is either parallel to 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 given order(left for down, right for up). By sweeping the plane along the x-axis with the info, wen can calculate the area of the window that is not covered by the curtain. Cutting all the perpendicular edges by the y-coordinates of given vertices beforehand makes the implementation easier as the rectangles that will emerge during sweeping the plane are either all covered by the curtain or not covered entirely. 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 sweeping line method as above in amortized O(N^2)).
2643 AI
Parsing. Be careful about infinite loops and recursions.
2784 Similarity of Subtrees
TODO.
2720 Identity Function
TODO.
2726 Black Company
TODO.