Connection Status:
Competition Arena > TheCardLineDivTwo

TheCardLineDivTwo

SRM 448 · 2009-09-10 · by Vasyl[alphacom]

SRM 448 · 2009-09-10 · by Vasyl[alphacom] · Dynamic Programming
Class Name: TheCardLineDivTwo
Return Type: int
Method Name: count
Arg Types: (vector<string>)
Problem Statement

Problem Statement

John and Brus are training for a card game tournament. During his off-time, Brus likes to occupy himself with the following game. The game is played with a subset of a standard deck of 52 distinct cards. Each card can be represented by a two-character string, where the first character is the rank ('2'-'9', 'T', 'J', 'Q', 'K', or 'A') and the second character is the suit ('S' for Spades, 'C' for Clubs, 'D' for Diamonds or 'H' for Hearts). All Spades and Clubs are black, and all Diamonds and Hearts are red. For example, the Jack of Spades is black and is represented as "JS", and the Nine of Hearts is red and is represented as "9H".

You are given a String[] cards containing the subset of the deck that Brus is playing with. Each element of cards represents a single card. He wants to place all of these cards in a line such that every pair of neighboring cards has the same rank or the same color (or both). Return the number of different ways he can do this modulo 1234567891.

Constraints

  • cards will contain between 1 and 16 elements, inclusive.
  • Each element of cards will contain exactly two characters, where the first character is '2'-'9', 'T', 'J', 'Q', 'K' or 'A', and the second character is 'S', 'C', 'D' or 'H'.
  • All elements of cards will be distinct.
Examples
0)
{"KH", "QD", "KC"}
Returns: 2

There are two possible placements - KC-KH-QD and QD-KH-KC.

1)
{"JS", "JC", "JD", "JH"}
Returns: 24

All 24 permutations are valid.

2)
{"2S", "3C", "4C", "5S", "6C", "7S", "8S", "9H"}
Returns: 0

There is nothing we can do with the Nine of Hearts.

3)
{"KD", "KC", "AD", "7C", "AH", "9C", "4H", "4S", "AS"}
Returns: 2416
4)
{"8S"}
Returns: 1

Submissions are judged against all 93 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TheCardLineDivTwo with a public method int count(vector<string> cards) · 93 test cases · 2 s / 256 MB per case

Submitting as anonymous