Editorial for ECOO '21 P6 - Problematic Pathways

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.

Authors: AQT, ChrisT

Subtask 1

For every segment between i and i+1, we can either direct it from i to i+1 or we can direct it from i+1 to i. This means that every segment has two different states. So, we can try all 2^{N-1} different configurations and find the minimal one. We can find the number of pairs for each configuration in \mathcal{O}(N) time.

Time complexity: \mathcal{O}(2^NN)

Subtask 2

We can think about this problem as partitioning the segments into multiple contiguous parts where every segment in one part has the same orientation and different orientation from the adjacent contiguous parts. We will try to apply dynamic programming to this program. dp[n][k] will be a boolean. dp[n][k] is true when it is possible to get k pairs among the first n friends and false otherwise. To find whether dp[n][k] is true or not, we can try to consider every suffix [m, n] where 1 \le m < n is a contiguous segment described above. So, we have

\displaystyle dp[n][k] = \begin{cases}
true, & \text{if } dp[m][k - c_{m, n}] \text{ is true} \\
false, & \text{otherwise}

where c_{m, n} is the number of pairs of the same element in the subarray [m, n]. We can quickly compute c_{m, n} by adding the number of other elements that are equal to a_m in [m+1, n] to c_{m, n}. This can be done quickly by having a frequency array. Thus, it is possible to have \mathcal{O}(N^3) states and \mathcal{O}(N) transition.

Time Complexity: \mathcal{O}(N^4)

Subtask 3

Note that for a fixed n and m, then for all k, if dp[m][k - c_{m, n}] is true, then dp[n][k] is true. Since c_{m, n} is constant, then we can simulate all k together with a bitset by getting the Bitwise Or of dp[m] shifted to the left by c_{m, n} with the current dp[n] for each m.

Time Complexity: \mathcal{O}(\frac{N^4}{W}) where W is the word size. In our case, W=64.

Subtask 4

Note that we have \mathcal{O}(N^3) states, so we cannot compute all the states if we want to solve for N \le 1000. We want to find some structure of dp[i][*] that allows us to compute less states. Define mn[i] to be minimal such that dp[i][mn[i]] = true, define mx[i] to be the maximal such that dp[i][mx[i]]=true, define b[i] to be the maximal such that \forall mn[i] \le j \le b[i], dp[i][j] = true. We can calculate mn[i], mx[i], in \mathcal{O}(N^2) time. Define seg[i] \subseteq [mn[i],b[i]] recursively as seg[1] = [0,0] and seg[i] = \cup_{j=1}^{i-1} seg[j]+c_{j,i}. We claim that \frac{|seg[i]|}{mx[i]-mn[i]+1} is large (>0.9) for large N. Some intuition for this is: seg[i] \supseteq seg[i-1]+(c_{i-1,i} \in \{0,1\}), seg[i] will be extended if there exists j such that mn[j]+c_{j,i} \le \max(seg[i]) and \max(seg[j])+c_{j,i} > \max(seg[i]). Since c_{j,i} - c_{j-1,i} is bounded by i, and seg[j] is large for j<i by induction, such a segment must exist.

Once we have that seg[i] is large, for N \le 1000, we can only compute states dp[n][k] where k > \max(seg[n]), which turns out to be very few states for N \le 1000, but this is not enough for full points.

Subtask 5

Note that since we are only considering states where k is very large, the number of j that we can transition to from i is very small. For each i, we can precompute the order in which we can transition to j for all 1 \le j < i in \mathcal{O}(N^2 \log N) time. Then, when solving for dp[i][k], we can binary search for the first j in the order that we can transition to, instead of looping over all possible transitions. With these observations, we compute far less states than in the Subtask 4 solution, and compute each state much faster, allowing us to solve for N \le 5000.

If you have a proof or countercase for this solution, feel free to put it in the comments.


There are no comments at the moment.