Connection Status:
Competition Arena > MovingTokens

MovingTokens

SRM 705 Sponsored By Blizzard · 2016-12-22 · by ltaravilse

SRM 705 Sponsored By Blizzard · 2016-12-22 · by ltaravilse · Graph Theory
Class Name: MovingTokens
Return Type: int
Method Name: move
Arg Types: (int, int, vector<int>)
Problem Statement

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:
  1. Ciel chooses the value of j: an integer between 0 and m-1.
  2. 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.

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
0)
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.

1)
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.

2)
3
1
{0,1,1}
Returns: 2
3)
2
5
{0,0,
 0,0,
 0,0,
 1,1,
 1,1}
Returns: 1
4)
3
2
{0,2,2,
 1,1,0}
Returns: 1

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

Coding Area

Language: C++17 · define a public class MovingTokens with a public method int move(int n, int m, vector<int> moves) · 134 test cases · 2 s / 256 MB per case

Submitting as anonymous