skpro19's blog

Need help in a problem
By skpro19, history, 8 years ago, In English

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

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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!

      → Reply
»
8 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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.

→ Reply