LONGQUEUE - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

N people stand in a queue, the i-th has a wealth of A_i.
Sushil is the N-th person. He can bully the person directly in front of him out of the queue if his wealth is greater than half the other person’s wealth.

Find Sushil’s final position.

EXPLANATION:

This is an implementation task: you only need to do exactly what’s outlined in the statement.

Let x denote the current position of Sushil. Initially, this is N.
While x \gt 1,

  • Check if Sushil can bully person x-1 out of the queue.
    This can be done by checking whether A_N \geq \frac{A_{x-1}}{2}.
  • If he can’t bully this person, x is Sushil’s final position.
  • Otherwise, decrease x by 1 and continue on.
  • In the end, output x.

To implement this, you can use a while loop.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    pos = n-1
    while pos > 0:
        if a[n-1] >= 2*a[pos-1]:
            pos -= 1
        else: break
    print(pos + 1)