You are not logged in. Please login at www.codechef.com to post your questions!

×

TWOTOWER-editorial

PROBLEM LINK:

Practice

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.

This question is marked "community wiki".

asked 05 Jun '18, 21:02

megabidoof's gravatar image

6★megabidoof
1
accept rate: 0%

edited 19 Jun '18, 11:44

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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