Scooter
Contest: European Championship 2024 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2300
Tags: graphs, greedy

The Czech Technical University campus consists of $$$n$$$ buildings, indexed from $$$1$$$ to $$$n$$$. In each building, there can be a math class scheduled, or a computer science class, or neither (but not both). Additionally, in each building, there is at most one professor, and each professor is either an expert in mathematics or in computer science.

As an intern at University Express Inc., your job is to quickly transport the professors to their classes. For this, you have been granted a brand new two-person scooter, able to accommodate yourself, plus at most one passenger.

Initially, you are the only person on the scooter. When you arrive at a building, you may drop off or pick up professors to/from that building. However, in order to improve the efficiency of your task, you are allowed to drive to each of the $$$n$$$ buildings at most once, in the order of your choice (you can also decide where to start the itinerary).

After the end of your itinerary, in each building where a math class is scheduled, there must be a professor expert in math, and in each building where a computer science class is scheduled, there must be a professor expert in computer science.

Devise an itinerary that makes it possible to teach all classes.

Input format:
The first line contains an integer $$$n$$$ ($$$1\le n \le 2000$$$) — the number of buildings in the campus.

The second line contains a string of $$$c$$$ of length $$$n$$$ consisting of the characters $$$\texttt{-}$$$, $$$\texttt{C}$$$, $$$\texttt{M}$$$ — the $$$i$$$-th character denotes the subject of the class scheduled in the $$$i$$$-th building. $$$\texttt{C}$$$ stands for computer science, $$$\texttt{M}$$$ stands for mathematics, while $$$\texttt{-}$$$ means that there is no class scheduled in the $$$i$$$-th building.

The third line contains a string $$$p$$$ of length $$$n$$$ consisting of the characters $$$\texttt{-}$$$, $$$\texttt{C}$$$, $$$\texttt{M}$$$ — the $$$i$$$-th character denotes the expertise of the professor in the $$$i$$$-th building (if there is a professor). $$$\texttt{C}$$$ stands for computer science, $$$\texttt{M}$$$ stands for mathematics, while $$$\texttt{-}$$$ means that there is no professor in the $$$i$$$-th building.

It is guaranteed that, for all tests given to your program, there exists a valid itinerary.

Output format:
In the first line print an integer $$$l$$$ — the number of operations in your chosen itinerary.

The $$$i$$$-th ($$$1 \leq i \leq l$$$) of the next $$$l$$$ lines must contain one of three commands:

1. $$$\texttt{DRIVE } x$$$ — go to the building with the number $$$x$$$ ($$$1 \leq x \leq n$$$);
2. $$$\texttt{PICKUP}$$$ — pick up the professor which was initially at the current building;
3. $$$\texttt{DROPOFF}$$$ — drop off the passenger professor at the current building.

In order for the itinerary to be valid, the following conditions must hold:

1. No two $$$\texttt{DRIVE}$$$ instructions should go to the same building;
2. At most one $$$\texttt{DROPOFF}$$$ and one $$$\texttt{PICKUP}$$$ instruction in this order should be issued at each specific building;
3. For all $$$\texttt{PICKUP}$$$ instructions, there must be a professor initially at the building, as well as no one already riding along on the scooter;
4. For all $$$\texttt{DROPOFF}$$$ instructions, there must be a professor riding along at the time of the command;
5. After the itinerary, in each building, if there is a class in that building, there must be a professor expert in the class' subject (either initially, or because they were dropped off there).

Note that, in particular, you cannot pick up a professor that you just dropped off for an itinerary to be valid.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first sample, You start by driving to building number $$$3$$$. You then pick up the mathematics professor. After dropping him off at building number $$$2$$$, where a mathematics class is being held, you pick up the computer science professor from there, and drop her off at building number $$$1$$$, finishing your itinerary.

Example input:
3
CM-
-CM

Example output:
7
DRIVE 3
PICKUP
DRIVE 2
DROPOFF
PICKUP
DRIVE 1
DROPOFF

Example input:
1
C
C

Example output:
0

Editorial:
First and foremost, let's notice that we can ignore professors that are already in a proper building, as well as empty buildings (in essence, all positions $$$i$$$ such that $$$c_i = p_i$$$).
More so, if there are no positions $$$i$$$ such that $$$c_i \neq p_i$$$ then we can simply answer $$$\texttt{YES}$$$ without doing any operations.
From this point on, we will assume that for all $$$i$$$, we have $$$c_i \neq p_i$$$.
General idea. Intuitively, we would want to iteratively pick up the professor from some building and drive them to a building where a corresponding class is held. However, we must make sure to not visit the same place twice. Multiple greedy solutions might solve this, but we also have to take into account implementation effort and the number of edge cases to consider. In this sense, we advise the reader to not rush into writing an implementation just yet, and instead try to simplify the solution as much as possible on paper.
An easier subproblem. The issue with the problem currently is that there is much room for making choices and, consequently, much room for making an erroneous decision. Let's consider the easier subproblem where there are exactly as many professors of a given class types as there are classes. Even though one might say that this makes the problem tighter, it actually paradoxically makes it easier! This is mainly because, as tight as it is, there is not much room for bad decisions.
A key observation is that this subproblem (and, as it turns out, the original problem as well) is $$$\textbf{impossible}$$$ if there are no buildings where no class is being held, as there is simply no way of returning to the starting position to drop off the corresponding professor (note, again, that we are ignoring positions $$$i$$$ with $$$c_i = p_i$$$).
Therefore, a greedy strategy that works for this subproblem is simply repeatedly choosing a professor from a building where no class is being held and driving them to one of the buildings where their class is being held. If one prioritizes buildings where there are professors before those where there are no professors, the key condition never becomes unsatisfied, thus the problem is solved.
Solving the original problem. Going back, let's solve the original problem. We can do that by simply reducing it to the easier version, by removing "excess" professors from some of the buildings. At the same time, note that we have to make sure the key observation above remains valid throughout the removal process. One easy and correct way of doing that is, yet again, the greedy approach of simply prioritizing removing professors from buildings where there are classes to buldings with no classes.
Final complexity of the solution is $$$\mathcal{O}(n)$$$.