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

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

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | tourist | 3404 |

3 | TLE | 3356 |

4 | apiadu | 3351 |

5 | mnbvmar | 3281 |

6 | LHiC | 3276 |

7 | Um_nik | 3268 |

8 | 300iq | 3267 |

9 | yosupo | 3249 |

10 | ainta | 3226 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 190 |

2 | antontrygubO_o | 186 |

3 | tourist | 182 |

4 | Radewoosh | 169 |

5 | vovuh | 167 |

6 | pikmike | 166 |

7 | ko_osaga | 161 |

8 | Um_nik | 160 |

9 | Petr | 155 |

10 | McDic | 153 |

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

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/20/2020 00:03:36 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Hey please explain the question....

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 !

yes ,sir it is so helpful..