Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Problem 1458 Timus

Revision en4, by noobinho, 2018-07-27 05:50:49

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.

#### History

Revisions

Rev. Lang. By When Δ Comment
en4 noobinho 2018-07-27 05:50:49 12 Tiny change: 'E. So, I want to know w' -> 'E. So, I would like to know w'
en3 noobinho 2018-07-27 05:47:19 1 Tiny change: '0).\nThank in advanc' -> '0).\nThanks in advanc'
en2 noobinho 2018-07-26 21:13:33 1 Tiny change: '.js/XU3rHF), but it ' -> '.js/XU3rHF ), but it '
en1 noobinho 2018-07-26 21:13:07 1126 Initial revision (published)