PROBLEM LINK:
Author: Suraj Prakash
Tester: Diwakar Bhardwaj
Editorialist: Suraj Prakash
DIFFICULTY:
Easy
PREREQUISITES:
Ad-hoc, Implementation
PROBLEM
Given a number n, find the person who survives when alternate person are killed standing in line.
Explanation:
IDEA 1:
The idea to solve the question using the Joseph game. Firstly all the odd numbers are killed and we are left with the problem of about half the size of the original size.
Now, we can solve each smaller problem and get answer based on the answer of the smaller problem.
In the question, if there are n persons, then c[n] denotes the survivor if we start the game from the first person, d[n] denotes the survivor if there are n persons and we start the game from the second person.
IDEA 2:
The given problem can be formulated using the given recurrence
ans(1) = 1
ans(2) = 2
if (n < a(n-1)+2): a(n)=2
else: a(n) = a(n-1)+2
OPTIMAL COMPLEXITY:
\mathcal{O}(N) + \mathcal{O}(Q)
AUTHOR’S SOLUTION:
Author’s solution can be found here.
Tester’s solution will be uploaded soon.