I was trying to solve http://www.codechef.com/ACMAMR12/problems/LIGHTS yesterday. Accidentally, I read the question wrong. Instead of doing flips on rows only, I did it for for row and column. Obviously my approach was wrong and after looking at others solutions, I found my mistake. Now I wonder, what if the question had said what I previously thought. What if flips are allowed not only in rows but also in columns.
e.g. k=2
- . * *
. * . .
- . * *
flipping row 2 and column 2, we will get maximum *.
I am unable to find an approach for this. I think it will be a dp problem. Still, how to solve it? Any pointers would be helpful.