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

×

ACM14KG4 - Editorial

PROBLEM LINK:

Practice
Contest

Author: Anudeep Nekkanti
Tester: Mahbubul Hasan
Editorialist: Jingbo Shang

DIFFICULTY:

Medium-Hard

PREREQUISITES:

Segment Tree

PROBLEM:

This problem is essentially to ask you do the following queries:

Given some numbers between 1 and 5 * N, find out the smallest 3 consecutive numbers not less than P, while the numbers are updated along time.

EXPLANATION:

For this interval type of queries (here, refer to the "not less then P"), it is natural to think about segment trees.

In this problem, the specific problem is that finding out the smallest 3 consecutive numbers not less than P. We can first transform it to another alternative statement:

The smallest number which is not less than P and it has not been forbiden before.

where, a number is "forbidden" means that there are some numbers missing such that we can't select 3 consecutive numbers starting from it.

More specifically, initially, we have all 5 * N - 2 numbers available except for the last 2 numbers, because there are not enough numbers after them. Then, when 3 numbers starting from x are selected by someone, i.e. x, x+1, x+2 are selected, the 5 numbers x-2, x-1, x, x+1, x+2 should be "forbidden".

Therefore, this problem could be solved by a basic segment tree, which maintains the availability of all numbers, supports the query of minimum available number in an interval, and can set the availability of some specific number.

AUTHOR'S AND TESTER'S SOLUTIONS:

Solutions will be available soon.

Author's solution can be found here.
Tester's solution can be found here.

asked 01 Dec '14, 09:17

shangjingbo's gravatar image

3★shangjingbo ♦♦
161446375
accept rate: 0%

edited 18 Mar '15, 17:26

admin's gravatar image

0★admin ♦♦
19.7k350498541

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,499
×1,729
×1,237
×13
×4

question asked: 01 Dec '14, 09:17

question was seen: 871 times

last updated: 18 Mar '15, 17:26