Editorial for DMOPC '17 Contest 5 P4 - Intersecting Arcs

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: r3mark

There is no intended solution for the first subtask.

For the second subtask, let $dp[a][b][c]$ ~dp[a][b][c]~ be the number of ways to draw the arcs in the first $a$ ~a~ dots so that the number of open arcs (only the left endpoint has been drawn so far) is $b$ ~b~ and there have been exactly $c$ ~c~ intersections where intersections between a completed arc and an open arc are counted as well. For each $a, b, c$ ~a, b, c~ there are three choices for the $a^\text{th}$ ~a^\text{th}~ dot. The first case is not putting any endpoint on this dot. This contributes $dp[a-1][b][c]$ ~dp[a-1][b][c]~ ways. The second case is putting a left endpoint on this dot, which increases the number of open arcs by one and doesn't change the number of intersections. This contributes $dp[a-1][b-1][c]$ ~dp[a-1][b-1][c]~ ways. The final case is putting a right endpoint on this dot. This decreases the number of open arcs by one. Note that there are $b+1$ ~b+1~ possible left endpoints which this right endpoint can connect to, and depending on which endpoint is chosen, can increase the number of intersections by $0, 1, \dots, b$ ~0, 1, \dots, b~. So this case contributes $dp[a-1][b+1][c] + dp[a-1][b+1][c-1] + dp[a-1][b+1][c-2] + \dots + dp[a-1][b+1][c-b]$ . The final answer is $dp[n][0][k]$ ~dp[n][0][k]~.

Time Complexity: $\mathcal O(N^3K)$ ~\mathcal O(N^3K)~

For the final subtask, we optimize the solution for the second subtask. Note that each row $dp[a][?][?]$ ~dp[a][?][?]~ only depends on $dp[a-1][?][?]$ ~dp[a-1][?][?]~ so the dp table can be compressed to $dp[2][n+1][k+1]$ ~dp[2][n+1][k+1]~. Also, for the third case where the dot is used as a left endpoint, we can optimize this by computing the prefix sum of $dp[a-1][b+1][?]$ ~dp[a-1][b+1][?]~ in $\mathcal O(K)$ ~\mathcal O(K)~ and using this to handle the third case in $\mathcal O(1)$ ~\mathcal O(1)~ instead of $\mathcal O(N)$ ~\mathcal O(N)~ as previously done. The prefix sums only need to be computed for each $a$ ~a~ and $b$ ~b~, so that gives $\mathcal O(N^2K)$ ~\mathcal O(N^2K)~.

Time Complexity: $\mathcal O(N^2K)$ ~\mathcal O(N^2K)~

Comments

2

tankibuds commented on March 31, 2018, 5:20 p.m.

If the first 10 points have three intersections formed by arcs (1, 7), (4, 8), and (6,10), and there are three open arcs at points 2, 3, and 9, this pattern should contribute to dp[10][3][3].

When a moves to the 11th point, one of the states we need to calculate is dp[11][2][3]. According to the editorial, the above example should contribute to dp[11][2][3] if the 11th point is an end point of an arc. However, in this case no matter which open arc is connected to the 11th point, an additional intersection is formed which transits to dp[11][2][4]. I do not see how the example can transit to dp[11][2][3].

Can anybody explain where I misinterpreted the editorial?

1

r3mark commented on March 31, 2018, 9:51 p.m. ← edited →

In the editorial's solution (which is the only one I'm aware exists), the intersections are counted when the left arc in the intersection is completed and only the left endpoint of the right arc has been chosen. So the intersection you are asking about has already been counted earlier.

Edit: I've updated the editorial - the previous definition of what was being stored by dp was incorrect.