Editorial for DMOPC '17 Contest 4 P4 - Cops and Robbers

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.

Author: r3mark

For the first subtask, choose the unassigned bank guarded for the most unassigned days and rob it on an unassigned day when it is unguarded. Continue repeating this process until all banks have been robbed. This greedy algorithm will always find a solution as long as a single bank isn't guarded every day, in which case the program should output $-1$ ~-1~. It's important that the unassigned bank is based on the most unassigned days and not all days.

Time Complexity: $\mathcal O(N^2)$ ~\mathcal O(N^2)~

For the second subtask, there are two approaches. The first is to use a priority queue and set to implement the $\mathcal O(N^2)$ ~\mathcal O(N^2)~ greedy solution in $\mathcal O(N \log N)$ ~\mathcal O(N \log N)~.

For the second approach, let $S$ ~S~ be the set of banks which is guarded at least once. If $|S|=1$ ~|S|=1~, then a single bank is guarded every day and the program should output $-1$ ~-1~. Otherwise, list the elements of $S$ ~S~. For each element in $S$ ~S~, the first time the cop guards that bank, you should rob the bank before it in the list. Clearly, the bank before it in the list will be different from it. Now note that after doing this, you've robbed from all the banks which are ever guarded. So for the remaining banks, you can rob them arbitrarily.

For example, if the input is:

6
2 1 4 2 1 1

then $S$ ~S~ is $\{1, 2, 4\}$ ~\{1, 2, 4\}~. Then the element before $2$ ~2~ is $1$ ~1~, before $1$ ~1~ is $4$ ~4~, and before $4$ ~4~ is $2$ ~2~.

2 1 1 2 4 1
1 4 ? ? 2 ?

Then we fill the question marks with the remaining banks.

2 1 1 2 4 1
1 4 3 5 2 6

Time Complexity: $\mathcal O(N)$ ~\mathcal O(N)~

Comments

0

faraz123 commented on April 11, 2021, 8:38 p.m.

What does |S| mean in this context?

0

Averesoft commented on April 11, 2021, 9:03 p.m.

$|S|$ ~|S|~ represents the size of set $S$ ~S~.