TopCoder problem "TurningLightOn" used in SRM 368 (Division II Level Two)



Problem Statement

    

A rectangular panel consists of R rows, with C bulbs in each row. The rows are numbered from 0 to R-1, and the columns are numbered from 0 to C-1. Some of the bulbs are turned on and some of them are turned off.

The panel is connected to a board with switches. The switches are arranged into a rectangle with R rows and C columns (i.e., with the same dimensions as the panel).

Flipping each switch will cause some of the bulbs to change state: those that were turned on will become turned off, and vice versa. More precisely, if we flip the switch with coordinates (row,col), then all bulbs with coordinates (x,y) where x<=row and y<=col will change their states. In other words, flipping the switch at (row,col) switches all the bulbs in the rectangle with opposite corners (0,0) and (row,col).

You will be given a String[] board containing the initial states of the bulbs. The character '1' represents a bulb that is turned on, and the character '0' represents a bulb that is turned off.

Return the smallest number of flips necessary to have all the bulbs on at the same time.

 

Definition

    
Class:TurningLightOn
Method:minFlips
Parameters:String[]
Returns:int
Method signature:int minFlips(String[] board)
(be sure your method is public)
    
 

Notes

-Using the right combination of switches it is always possible to turn on all bulbs at the same time.
 

Constraints

-board will contain between 1 and 50 elements, inclusive.
-Each element of board will contain between 1 and 50 characters, inclusive.
-All elements of board will have the same length.
-Each element of board will only contain the characters '0' (zero) and '1' (one).
 

Examples

0)
    
{"0001111",
 "0001111",
 "1111111"}
Returns: 1
It is enough to flip the switch at (1,2).
1)
    
{"1111111",
 "1111111",
 "1111111"}
Returns: 0
Here all the bulbs are already turned on, we don't have to do anything.
2)
    
{"01001"}
Returns: 3
For this case, one optimal solution is to start by flipping the leftmost switch (turning on the leftmost bulb only), then flip the switch at (0,3) to get "00111", and finally flip the switch at (0,1).
3)
    
{"0101",
 "1010",
 "0101",
 "1010"}
Returns: 7
For chessboard patterns one needs quite a lot of flips.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8244

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10936&pm=8244

Writer:

misof

Testers:

PabloGilberto , vorthys , Olexiy , ivan_metelsky

Problem categories:

Greedy, Simulation