Connection Status:
Competition Arena > TwoSidedCards

TwoSidedCards

SRM 472 · 2009-11-12 · by rng_58

SRM 472 · 2009-11-12 · by rng_58 · Graph Theory, Math
Class Name: TwoSidedCards
Return Type: int
Method Name: theCount
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

There are N cards which are initially blank. First, Taro writes a distinct number between 1 and N, inclusive, on the front side of each card. The number he writes on the i-th card is taro[i]. Then, Hanako turns over all the cards and writes a distinct number between 1 and N, inclusive, on the back side of each card. The number she writes on the i-th card is hanako[i].

Now you must determine the number of distinct ways that the N cards can be arranged in a row. The cards can be placed in any order and each card can be oriented so that either its front side or back side is displayed. Two arrangements are considered distinct if the i-th card in the row shows a different number in one arrangement than it does it in the other. Return the number of distinct possible arrangements, modulo 1,000,000,007.

Constraints

  • N will be between 1 and 50, inclusive, where N is the number of elements in taro.
  • Each element of taro will be between 1 and N, inclusive.
  • taro will contain no duplicate elements.
  • hanako will contain exactly N elements.
  • Each element of hanako will be between 1 and N, inclusive.
  • hanako will contain no duplicate elements.
Examples
0)
{1, 2, 3}
{1, 3, 2}
Returns: 12

If the front side of each card is displayed, the cards will be (1,2,3), and you can get (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1) by changing the order. If the back side of the second card is displayed, the cards will be (1,3,3), and you can get (1,3,3), (3,1,3), (3,3,1) by changing the order. If the back side of the third card is displayed, the cards will be (1,2,2), and you can get (1,2,2), (2,1,2), (2,2,1) by changing the order. If the back sides of both the second and third cards are displayed, the cards will be (1,3,2), and you can get (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1) by changing the order. In total, there are 12 possibilities: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1), (1,3,3), (3,1,3), (3,3,1), (1,2,2), (2,1,2), (2,2,1).

1)
{1, 2, 3}
{1, 2, 3}
Returns: 6

You can make 123, 132, 213, 231, 312, 321.

2)
{1, 2}
{2, 1}
Returns: 4

You can make 11, 12, 21, 22.

3)
{5, 8, 1, 2, 3, 4, 6, 7}
{1, 2, 3, 4, 5, 6, 7, 8}
Returns: 2177280
4)
{41, 22, 17, 36, 26, 15, 10, 23, 33, 48, 49, 9, 34, 6, 21, 2, 46, 16, 25, 3, 24, 13, 40, 37, 35,
50, 44, 42, 31, 12, 29, 7, 43, 18, 30, 19, 45, 32, 39, 14, 8, 27, 1, 5, 38, 11, 4, 20, 47, 28}
{19, 6, 23, 35, 17, 7, 50, 2, 33, 36, 12, 31, 46, 21, 30, 13, 47, 22, 44, 4, 25, 24, 3, 15, 20,
48, 10, 28, 26, 18, 5, 45, 49, 16, 40, 42, 43, 14, 1, 37, 29, 8, 41, 38, 9, 11, 34, 32, 39, 27}
Returns: 529165844

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

Coding Area

Language: C++17 · define a public class TwoSidedCards with a public method int theCount(vector<int> taro, vector<int> hanako) · 71 test cases · 2 s / 256 MB per case

Submitting as anonymous