You are not logged in. Please login at www.codechef.com to post your questions!

×

CDVA1604 - Editorial

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.

This question is marked "community wiki".

asked 30 Mar '16, 00:12

suraj_ch77's gravatar image

5★suraj_ch77
513
accept rate: 33%

edited 30 Mar '16, 14:49

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,680
×3,764
×947
×832
×34
×4

question asked: 30 Mar '16, 00:12

question was seen: 568 times

last updated: 30 Mar '16, 14:49