Connection Status:
Competition Arena > MatrixGame

MatrixGame

SRM 466 · 2009-11-12 · by Chmel_Tolstiy

SRM 466 · 2009-11-12 · by Chmel_Tolstiy · Brute Force, Sorting, String Manipulation
Class Name: MatrixGame
Return Type: String[]
Method Name: getMinimal
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Alex likes to play the following strange game. He starts with a rectangular NxM grid where each cell contains a '0' (zero) or '1' (one). Rows of the grid are numbered 0 to N-1, inclusive, and columns are numbered 0 to M-1, inclusive. On each move, he chooses two columns in the grid and entirely swaps their content or he chooses two rows in the grid and entirely swaps their content. He can perform an arbitrary large number of moves and there are no restrictions on the order in which he performs moves.

Each NxM grid can be described as a String[] containing N elements. The j-th character in the i-th element of this String[] is the same as the character in row i, column j of the grid. Alex's goal is to achieve such a grid that the corresponding String[] is lexicographically minimal (see notes for exact definition). Since he is always unsure whether the goal has been achieved, you are to write a program that checks it for him. Given a String[] matrix describing the grid that Alex initially has, return the lexicographically smallest String[] that he can produce.

Notes

  • A String[] A is lexicographically smaller than a String[] B of the same length if it contains a lexicographically smaller String at the first position where they differ.
  • A String A is lexicographically smaller than a String B of the same length if it contains a smaller character at the first position where they differ ('0' is smaller than '1').

Constraints

  • matrix will contain between 1 and 8 elements, inclusive.
  • Each element of matrix will contain between 1 and 8 characters, inclusive.
  • All elements of matrix will have the same length.
  • Each character in matrix will be either '0' or '1'.
Examples
0)
{"000",
 "000",
 "000"}
Returns: {"000", "000", "000" }

Any move has no effect.

1)
{"010",
 "000",
 "110"}
Returns: {"000", "001", "011" }

The following sequence of moves can be used: 010 000 000 000 000 -> 010 -> 001 -> 001 110 110 101 011

2)
{"111",
 "111",
 "111"}
Returns: {"111", "111", "111" }
3)
{"01010",
 "10101",
 "01010",
 "10101"}
Returns: {"00011", "00011", "11100", "11100" }
4)
{"11010100",
 "11110001",
 "00011101",
 "11111111",
 "01110100",
 "10000110",
 "00001001",
 "11010111"}
Returns: {"00000011", "00001111", "00110100", "01011100", "01111101", "11001100", "11011001", "11111111" }

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

Coding Area

Language: C++17 · define a public class MatrixGame with a public method vector<string> getMinimal(vector<string> matrix) · 99 test cases · 2 s / 256 MB per case

Submitting as anonymous