×

TWOTOWER-editorial

Author: sathu19
Tester: sathu19
Editorialist: sathu19

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.

This question is marked "community wiki".

1
accept rate: 0%

19.8k350498541

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×2,214
×1,723
×1,056
×16
×2

question asked: 05 Jun '18, 21:02

question was seen: 282 times

last updated: 19 Jun '18, 11:44