TopCoder problem "BridgeArrangement" used in TCO04 Round 4 (Division I Level Three)



Problem Statement

    

Bridge is a card game in which you are dealt a collection of cards, called a hand. You pick up your hand and hold it so that you can see the fronts of your cards but other players can only see the backs. You are free to arrange the cards in any order, but deciding on a good arrangement is not always straightforward. You could sort them, but that might give your opponents too many clues. For example, if you pull out the leftmost card, they might be able to guess that the card is either your lowest or your highest in that suit. You could leave the hand completely unsorted, but most people find it too difficult to keep track of their cards that way.

A good compromise between security and ease of use is to group the cards by suit, arrange the suits in alternating colors, and leave the cards within each suit unsorted. More precisely, an arrangement of cards is deemed valid if and only if

  • no two cards of the same suit are separated by a card of a different suit,
  • no two cards of the same color but different suits are adjacent (unless no cards of the opposite color are present in the hand), and
  • no suit with more than two cards is arranged in either increasing or decreasing order.
In the second condition, recall that clubs ('C') and spades ('S') are black, while diamonds ('D') and hearts ('H') are red. For example, the hand 

  2C KC 4C 5H 3H 2H AH QS KS 6D TD 9D JD
is valid, but none of the following hands are valid: 
  2C KC 5H 4C 3H 2H AH QS KS 6D TD 9D JD  (a heart is between two clubs)
  2C KC 4C 5H 3H 2H AH 6D TD 9D JD QS KS  (hearts and diamonds are adjacent)
  2C KC 4C 5H 3H 2H AH QS KS 6D 9D TD JD  (diamonds are sorted in increasing order)
  2C KC 4C AH 5H 3H 2H QS KS 6D TD 9D JD  (hearts are sorted in decreasing order)
Notice that, in all of these examples, the spades are allowed to be in increasing order because there are only two of them. Also, notice that aces are considered high, so "5H 3H 2H AH" is not in decreasing order, but "AH 5H 3H 2H" is.

When arranging your hand, you move cards one at a time by pulling them out of their current positions and reinserting them at other positions. Given a hand, you are to calculate and return the minimum number of moves necessary to achieve a valid arrangement. The hand will be represented by a String[] cards. Each element of cards represents a separate card as a two-character string of the form <rank><suit>. The possible ranks, listed in increasing order, are {'2'-'9','T','J','Q','K','A'}. The possible suits are {'C','D','H','S'}. For example, the jack of hearts would be written "JH".

 

Definition

    
Class:BridgeArrangement
Method:minMoves
Parameters:String[]
Returns:int
Method signature:int minMoves(String[] cards)
(be sure your method is public)
    
 

Notes

-In real bridge, a hand always starts with 13 cards, but in this problem, a hand might be bigger or smaller than that.
 

Constraints

-cards contains between 3 and 50 elements, inclusive.
-Each element of cards contains exactly two characters, in the format described above.
-cards contains no duplicate elements.
 

Examples

0)
    
{ "2C", "KC", "4C", "5H", "3H", "2H", "AH", "QS", "KS", "6D", "TD", "9D", "JD" }
Returns: 0
The example of a valid hand from above. No cards need to be moved.
1)
    
{ "2C", "3C", "8C", "TC", "KC", "AC" }
Returns: 1
Here you only have one suit, but it is sorted. You can make the suit unsorted by moving the 2 to the other side of the 3. Many other moves would work equally well.
2)
    
{ "9S", "AS", "2S", "JH", "TH", "KH", "3D", "QD", "5D", "AC", "6C" }
Returns: 2
The cards have been grouped by suits, but the suits do not alternate in color. This can be fixed by moving the clubs between the hearts and diamonds.
3)
    
{ "3C", "7S", "5C", "5S", "8C", "2S", "TC" }
Returns: 3
The black suits are permitted to be adjacent when there are no red cards in the hand.
4)
    
{ "5D", "5C", "KH", "7C", "3C", "7D", "4D", "KC", "AS", "AD",
  "7H", "AC", "9C", "8H", "4C", "8S", "KS", "QD", "5S", "JC",
  "KD", "9D", "JD", "JH", "8D", "JS", "QH", "2S", "3H", "QC",
  "9S", "2C", "3S", "TS", "4H", "6D", "7S", "TC", "6C", "4S",
  "3D", "2H", "9H", "6H", "8C", "AH", "6S", "2D", "QS", "TH" }
Returns: 26

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2967

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5881&pm=2967

Writer:

vorthys

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Dynamic Programming