java - Recreate a binary matrix with least "XOR" operations -

this highschool-degree coding contest question while back. basic idea recreate painting of black , white rectangular xor operations, or that's called it.

the problem

let assume have painting trying recreate (represented binary matrix, 0 being black , 1 being white):

1 0 0 1 1 1 1 0 1 

one way of recreating painting following operations:

(0, 0) (2, 2) (1, 0) (2, 0) (1, 2) (1, 2) 

the operations in form of (xstart, ystart) (xend, yend)

thus above operations following, if start all-black canvas:

beginning:      0 0 0     0 0 0     0 0 0  after (0, 0) (2, 2) :      1 1 1     1 1 1     1 1 1  after (1, 0) (2, 0) :      1 0 0     1 1 1     1 1 1  after (1, 2) (1, 2) :      1 0 0     1 1 1     1 0 1 

---

technicalities assignment:

• winner has least operations.
• one operation should in form of (xstart, ystart) (xend, yend).
• there no time or space restraints.
• in assignment, painting trying recreate 200x200 in size, , generated 2000 random xor operations.

---

my own ideas

i have come couple of ways this. i'll list them here in order of worse best.

xor pixels:

we can recreate painting writing 1 blank canvas 1 resides in painting trying recreate. solution simplest , obvious of all. number of operations needed amount of white pixels in painting.

xor horizontally adjacent whites:

this substantial improvement first solution, still simple , obvious. in method xor horizontally adjacent whites. in way, example operations

(0, 0) (0, 0) (1, 0) (1, 0) (2, 0) (2, 0) 

would diminished (0, 0) (2, 0).

xor rectangles:

this think clear follow-up of previous method, can see xoring rectangles height of 1 - add second dimension rectangles, further improving our results. determined xorable area getting rectangle whites. improvement still good.

xor biggest difference:

this slight change above methods, , bit more brute-force. in method find rectangle biggest difference painting, , xor it. example, if have painting

1 0 1 0 1 1 0 1 0 

and all-black canvas, biggest difference in rectangle (0, 0) (2, 1), has difference of 2. calculate difference getting non-same colors of painting, 4 in above situation, , subtracting amount of same colors it, in above situation 2. different_colors - same_colors = difference.

in above painting , blank canvas, there many rectangles produce same difference. 1 other (1, 0) (2, 2).

this method gave smallest improvement previous 1 large paintings, improvement nonetheless. interstingly, method came worse solution previous 1 small paintings (can't remember how small, though).

---

any code had described methods above have been long since lost. can come breath-taking solutions? there magical approach outer space? find question (post) pretty interesting , see if can come anything.

---

about tags

i have tagged both java , c++, not because question concerns particularly languages, because can understand code written in languages, , languages similar syntax.

i think, complete task, require find coordinates of maximum size sub-matrix containing zeros.

i can explain algorithm think following link has best explanation :

maximum size sum-matrix 1s in binary matrix

here solution 1s, can modify 0s.

then need find coordinate maximum value , can operation.

i'll update if can think of better method.