Connection Status:
Competition Arena > LampsGrid

LampsGrid

SRM 432 · 2009-01-06 · by nika

SRM 432 · 2009-01-06 · by nika · Search
Class Name: LampsGrid
Return Type: int
Method Name: mostLit
Arg Types: (vector<string>, int)
Problem Statement

Problem Statement

Jack has bought a rectangular table containing a grid of lamps. Each lamp is initially either "on" or "off". There is a switch underneath each column, and when the switch is flipped, all the lamps in that column reverse their states ("on" lamps become "off" and vice versa).


A row in the grid is considered lit if all the lamps in that row are "on". Jack must make exactly K flips. The K flips do not necessarily have to be performed on K distinct switches. His goal is to have as many lit rows as possible after making those flips.


You are given a String[] initial, where the j-th character of the i-th element is '1' (one) if the lamp in row i, column j is initially "on", and '0' (zero) otherwise. Return the maximal number of rows that can be lit after performing exactly K flips.

Constraints

  • initial will contain between 1 and 50 elements, inclusive.
  • Each element of initial will contain between 1 and 50 characters, inclusive.
  • Each element of initial will contain the same number of characters.
  • Each element of initial will contain only the digits '0' and '1'.
  • K will be between 0 and 1000, inclusive.
Examples
0)
{"01",
 "10",
 "10"}
1
Returns: 2

Here, Jack must flip exactly one switch. If he flips the switch for the second column, the bottom two rows become lit.

1)
{"101010"}
2
Returns: 0
2)
{"00", "11"}
999
Returns: 0

No row can be lit after exactly 999 flips.

3)
{"0", "1", "0", "1", "0"}
1000
Returns: 2
4)
{"001", "101", "001", "000", "111", "001", "101", "111", "110", "000", "111", "010", "110", "001"}
6
Returns: 4

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

Coding Area

Language: C++17 · define a public class LampsGrid with a public method int mostLit(vector<string> initial, int K) · 240 test cases · 2 s / 256 MB per case

Submitting as anonymous