## 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

For every segment between and , we can either direct from to or we can direct it from to . This means that every segment has two different states. So, we can try all different configuration and find the minimal one. We can find the number of pairs for each configuration in time.

Time complexity: 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. will be a boolean. is true when it is possible to get pairs among the first friends and false otherwise. To find the whether is true or not we can try to consider every suffix where is a contiguous segment described above. So, we have where is the number of pairs of the same element in the subarray . We can quickly compute by adding the number of other elements that is equal to in to . This can be done quickly by having a frequency array. Thus, it is possible to have states and transition.

Time Complexity: Note that for a fixed and , then for all , if is true, then is true. Since, is constant, then we can simulate all together with a bitset by getting the Bitwise Or of shifted to the left by with the current for each .

Time Complexity: where is the word size. In our case, .

Note that we have states, so we cannot compute all the states if we want to solve for . We want to find some structure of that allows us to compute less states. Define to be minimal such that , define to be the maximal such that , define to be the maximal such that , . We can calculate , , in time. Define recursively as and . We claim that is large for large . Some intuition for this is: , will be extended if there exists such that and . Since is bounded by , and is large for by induction, such a segment must exist.

Once we have that is large, for , we can only compute states where , which turns out to be very few states for , but this is not enough for full points.

Note that since we are only considering states where is very large, the number of that we can transition to from is very small. For each , we can precompute the order in which we can transition to for all in time. Then, when solving for , we can binary search for the first 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 . Let be the number of states we visit, and be the number of such that we visit a state :