Блог пользователя skpro19

Need help in a problem
Автор skpro19, история, 7 лет назад, По-английски

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

  • Проголосовать: нравится
  • -12
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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!

      → Ответить
»
7 лет назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить