Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

helllo111's blog

By helllo111, history, 5 weeks ago, In English,

Hi Evevryone , I face some difficulty to understand the editorial of this question . May anyone explain the solution of this question .

Thank you in advance. Click me for question

 
 
 
 
  • Vote: I like it
  • -2
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Hey please explain the question....

»
5 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

First of all, we can observe that a change made on one column will have no influence on the other columns. We will therefore focus on how to solve the exercise on a single column. Only the solution for the first column is therefore detailed below; it is obvious that the same process can be applied to the following columns, so as to finally obtain the good result.


The elements of this column must have in the final permutation the values 0, m, ..., (n-1). m.

The elements of this column must have in the final permutation the values 0, m, ..., (n-1). m. If, among the elements of the basic matrix, one finds one of these elements, one will not have to replace it by another if one carries out the number of adequate circular shifts to return it to the position where it must finally arrive.

For each element which must be in the final column and which is in the starting column, the number of circular shifts to be calculated is calculated. We note that for this circular shift, we will have one less transformation operation to do (this is easily done with an occurrence table). Then just loop for all possible circular offsets.

This solution has a complexity of O (NM). I hope I have been helpful !