Editorial for WC '18 Contest 2 S4 - Car Convergence Chaos


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.

Given a pair of starting intersections E and S, with M = \frac{E+S}{2}, let K be the number of intersections which each car will visit (K = M-S+1). Let X_{1 \dots K} be the times at which Ethan would arrive at each of the intersections on his path (such that X_1 = 0, X_2 = T_S, X_3 = T_S+T_{S+1}, and so on). Similarly, let Y_{1 \dots K} be Solomon's sequence of arrival times. Then, let D_{1 \dots K} be a sequence of differences between these arrival times (such that D_i = X_i-Y_i). If we were to remove all 0's from D_{1 \dots K}, then the CCCC would be equal to the number of elements in D which either have no preceding element, or have a different sign than their preceding element. If we consider each (E, S) pair independently, computing its D sequence and resulting CCCC value in this fashion would take \mathcal O(K) time, which would result in an \mathcal O(N^3) algorithm overall. We'll need to do better than that to obtain full marks.

Let's consider each possible bomb intersection M, 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 X'_i be the time at which Ethan would arrive at the i-th intersection when driving left from M (such that X'_1 = 0, X'_2 = T_M, X'_3 = T_M+T_{M-1}, and so on). Similarly, let Y'_i be the time at which Solomon would arrive at the i-th intersection when driving right from M, and let D'_i = X'_i-Y'_i. We can now make the key insight that, for any K, D_{1 \dots K} is similar to D'_{1 \dots K} — just reversed (which is irrelevant), and shifted by subtracting D'_K from each of its values (such that D_1 ends up being equal to 0).

One way of thinking about the CCCC of a given sequence D_{1 \dots K} is that it's equal to the number of times that it "crosses" 0 (the number of times which there's a positive value followed by zero or more 0's followed by a negative value, or vice versa), plus 1 if the sequence has at least 1 non-zero value. And by the same token, the CCCC of a given sequence D'_{1 \dots K} is then the number of times that it "crosses" D'_K. For example:

  • The CCCC of D' = [3, 3, 3] is 0 (as its values are all equal to 3)
  • The CCCC of D' = [1, 3, 2] is 2 (as 2 is crossed by 1 \to 3, and not all of its values are equal to 2)
  • The CCCC of D' = [1, 2, 2, 3, 2] is 2 (as 2 is crossed by 1 \to 2 \to 2 \to 3, and not all of its values are equal to 2)
  • The CCCC of D' = [1, 2, 2, 1, 2] is 1 (as not all of its values are equal to 2)

We can represent a D' sequence as a set of intervals of crossed values, based on pairs of adjacent elements. For example, if D' = [5, 10, 10, 15, 12], then all values in the exclusive intervals (5, 10), (10, 10), (10, 15), and (12, 15) are crossed (in other words, in the inclusive intervals [6, 9], [11, 14], and [13, 14]). Furthermore, if we exclude intervals with both endpoints equal (of the form (x, x)), 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, 5 \to 10 and 10 \to 15 satisfy this property, meaning that 10 is also crossed. However, 10 \to 15 and 15 \to 12 don't, meaning that 15 is not crossed.

With this representation, we're ready to compute all of the CCCCs for a given bomb intersection M efficiently. We'll start by iterating outwards from it in both directions to compute its full D' sequence in \mathcal O(N) time. We'll then compress the original values in D' down to values 1 \dots C, where C is the number of distinct values in D' (such that C is in \mathcal O(N)), in \mathcal O(N \log N) time. We'll proceed to iterate i upwards from 1 to |D'| while maintaining information about intervals of crossed values — specifically, we'll use a binary indexed tree to maintain an array A in which A_x is the difference between the number of intervals starting at and ending at x (such that the sum of A_{1 \dots x} is then the number of intervals spanning x). For each i, we'll query for the number of intervals so far which encompass D'_i in order to compute the CCCC of D'_{1 \dots i} (in other words, the CCCC of the (S, E) pair (M-(i-1), M+(i-1))), and we'll then insert at most 2 intervals based on D'_i. In total, this process takes \mathcal O(N \log N) time per bomb intersection M, resulting in an overall time complexity of \mathcal O(N^2 \log N).


Comments

There are no comments at the moment.