TwoSquares
SRM 699 (Cisco) · 2016-08-27 · by Errichto
Problem Statement
Limak has a square grid that consists of N rows by N columns of unit square cells.
Each cell contains either the number 0 or the number 1.
You are given the current content of Limak's grid in the
Limak can change the grid by performing the following operation: he can select any square part of the grid and flip all values inside the selected square (i.e., changing each 0 to a 1 and vice versa). Note that the selected square can have any position within the grid and any size, including just a single cell (a 1x1 square) and the entire grid (an NxN square).
Limak is allowed to perform the above operation zero, one, or two times. Compute and return the largest possible number of 1s in the final grid.
Notes
- Note the unusual Time Limit.
Constraints
- N will be between 1 and 100, inclusive.
- t will contain exactly N elements.
- Each element in t will contain exactly N characters.
- Each character in each element in t will be '0' or '1'.
{
"000",
"010",
"011"}
Returns: 8
One optimal solution is to do two operations. For the first operation Limak selects the entire square. This produces the following grid: 111 101 100 For the second operation Limak should select the 2 times 2 square in the bottom right corner of the grid. The final grid looks as follows: 111 110 111 There are 8 ones in this grid. This is the largest number of ones that can be obtained.
{"0"}
Returns: 1
Here, there is only one optimal solution. Limak should perform a single operation, flipping the only 0 to 1.
{
"0001",
"0001",
"0111",
"1001"}
Returns: 16
In this case it is possible to obtain a grid full of 1s, which is clearly optimal. One way of doing so starts by flipping the top-left 3x3 square. This produces the following grid: 1111 1111 1001 1001 Obviously, the second operation is to flip the 2x2 square in the middle of the bottom side.
{
"001111",
"111111",
"110001",
"110001",
"110001",
"111111"}
Returns: 35
{"1"}
Returns: 1
Submissions are judged against all 32 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TwoSquares with a public method int maxOnes(vector<string> t) · 32 test cases · 2 s / 256 MB per case