Editorial for CCC '24 S3 - Swipe


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.

Subtask 1

Since N = 2, we can use casework on all possible cases. Alternatively, note that the only moves that can be made are to do nothing, swipe left on [0, 1], or swipe right on [0, 1]. After 1 swipe, additional swipes will not change the array A, as both elements of A will be the same. Thus, we can try all possible moves, and check if array A becomes B. Otherwise, the answer will be NO.

Subtask 2

The intended solution for this subtask is to iteratively brute force all possible arrays by trying all possible swipes at each step. This can be implemented similarly to BFS, with a visited map, to ensure we don't visit the same array A twice. If we are able to reach array B, then we print out the sequence of swipes and return. As N \le 8, with careful implementation, this should pass comfortably in time.

Subtask 3 and 4

Let B^{\prime} be the "compressed" version of B, where all adjacent equal elements of B are removed. Then, the answer is YES if and only if B^{\prime} is a sub-sequence of A.

To see why this is the case, notice that intersecting a necessary left swipe with a necessary right swipe will overwrite valuable elements. Take A = [1, 2] and B = [2, 1] as an example. In order to make the first element a 2, we must swipe left and we get A = [2, 2]. However, we cannot make the second element a 1 now, as the 1 has been overwritten. A similar argument follows if we first try to swipe right. Thus, it is impossible for array A to turn into B. When B^{\prime} is not a sub-sequence of A, there will inevitably be a case where a necessary left swipe intersects a necessary right swipe, which makes it impossible.

To construct the solution, we employ a 2-pointers approach. Iterate i through each element of A, and increment j while A_i is equal to B_j . This will capture the range of elements that we need to swipe across.

We push all left swipes into a list of swipes left, and right swipes into a list of swipes right. Notice that left swipes should be performed in increasing order of right endpoints, while right swipes should be performed in decreasing order of left endpoints, so that valuable elements will not get overwritten. Thus, we can push the reversed right into left to get the correct order of swipes.

This solution runs in \mathcal{O}(N) time, which is sufficient for full marks. Subtask 3 was meant for suboptimal implementations of the full solution.


Comments

There are no comments at the moment.