CDVA1604 - Editorial

ad-hoc
cdva16
cdva1604
easy
editorial
implementation

#1

PROBLEM LINK:

Practice

Contest

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.