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 vector 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.
DEFINITION
Class:LampsGrid
Method:mostLit
Parameters:vector , int
Returns:int
Method signature:int mostLit(vector initial, int K)
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
5)
{"01", "10", "01", "01", "10"}
1
Returns: 3
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)2010, TopCoder, Inc. All rights reserved.