CLVSTR - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Subham Das
Tester: Soumik Sarkar
Editorialist: Soumik Sarkar

DIFFICULTY:

EASY

PREREQUISITES:

Ternary search, Median

PROBLEM:

Given a sequence of 1’s and 0’s, find the minimum total number of steps required to group all the 1’s together in a consecutive chain with the difference between the initial and final position of each 1 being the number of steps it required.

QUICK EXPLANATION:

Let p be the array of positions of 1 in the sequence in increasing order. Generate array q such that q_i = p_i - i. The answer is \sum_{q_i \in q} |q_m - q_i| where q_m is the median of array q.

EXPLANATION:

First, observe that the operation we are allowed to do is swap any two adjacent numbers, but we should try to only swap 0’s and 1’s, because swapping two 0’s or swapping two 1’s is a wasted move that leads to the same state as before. This means that no two 1’s will cross each other. Once we choose a certain position, we will bring in the 1’s from the left with the closer 1’s arriving first, and the same applies to the right.

To solve this problem, first consider a similar (and quite famous) problem. Given a set of numbers S, find the minimum sum of absolute deviations possible. In other words, find the minimum value of f(x) when

f(x) = \sum_{s \in S} |x - s|

It turns out that the minimum value occurs when x the median of set S. For the intuition behind this, refer to this excellent answer.

Coming back to our problem, let p be the array of all positions of 1’s in sorted order, whose length is n. In the final state, the 1’s are in a consecutive chain. Let this chain start at position x. The first 1 in this chain is also the first 1 initially, so the number of steps it took is |x-p_0|. Generally speaking, the number of steps taken by the p_i is |x+i-p_i|. Then, the total number of steps required to reach the final state is g(x) such that

\begin{aligned} g(x) &= \sum_{i=0}^{n-1} |x + i - p_i| \\ &= \sum_{i=0}^{n-1} |x - (p_i-i)| \end{aligned}

Let us set up a new array q such that q_i = p_i-i. The solution should be obvious now, we have converted the problem into finding the minimum h(x) when

h(x) = \sum_{i=0}^{n-1} |x - q_i|

…which we already know occurs when x is the median of the array q.

Complexity of this approach is \mathcal{O}(N).

ALTERNATE APPROACH:

The minimum value of h(x) also occurs when the 1 at the median of p is not moved, and the rest of the 1’s are brought around it to form the chain. You can try proving this as an exercise :stuck_out_tongue:

ALTERNATE APPROACH 2:

It is possible to notice by being observant or having good intuition that the function h(x) is weakly unimodal. So one can use ternary search to obtain the answer in \mathcal{O}(N\ log\ N).

TESTER’S SOLUTION:

Tester’s solution can be found here.