TopCoder problem "TVGame" used in SRM 379 (Division I Level Three)



Problem Statement

    A domino is a rectangular tile with a number on each end.



On a TV game show, a player is presented with a NxN board containing N^2 dominoes. The domino in row i, column j (both 1-based indices) contains the numbers i and j. The player must choose exactly N dominoes from the board such that no two dominoes are from the same column and no two are from the same row. He is then required to join all pairs of dominoes that contain the same number. For example, if he picks (1,3), (3,2), (2,4) and (4,1), he must join them all together in a cycle.



At this point, there are one or more groups of connected dominoes (a single domino counts as a group). Because the player is not allowed to choose dominoes from the same column or row, there will always be a single way to join the dominoes together.



Each domino has a hidden number on its back. Compute the product of the hidden numbers of all the selected dominoes. If there is an even number of connected domino groups, multiply this product by -1. The final product is the outcome of the game, and if it is positive, the player wins money, and if it's negative, he loses money.



You are given a String[] board containing the hidden numbers of all the dominoes on the board. The j-th character of the i-th element of board is a character representing the hidden number of the domino in row i, column j. Digits '0' to '9' represent the numbers 0 to 9. Letters 'A' to 'I' represent the numbers -1 to -9. Your task is to find the sum of every possible outcome given the hidden numbers of the dominoes. Calculate the sum of every possible outcome of the game, and return this sum modulo 121547.
 

Definition

    
Class:TVGame
Method:expectedProfit
Parameters:String[]
Returns:int
Method signature:int expectedProfit(String[] board)
(be sure your method is public)
    
 

Constraints

-board will contain between 1 and 50 elements, inclusive.
-Each element of board will contain exactly n characters, where n is the number of elements in board.
-board will contain only digits '0'-'9' and uppercase letters 'A'-'I'.
 

Examples

0)
    
{"35",
 "44"}
Returns: 8
There are two possible ways to select the dominoes:



1) Select (1,1) and (2,2). You can't join them together, so you have two groups of dominoes (each containing a single domino). The product of their hidden numbers is 3x4 = 12. Since there's an even number of groups, you then multiply by -1 to get -12.



2) Select (1,2) and (2,1). You must join these two together, so you have one connected group of dominoes. The product of their hidden numbers is 4x5 = 20.



The sum of these two possible outcomes is -12+20 = 8.
1)
    
{"00200",
 "0B000",
 "00020",
 "10000",
 "00001"}
Returns: 121539
Every choice leads to 0 earnings except (1,3), (2,2), (3,4), (4,1), (5,5). When we choose those, we get three groups of connected dominoes:

  • (1,3) - (3,4) - (4,1)
  • (2,2)
  • (5,5)
The outcome here is 2*(-2)*2*1*1 = -8. -8 mod 121547 = 121539.
2)
    
{"12A",
 "A12",
 "2A1"}
Returns: 14
There are 6 possible ways to select the dominoes, and their outcomes are: -1, 1, 2, 2, 2, 8.
3)
    
{"AAAA",
 "BBBB",
 "CCCC",
 "DDDD"}
Returns: 0
Here, no matter how we choose the dominoes, the outcome will always be either 24 or -24. It is 24 half the time, and -24 half the time, so the sum is 0.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10800&pm=8174

Writer:

asal1

Testers:

PabloGilberto , Olexiy , gawry , ivan_metelsky

Problem categories:

Advanced Math