PROBLEM LINK:
Author: Abhra Dasgupta
Tester: Kevin Atienza and Istvan Nagy
Editorialist: Kevin Atienza
PREREQUISITES:
Ad hoc
PROBLEM:
There are N distinct numbers A_1, \ldots, A_N. With a single move, you can kill any existing number X, but if X-1 and/or X+1 exists, they are killed along with X. What is the minimum and maximum number of moves needed to kill all numbers? Note that you cannot target a number X if it doesn’t exist in the list or if it has already been killed.
QUICK EXPLANATION:
First, try to sort the numbers. Now, for any maximal contiguous sequence V, V+1, \ldots, V+k-1 with k values, the minimum and maximum moves to kill them all is \lceil k/3 \rceil and \lceil k/2 \rceil, respectively. The answer is the sum of all those for all contiguous sequences.
Sorting can be done with any library comparison sort, or by using counting sort (exploiting the fact that \max_i A_i is not too large).
EXPLANATION:
First, note that the order of the input numbers do not matter in this problem, so it might make sense to sort them first. In fact, the sorted array makes our tasks a bit easier, because if one targets the number X, then X-1 and X+1 can be found beside X in the array (if they exist)!
Now, since all values are distinct, the difference between consecutive elements is either 1 or something greater than 1. Consider two adjacent numbers A and B where B - A > 1. Note that targeting B does not affect A or all numbers lower than A, and similarly targeting A does not affect B or all numbers greater than B. Therefore, we can essentially split the array into two parts: one group contains all numbers \le A and the other contains all those \ge B. Since there are no interaction between these two groups, we can essentially solve both groups separately and add the results.
In fact, you can do this splitting whenever you can find a gap larger than 1! After doing all the splits, we are left with several groups (or maybe just one) where consecutive numbers in each group have differences of 1. Thus, we can restrict our attention to only arrays with that property. In such an array, whenever you target a number X, you also kill both its neighbors, because its neighbors, if they exist, have values X-1 and X+1.
As an example, consider the sequence [1, 2, 3, 5, 6, 9, 10, 11, 15, 20]. Then after doing all the splittings, we end up with the following groups: [1, 2, 3], [5, 6], [9, 10, 11], [15], [20].
Now, what is the minimum number of moves to kill such a group with k members? Well, note that you only kill at most 3 per move. Therefore, you cannot do it in fewer than \lceil k/3 \rceil moves. But is it possible to do it in exactly \lceil k/3 \rceil moves? Yes of course, by killing every three numbers in increasing order! For example, in the group [4, 5, 6, 7, 8, 9, 10, 11] we target 5, 8 and 11. Thus, we have shown that the minimum number is \lceil k/3 \rceil.
But what is the maximum number of moves? Well, note that you cannot target two adjacent numbers separately, because whenever you target one you automatically kill the other. Therefore, you cannot exceed \lceil k/2 \rceil moves. But is it possible to do it in exactly \lceil k/2 \rceil moves? Yes, by targeting every other number! For example, in the group [5, 6, 7, 8, 9, 10, 11] we target 5, 7, 9 and 11. Thus, we have shown that the maximum number is \lceil k/2 \rceil 
Time Complexity:
O(N \log N) or O(N+M) where M = \max_i A_i