noobinho's blog

Problem 1458 Timus
By noobinho, history, 6 years ago, In English

I'm trying to solve this problem: http://acm.timus.ru/problem.aspx?space=1&num=1458. It gives a n x n matrix (2 <= n <= 1000), with n always even, with all entries 0-1. We can change the matrix with operations with the format op(i,j), which turns on all the zeros and turns off all the ones in the ith horizontal and in the jth vertical. It's demanded to find the minimum number of operations (and output these operations) that we can apply to the matrix to get a matrix with all entries 0 or a matrix with all entries 1. I found a closed way to turn on or turn off a unique entry of the matrix using (2*n-1) operations and used it in my algorithm in the following way: I count the number of ones in the matrix. If it's less than (n*n)/2, I turn off all the ones of the matrix to get a matrix with all entries 0. Else, I turn on all the zeros to get a matrix with all entries 1 (code: https://ideone.com/e.js/XU3rHF ), but it gives TLE. So, I would like to know what I can do to improve the complexity of the algorithm (at this moment, I think it's O(n³), which is not enough for 2 <= n <= 1000). Thanks in advance.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Observe that for a given matrix; if no coordinates are repeated more than once, then that answer is optimal.Why would we want to repeat coordinates? If you call a coordinate twice then it will be as if you didn't modify the matrix at all.

In other words, the answer is unique.

So now all we have to do is find an answer, and only output the coordinates that are repeated an odd number of times.

Suppose that there's a cell (x,y) that you want to flip; you will need 2*n-1 operations.Specifically, you will call every (i,j) such that i=x or j=y once.

Then for each (i,j) find out C[i][j]: the number of times that you will call it if you want to flip all the 'B's to 'W's.And only call it if this number is odd.

To do this effectively keep two arrays r and c and for each cell (i,j) you want to flip increment r[i] and c[j].Now C[i][j] = r[i]+c[j] for every (i,j).Note that for the 'B' cells, you need to +-1 to this number, because it will be as if you counted 2*n operations(repeating (i,j) twice).Now output the cells (i,j) such that C[i][j]%2 = 1.

Do the same after reversing 'W's to 'B's.Pick the answer with the least number of operations.

Last observation; Let the minimum number of operations needed to convert the whole matrix to 'B's nB and the minimum number of operations needed to convert the whole matrix to 'W's nW; nB + nW = n².

So pick a character and find out all the cells needed to flip all the occurences of this character, and if the number of these cells is > n²/2, pick all the other cells.

Code.

→ Reply