P2_175 - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: abhigyan1245
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

cakewalk

PREREQUISITES:

None

PROBLEM:

You’re the N-th person standing in a queue to obtain a ticket to an event.
Every second, the first and third person in the queue will receive a ticket and leave the line.

When will you receive your ticket?

EXPLANATION:

If N = 1 or N = 3, you’ll receive a ticket in the very first second.

If N = 2, you’ll receive a ticket in the second second; because after person 1 leaves the line you’ll be the first person remaining.

For N \gt 3, note that in the first second two people ahead of you will receive their tickets and leave the line.
This means one second has passed and you’re basically in the same situation, just that you’re now at position N-2 of the queue instead.

This leads to a very straightforward solution:

  • While N \gt 3, add 1 to the answer and subtract 2 from N.
  • Once N becomes \leq 3, utilize the cases observed initially: add 1 to the answer if N = 1 or N = 3, and add 2 to the answer if N = 2.

Implemented directly this takes \mathcal{O}(N) time which is fast enough for the given constraints.
It can be further optimized to constant time by doing some simple algebra to avoid the loop over N.

TIME COMPLEXITY:

\mathcal{O}(N) or \mathcal{O}(1) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    ans = 0
    while n > 3:
        n -= 2
        ans += 1
    if n == 1 or n == 3: ans += 1
    else: ans += 2
    print(ans)
2 Likes
2

Looking at the sequence, it can be inferred that for an odd numbered position, its integral division gives the result. For even numbers, we just need to add one to the result.

void solve() {
    // Solution for each test case
    int a;
    cin >> a;
    if(a == 1) cout <<  1;
    else if(a & 1) cout << (a / 2);
    else cout << ((a / 2) + 1);
}
1 Like