In this problem Div 2C, how can the difference between the maximum visited and the minimum visted be more than 1 ?

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

1 | Benq | 3783 |

2 | jiangly | 3666 |

3 | tourist | 3611 |

4 | Um_nik | 3536 |

5 | inaFSTream | 3477 |

6 | fantasy | 3468 |

7 | maroonrk | 3464 |

8 | QAQAutoMaton | 3428 |

9 | ecnerwala | 3427 |

10 | Ormlis | 3396 |

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

1 | Um_nik | 184 |

2 | adamant | 178 |

3 | awoo | 177 |

4 | nor | 169 |

5 | maroonrk | 165 |

6 | -is-this-fft- | 164 |

7 | antontrygubO_o | 152 |

8 | ko_osaga | 151 |

9 | dario2994 | 150 |

10 | SecondThread | 149 |

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/05/2023 03:07:52 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Try and simulate a case where the teacher stops asking questions in the middle of a row that isn't the top or bottom one. I think that should help.

Let's take the input as

5 5 33 3 3.

Here also, the difference between the maximum visited and the minimum visited is not more than 1.

Consider this case: 3 2 15 2 2

{0, 0}

{0, 0}

{0, 0}

After the first six iterations, it becomes:

{1, 1}

{1, 1}

{1, 1}

There are 9 questions left to ask. The teacher will start going backwards in the ordering now (I think it was in the problem statement). Consider the questions asked after another 4:

{2, 2}

{2, 2}

{1, 1}

There are 5 questions left:

{2, 2}

{3, 3}

{2, 2}

And now with one question left it becomes:

{2, 2}

{4, 3}

{2, 2}

So the minimum questions asked is two but the one student in the middle row got the last question making him four (notice that the students in the rows that aren't the top and bottom will always get asked more questions). I hope that makes things clearer. If not, feel free to ask more questions!

Thank you so much.

Let's consider this input. 4 1 8 3 1

We have 4 X 1 matrix.

0

0

0

0

After teacher asks 8 questions. Matrix turns out like this —

2

3

2

1

Here we have max — min > 1.

The difference between maximum and minimum can be greater than 1, because firstly the teacher asks questions from 1st to Nth row, so till now all cells in all rows have same value, then now skip Nth and ask from N-1th to 1st, so the cells in Nth rows are 1 less than all other cells. Now skip 1st and ask from 2nd to Nth, now suppose total questions are over before actually reaching Nth row, then now the 1st row cells are 1 less, and Nth row cells are 2 less than the cells of row [2 , x] where x < N.

Thank you so much.