Yet Another Unusual Sorting

Computer Science Level 5

You are tasked to sort this permutation of integers from 1 to 1000.

You are supposed to do so using the following operation (and only the following operation):

Remove an element, then insert it at any position that you choose in the list, shifting elements if necessary.

Each time this operation is done, it takes a cost of 1. What is the minimum cost of sorting this permutation?

Inspired by Unusual Sorting


The answer is 944.

Agnishom Chattopadhyay by Agnishom Chattopadhyay , 22, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Christopher Boo
Aug 13, 2016

Read @Ivan Koswara detailed explanation in this problem to understand why is it related to the longest increasing subsequence.

TL;DR : The answer is the length of the sequence minus the length of the longest increasing subsequence. We can solve this in a dynamic programming manner. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
 
L = [int(x) for x in raw_input().split(',')]

lis = [1] * len(L)

for i in range(1,len(L)):
    for j in range(0,i):
        if L[i] > L[j]:
            lis[i] = max(lis[i],lis[j]+1)

print len(L) - max(lis)

2 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...