SECLN - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

There are N security queues. The i-th has A_i people. You’re initially standing at the end of queue 1.
Every second, you can either stay in the same queue or move to the back of an adjacent queue. Then, the first person of each queue will leave.
Find the minimum time needed for you to leave.

EXPLANATION:

Suppose we decide to leave from exactly the i-th queue. How much time will we need?

Well, it’s obvious that if we’re leaving from the i-th queue, we should first repeatedly move towards it till we reach it, and then just keep waiting there till we leave.

The movement will take i - 1 seconds, since we start at 1 and can only move to adjacent queues.

During these i-1 seconds, people will be leaving the queue too: specifically, at the end of the (i-2)-th second (i.e. just before we enter this queue), upto (i-2) people will have left the i-th queue.

So,

  • If A_i \leq i-2, the queue will be empty before we enter it - so we’ll be the first person in it as soon as we enter it, and we’ll leave immediately.
    This means we’ll need i-1 seconds.
  • If A_i \gt i-2, the queue will not be empty when we enter it.
    This means everyone ahead of us must leave the queue before we’re able to.
    Since there were A_i people in it to begin with, this means we’ll leave in the (A_i + 1)-th second.
    • There is one edge case here: for i = 1, we’ll need A_1 seconds rather than (A_1 + 1), since we start out being the last person in this queue already.

So, for each queue we’re able to compute the minimum time needed, depending on how A_i compares to i-2.
Compute the necessary time for each queue, and take the minimum among them.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = [0] + list(map(int, input().split()))
    ans = a[1]

    for i in range(2, n+1):
        if a[i] <= i-2: ans = min(ans, i-1)
        else: ans = min(ans, a[i]+1)
    print(ans)