Editorial for DMOPC '21 Contest 7 P6 - Rainbow Subgraphs

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: zhouzixiang2004

Subtask 1

Hint All the points in V are contained inside a small (2N+2M-1) \times (N+M) rectangle.
Hint 2 Use broken profile DP.
Solution For subtask 1, note that all the points in V are contained inside a (2N+2M-1) \times (N+M) rectangle, which has a "height" of only N+M \le 15. We can use dynamic programming on broken profiles, keeping track of which nodes in a profile of size N+M are chosen to be in the subgraph. This takes \mathcal{O}\left((2N+2M-1)(N+M) \cdot 2^{N+M}\right) = \mathcal{O}\left((N+M)^2 \cdot 2^{N+M}\right) time.

Time Complexity: \mathcal{O}\left((N+M)^2 \cdot 2^{N+M}\right)

Subtask 2

Hint Most of the rectangle is empty. At most how many points are there for each x-coordinate?
Hint 2 Use this to reduce the number of states in the broken profile DP.
Solution For subtask 2, note that although the rectangle has a height of N+M, there aren't too many points sharing the same x-coordinate. Printing out the "rainbow" shape for N = 35, M = 5 shows that there are at most 20 points with the same x-coordinate under the constraints for subtask 2. We can modify the usual broken profile DP to maintain a profile that never gets larger than this.

We can analyze the time complexity of this solution as follows. Observe that the maximum number of points sharing the same x-coordinate is achieved at x = \pm N. At these columns, we have x^2+y^2 < (N+M)^2 \implies y < \sqrt{(N+M)^2-N^2} = \sqrt{2MN+M^2}, so the profile size needs to be approximately \sqrt{2MN+M^2}:


Furthermore, there are only around \frac{\pi}{2}(N+M)^2-\frac{\pi}{2}N^2 = \frac{\pi}{2}(2MN+M^2) = \mathcal{O}((N+M)M) nodes in V, and we perform \mathcal{O}\left(2^\sqrt{2MN+M^2}\right) transitions for each node. Therefore the time complexity is no more than \mathcal{O}\left((N+M)M \cdot 2^{\sqrt{2MN+M^2}}\right). In fact, the time complexity is lower than this because the profile needed is almost always smaller than \sqrt{2MN+M^2}.

Time Complexity: \mathcal{O}\left((N+M)M \cdot 2^{\sqrt{2MN+M^2}}\right)

Subtask 3

Hint What is the bottleneck of the subtask 2 solution? How can we prevent needing this many states?
Hint 2 Note that the horizontal "width" of the rainbow shape is small when the vertical "width" is large.
Solution For subtask 3, consider the bottom-left part of the graph (Case when N = 100, M = 5 is shown below, rotated 90^{\circ} for convenience): 
##############C...................................
##############C######.............................
##############C##########.........................
##############CBBBBBBBBBBBBBB.....................
AAAAAAAAAAAAAACAAAAAAAAAAAAAAAAAA.................
...............####################...............
....................##################............
.........................################.........
............................###############.......
................................#############.....
...................................############...
.....................................############.
........................................##########
..........................................########
............................................######
..............................................####
................................................##
..................................................
..................................................
..................................................
The bottleneck of the subtask 2 solution is the long column at x = \pm N (A's above), causing the profile to get up to size 33 when N = 100, M = 5. However, the profile size drops drastically to only 20 in the next column. Furthermore, there is a large, perfect rectangle of points to the left of the C's in the diagram above. If we knew the state of all the M C's, we could use a simpler dynamic programming to find the number of ways to complete the subgraph within this rectangle. We can process the region to the right of the C's and above the B's (in the diagram above) while maintaining a state of which C's are chosen and a profile that doesn't exceed the number of B's in the diagram. After processing this region, we can multiply the current DP value by the number of ways to complete the subgraph within the rectangle and continue with the same broken profile DP as subtask 2 (now that the information about the C's is no longer needed). This idea reduces the maximum necessary size of the profile by about \sqrt{2N}-M, which is enough for subtask 3.

Time Complexity: \mathcal{O}\left((N+M)M \cdot 2^{\sqrt{M^2+2MN}-\sqrt{2N}+M}\right)

Subtask 4

Hint How can we extend the idea from subtask 3 to further reduce the maximum size of the profile needed?
Hint 2 Switch from using horizontal profiles to vertical profiles at the optimum location.
Solution The subtask 3 solution effectively switches between using a horizontal profile and a vertical profile at the x = \pm N column. Instead, we can switch between using horizontal profiles and vertical profiles at x \approx \pm \frac{\sqrt{2}}{2}N to minimize the maximum horizontal or vertical profile size we need.


We can calculate the maximum profile size we now need as \sqrt{(N+M)^2-\left(\frac{\sqrt{2}}{2}N\right)^2}-\frac{\sqrt{2}}{2}N = \sqrt{\frac{1}{2}N^2+2NM+M^2}-\frac{\sqrt{2}}{2}N. When N is much larger than M, this is slightly less than \sqrt{\frac{1}{2}N^2+2NM+2M^2}-\frac{\sqrt{2}}{2}N = \sqrt{\left(\frac{\sqrt{2}}{2}N+\sqrt{2}M\right)^2}-\frac{\sqrt{2}}{2}N = \left(\frac{\sqrt{2}}{2}N+\sqrt{2}M\right)-\frac{\sqrt{2}}{2}N = \sqrt{2}M. Therefore, the maximum profile size we now need is about \sqrt{2}M.

Time Complexity: \mathcal{O}\left((N+M)M \cdot 2^{\sqrt{2}M}\right)

Subtask 5

Hint How can we transition more smoothly between a perfectly horizontal profile at the start to a perfectly vertical profile at the middle?
Hint 2 The "rainbow" shape has a uniform "thickness" of M.
Hint 3 Instead of sweeping through the rainbow in a linear fashion, sweep through it in an angular fashion.
Solution Instead of "sharply" transitioning between horizontal and vertical profiles, we can instead sweep through the points in V in order of their angle to (0,0). We maintain a profile that consists of all points that are adjacent to at least one other point that has not been processed yet, and keep the profile sorted in order of the points' distances to the origin. As the rainbow shape has a uniform "thickness" of M, the size of this "angular" profile will never exceed M:


(In fact, the size of the profile gets closer to \frac{\sqrt{2}}{2}M when the angle gets near 45^{\circ} or 135^{\circ}, so this solution runs faster than what the asymptotic complexity suggests.)

When handling the DP transitions, a naive implementation might take \mathcal{O}\left(M \cdot 2^M\right) time for each point, which might have some difficulty passing. We can optimize this to \mathcal{O}\left(2^M\right) by individually handling the 4 possible cases for the difference between the old and new profile, using constant time bitmask operations:
  1. Replace two consecutive points with one new point.
  2. Replace one point with a new point.
  3. Insert a new point at the beginning.
  4. Insert a new point at the end.
If necessary, we can also reduce the runtime by a factor of 2 by only calculating the DP for one quadrant and noting that the other quadrant is symmetrical.

Time Complexity: \mathcal{O}\left((N+M)M \cdot 2^M\right)

Remark: The small "thickness" of the rainbow shape we used in this problem can be viewed as the graph G having a small pathwidth.
Remarks Let's number each node in V by its index when the points are sorted by angle. Here's an observation that might make the solution easier to implement: For every node i, observe that there are at most M distinct nodes u \le i that have an edge to a node v > i. This means that we can do a bitmask DP that tracks the current node and the state of these previous (up to) M nodes u.

Comments


  • 1
    bqi343  commented on Oct. 18, 2024, 3:02 a.m.

    The claim in the alternative solution seems wrong? For N=1, (1,0) and (1,1) are connected by an edge but are not always within M indices of each other.


    • 1
      zhouzixiang2004  commented on Oct. 18, 2024, 2:26 p.m.

      I replaced the alternative solution with a remarks section that is hopefully more correct.