MCARDS  Card Sorting
English  Vietnamese 
Dave’s little son Maverick likes to play card games, but being only four years old, he always lose when playing with his older friends. Also, arranging cards in his hand is quite a problem to him.
When Maverick gets his cards, he has to arrange them in groups so that all the cards in a group are of the same color. Next, he has to sort the cards in each group by their value – card with lowest value should be the leftmost in its group. Of course, he has to hold all the cards in his hand all the time.
He has to arrange his cards as quickly as possible, i.e. making as few moves as possible. A move consists of changing a position of one of his cards.
Write a program that will calculate the lowest number of moves needed to arrange cards.
Input
The first line of input file contains two integers C, number of colors (1 ≤ C ≤ 4), and N, number of cards of the same color (1 ≤ N ≤ 100), separated by a space character.
Each of the next C*N lines contains a pair of two integers X and Y, 1 ≤ X ≤ C, 1 ≤ Y ≤ N, separated by a space character.
Numbers in each of those lines determine a color (X) and a value (Y) of a card dealt to little Maverick. The order of lines corresponds to the order the cards were dealt to little Maverick. No two lines describe the same card.
Output
The first and only line of output file should contain the lowest number of moves needed to arrange the cards as described above.
Sample
CARDS.IN 2 2 2 1 1 2 1 1 2 2 CARDS.OUT 2 CARDS.IN 4 1 2 1 3 1 1 1 4 1 CARDS.OUT 0 CARDS.IN 3 2 3 2 2 2 1 1 3 1 2 1 1 2 CARDS.OUT 2
hide comments
akj698:
20190126 12:58:59
a must do DP Problem 

anshuman16423:
20181206 14:24:07
Must try if learning Dynamic Programming


shubham_04_04:
20181020 12:43:41
Feeling good after new learning 

supriyanta:
20180822 23:32:28
Nice problem! 

Simes:
20180525 15:11:17
Hey @imkiller, why do you keep posting links to your code after you solve a problem? Not good imho.


alexyu:
20171221 03:22:50
Last edit: 20171221 03:31:09 

mastik5h_1998:
20170929 08:54:05
never used LIS like this before


singh1495:
20170207 11:44:05
took time but interesting question, best implementation of LIS 

melzarei:
20160703 18:40:35
Interesting problem , learnt alot


Sahil Dua:
20141108 09:59:13
What a question! DP + Permutations! Awesome :D 
Added by:  ~!(*(@*!@^& 
Date:  20090313 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  COI 01 