Subtask 1 [30%]

Directly simulating the problem was the intended solution. Be careful to correctly update arrows after each minute.

Time Complexity: \(O(N^{2})\)

Subtask 2 [70%]

There are several observations to make.

The first observation is to realize that if one type of arrows all end up at their respective end, then the array is sorted. For the purposes of this editorial, we will be using the < arrows.

The second observation is that arrows of the same type never swap positions. That is, the first < is always the first < - it will always end up at the very left of the array at the end. This allows us to quickly compute the ending indices of each arrow with a running sum.

The third observation is that a continuous segment of < arrows will end up giving a time penalty to the arrows further back. The first arrow has a penalty of \(0\), the second arrow has \(1\), and so on, with the \(i\)th arrow having \(i - 1\). The first three observations are enough to solve simple cases such as >>>><<.

The fourth observation is that continuous segments of < arrows that are close enough will affect each other. Arrows from a further back segment can bump into a segment in front of it. This can be calculated efficiently by treating each > arrow in between as a penalty decreaser. If there are a sufficient amount of > arrows behind a < segment, that segment will clear out by the time any new < arrow comes along. This last observation is enough to solve the entire problem.

The implementation of this is left as an exercise to the reader.

Time Complexity: \(O(N)\)

Author's Note: The solution listed above for subtask 2 is not the only valid solution. Notably, many contestants came up with different solutions. However, for the purposes of problem solving, it is best to be able to organize your solution into smaller "pieces", so that any wrong approach can be scrapped whilst retaining useful observations.