CODEWITHSUNDEEP
c#
user7314328
user7314328

Reputation:

Flipping tile game

I need help building an algorithm to solve a tile flipping game: Given an integer 'n', an n x n square of 1s and 0s is formed. I must flip all of the 1s to 0s. Although, you can only flip the tiles in the form of a rectangle (everything in the rectangle is toggled), where the upper-left vertice of the rectangle is the upper-left corner of the square. I must compute the minimum number of toggles that can be made to have all zeros.

Upvotes: 2

Views: 436

Answers (2)

Juan
Juan

Reputation: 430

Not sure if there's an actual benefit over @kraskevich's answer, apart of progressively shorter rows to flip.

My proposal is to flip the furthest row which is not already in its final form and discard it. Then, the same with the column at the same distance from origin. At this point you have an n-1 x n-1 square to which we can apply the same solution.

I still find very unfortunate the situation with inner homogeneous rectangles (all 0's or all 1's.

For example, say you have as input an nxn square such that its inner n-1 x n-1 square is homogeneous and the furthest row and/or column is randomly "scrambled" with 0's and 1's. Then, to flip these outer tiles you don't have choice but to totally scramble the inner square.

My questions are:

  • do we actually have no choice? No possible preprocessing which globally helps?

  • Would the inner rectangle get irreversibly scrambled? No property I'm not seeing which would still allow us to get profit of the fact that area was originally uniform? Something like it gets scrambled when flipping the outer-row tiles but after "unscrambling" the furthest row in the inner rectangle the whole of it woyld trivially get unscrambled too?

EDIT:

I believe the second question has affirmative answer, as conditional bit flipping is reversible.

However, I still feel the need of some proof of optimality I still don't come up with.

Upvotes: 0

kraskevich
kraskevich

Reputation: 18556

  1. If the solution is optimal, no rectangle is flipped more than once (indeed, we can never flip it instead of flipping it twice).

  2. The order of flips doesn't matter.

  3. Thus, we can use the following algorithm:

    for i = n - 1 downto 0
     for j = n - 1 downto 0
         if f[i][j] == 1
             flip(i, j) // This function should flip the entire rectangle
             res += 1

If we process cells in this order, later cells never affect any previous one. Thus, we either flip the current cell or we don't.

If N is large, you can use prefix sums on rectangles to find whether we need to make a flip or not to obtain an O(N^2) time complexity (if it's small, you can flip the rectangle naively).

Upvotes: 3

Related Questions