Editorial for CCC '24 S3 - Swipe
Submitting an official solution before solving the problem yourself is a bannable offence.
Subtask 1
Since , 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 , or swipe right on . After swipe, additional swipes will not change the array , as both elements of will be the same. Thus, we can try all possible moves, and check if array becomes . 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 twice. If we are able to reach array , then we print out the sequence of swipes and return. As , with careful implementation, this should pass comfortably in time.
Subtask 3 and 4
Let be the "compressed" version of , where all adjacent equal elements of are removed. Then, the
answer is YES
if and only if is a sub-sequence of .
To see why this is the case, notice that intersecting a necessary left swipe with a necessary right swipe will overwrite valuable elements. Take and as an example. In order to make the first element a , we must swipe left and we get . However, we cannot make the second element a now, as the has been overwritten. A similar argument follows if we first try to swipe right. Thus, it is impossible for array to turn into . When is not a sub-sequence of , 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 through each element of , and increment while is equal to . 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 time, which is sufficient for full marks. Subtask was meant for suboptimal implementations of the full solution.
Comments