Editorial for WC '18 Contest 2 S4 - Car Convergence Chaos
Submitting an official solution before solving the problem yourself is a bannable offence.
Given a pair of starting intersections and , with , let be the number of intersections which each car will visit (). Let be the times at which Ethan would arrive at each of the intersections on his path (such that , , , and so on). Similarly, let be Solomon's sequence of arrival times. Then, let be a sequence of differences between these arrival times (such that ). If we were to remove all 's from , then the CCCC would be equal to the number of elements in which either have no preceding element, or have a different sign than their preceding element. If we consider each pair independently, computing its sequence and resulting CCCC value in this fashion would take time, which would result in an algorithm overall. We'll need to do better than that to obtain full marks.
Let's consider each possible bomb intersection , and let's imagine for the moment that Ethan and Solomon are each driving away from it rather than towards it. We'll define a similar set of sequences to the ones described above. Let be the time at which Ethan would arrive at the -th intersection when driving left from (such that , , , and so on). Similarly, let be the time at which Solomon would arrive at the -th intersection when driving right from , and let . We can now make the key insight that, for any , is similar to — just reversed (which is irrelevant), and shifted by subtracting from each of its values (such that ends up being equal to ).
One way of thinking about the CCCC of a given sequence is that it's equal to the number of times that it "crosses" (the number of times which there's a positive value followed by zero or more 's followed by a negative value, or vice versa), plus if the sequence has at least non-zero value. And by the same token, the CCCC of a given sequence is then the number of times that it "crosses" . For example:
- The CCCC of is (as its values are all equal to )
- The CCCC of is (as is crossed by , and not all of its values are equal to )
- The CCCC of is (as is crossed by , and not all of its values are equal to )
- The CCCC of is (as not all of its values are equal to )
We can represent a sequence as a set of intervals of crossed values, based on pairs of adjacent elements. For example, if , then all values in the exclusive intervals , , , and are crossed (in other words, in the inclusive intervals , , and ). Furthermore, if we exclude intervals with both endpoints equal (of the form ), then if two intervals in a row go in the same direction (either both are increasing or both are decreasing), then their joining value is also crossed. In this example, and satisfy this property, meaning that is also crossed. However, and don't, meaning that is not crossed.
With this representation, we're ready to compute all of the CCCCs for a given bomb intersection efficiently. We'll start by iterating outwards from it in both directions to compute its full sequence in time. We'll then compress the original values in down to values , where is the number of distinct values in (such that is in ), in time. We'll proceed to iterate upwards from to while maintaining information about intervals of crossed values — specifically, we'll use a binary indexed tree to maintain an array in which is the difference between the number of intervals starting at and ending at (such that the sum of is then the number of intervals spanning ). For each , we'll query for the number of intervals so far which encompass in order to compute the CCCC of (in other words, the CCCC of the pair ), and we'll then insert at most intervals based on . In total, this process takes time per bomb intersection , resulting in an overall time complexity of .
Comments