PROBLEM LINK:
Author: sathu19
Tester: sathu19
Editorialist: sathu19
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Dynamic Programming, Binary Search
EXPLANATION:
Consider the arrangement 10, 163, 89, 5, 73, 15, 49. To get the final arrangement in ascending form, we need to move blocks 73, 89, 10 and 163. If you observe carefully the remaining blocks 5, 15 and 49 form an increasing subsequence. In fact, this is the longest increasing subsequence. The minimum number of blocks to be moved to form an ascending arrangement will always be N - (the length of the longest increasing subsequence).
For the descending arrangement, we should find the length of the longest decreasing subsequence. Considering the previous example, the unmoved blocks in the descending arrangement are 163, 89, 73, 15 or 163, 89, 73 , 49. The length of the longest decreasing subsequence is 4, i.e the minimum number of blocks to be moved in this case is 3. Hence, Sriram’s arrangement will be used in this case.
To find the longest increasing/decreasing subsequence it takes time complexity O(N^2) through the dynamic programming solution. Since N can go upto 10^5, a solution with this approach would not pass within the given time limit of 1 second. However, we only require the length of the longest increasing/decreasing subsequence. Finding the length of the longest increasing/decreasing subsequence takes time complexity O(Nlog(N)). Please refer to this link for the algorithm to find the length of the longest increasing subsequence. To find the length of the longest decreasing subsequence, we just reverse the array and apply the above algorithm again.
AUTHOR’S SOLUTION:
Author’s solution can be found here.