×

# ACM14KG4 - Editorial

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

Medium-Hard

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.

161446375
accept rate: 0%

19.7k350498541

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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