PCJ18E - Editorial

PROBLEM LINK:

Practice
Contest

Author: Prakhar Gupta
Tester: Madhav Sainanee
Editorialist: Prakhar Gupta

DIFFICULTY:

EASY

PREREQUISITES:

None

PROBLEM:

Given an array A of N distinct elements, we can move any element to the end. Find the minimum number of moves to sort the array in ascending order.

QUICK EXPLANATION

Suppose B be the sorted version of A. Let cnt be the longest subsequence of A which is a prefix of B. The minimum number of moves are N - cnt.

EXPLANATION:

Let the original array be A and its sorted version be B.

We call two elements ordered if A_i < A_j and i < j. If they are unordered, the only way to make them ordered is to put A_i to the end, as it is the only move we are allowed.

For a sorted array, all consecutive pairs of elements are ordered.

So, we start from i = 0 in B and look at the pair of elements B_i and B_{i+1} in A. If they are not ordered, it means that B_{i+1} is coming before B_i in A. So, we have to send B_{i+1} to the end of A. This makes B_{i+1} unordered with B_{i+2}, B_{i+3} and so on.

So essentially, we exclude the elements which are already ordered from the start of B and move the others to the end.

This ultimately comes down to finding the largest prefix of B that is a subsequence of A.

This can be achieved by a map/dictionary, or an array of pairs containing the index of the element in the original array and sorting it.

Complexity: The time complexity is O(N log(N)) per test case, due to sorting.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.