(Note: the editorials are written in a hurry and without having solved the problems, so there may be mistakes. Feel free to correct them / inform me.)
PROBLEM LINK:
Author: Vitalii Kozhukhivskyi
Tester: Sergey Kulik
Editorialist: Xellos
DIFFICULTY:
EASY
PREREQUISITES:
none
PROBLEM:
There are N numbers whose value depends on discrete time t as v_i=h_i+tm_i. Find the time intervals when the numbers form an alternating sequence (v_1 < v_2 > v_3 < \dots or v_1 > v_2 < v_3 > \dots).
QUICK EXPLANATION:
There are at most 2 time intervals and they can be found as intersections of intervals when the inequalities for each pair of adjacent values hold.
EXPLANATION:
Since the values increase linearly, any inequality of the form v_i < v_j will hold during a time interval (unbounded at one or both ends or empty). The time when all inequalities for one type of an alternating sequence hold will also be an interval, since it’s the intersection of the intervals when individual inequalities hold.
Therefore, there are at most 2 time intervals to print for each testcase, one for the alternating sequence starting with v_1 < v_2 and another for the one starting with v_1 > v_2 (of course, we don’t print empty intervals).
In order to compute them, we only need the intervals when individual inequalities hold. Computing their intersection is easy - for intervals [I_{il},I_{ir}], the intersection is [max_i(I_{il}),min_i(I_{ir})]. The endpoints of those intervals can be computed using binary search or directly through a formula: if m_2 > m_1, then v_1=v_2 at the time t_i=(v_1-v_2)/(m_2-m_1), v_1 > v_2 at times < t_i and v_1 < v_2 at times > t_i; since we’re only looking for integer bounds, it’s best to make an estimate using \mathrm{floor}(t_i) and then increase/decrease it by 1 until it’s correct to avoid precision errors. This can only take at most one increase/decrease. There’s also a special case m_2=m_1, where the inequality holds either always or never depending on the initial h-s.
The time and memory complexity of this approach is O(N).
AUTHOR’S AND TESTER’S SOLUTIONS:
The author’s solution can be found here.
The tester’s solution can be found here.