MovingTokens | Topcoder Archive

Problem Statement

Fox Ciel is going to play a game with tokens. She has n bins, numbered 0 through n-1. At the beginning of the game each bin contains a single token. During the game each bin may contain arbitrarily many tokens.

Fox Ciel also has a rectangular matrix M with n rows and m columns. You are given the ints n and m. You are also given a int[] moves that encodes the content of M. For each i from 0 to n-1, inclusive, and for each j between 0 and m-1, inclusive, M[i][j] = moves[j*n+i].
The matrix M describes the valid moves Ciel can make in the game. Each turn of the game looks as follows:

Ciel chooses the value of j: an integer between 0 and m-1.
For each i between 0 and n-1, inclusive, Ciel moves all tokens from bin i into bin M[i][j].

Note that all movement in step 2 occurs simultaneously. For example, if she wants to move all tokens from bin 0 to bin 1 and all tokens from bin 1 to bin 0, the bins 0 and 1 swap their content.
The game Fox Ciel plays consists of exactly 10^100 turns, each of the form described above. Her goal is to minimize the number of bins that contain some tokens at the end of the game. Calculate the best possible result she can obtain. In other words, return the smallest K such that Ciel can play the game in such a way that at the end of the game only K of the bins contain some tokens.

Definition

Class:: MovingTokens
Method:: move
Parameters:: int, int, int[]
Returns:: int
Method signature:: int move(int n, int m, int[] moves)
(be sure your method is public)

Constraints

n will be between 1 and 50 inclusive.
m will be between 1 and 50 inclusive.
moves will contain exactly n * m elements.
Each element of moves will be between 0 and n-1.

Examples

```
2
```
```
2
```
```
{0,1,
0,1}
```
```
Returns: 2
```
There are two bins. At the beginning of the game, each bin contains a token. In each turn of the game Ciel will choose either j=0 or j=1. Regardless of which j she chooses, the result will be that she should move all tokens from bin 0 to bin 0 and all tokens from bin 1 to bin 1. That is, nothing changes, all tokens stay where they were. Thus, after 10^100 turns we still have two bins that each contain a token.
```
2
```
```
2
```
```
{0,0,
1,1}
```
```
Returns: 1
```
This is the same setting as in Example 0, only the matrix M is different. The choice j=0 now means "put everything into bin 0" and the choice j=1 now means "put everything into bin 1". Regardless of how Ciel plays the game, after 10^100 turns one of the bins will contain both tokens and the other bin will be empty.
```
3
```
```
1
```
```
{0,1,1}
```
```
Returns: 2
```

{0,0,
 0,0,
 0,0,
 1,1,
 1,1}

Returns: 1

```
3
```
```
2
```
```
{0,2,2,
 1,1,0}
```
```
Returns: 1
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.