PROBLEM LINK:
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.