Author: | Roman Bilyi |
Prepared by: | Yarema Stiahar |
Solved by: | 25/42 |
First to solve: | RAF 1 |
For each triplet (a_i, b_i, c_i) we must choose two values to form an interval. Notice that the middle value b_i always belongs to any possible interval:
Therefore, regardless of the chosen pair, every interval contains b_i.
Since a_i < b_i < c_i, if three or more triplets have the same middle value b_i, it is impossible to choose intervals with zero intersection length, because all of them would intersect at b_i. In this case, the answer is .
We sort all triplets by increasing b_i and process them in this order. Triplets with the same value of b_i are processed simultaneously. We use dynamic programming to find the maximum possible total length of intervals.
An interval chosen from the -th triplet can end either at b_i or at c_i, which is represented by states and .
Let dp_{0,i} and dp_{1,i} be the maximum total length using the first triplets. State means that the chosen interval ends as early as possible, while state means that it ends as late as possible.
More precisely, if the -th triplet is the only one with value b_i, then:
If there are two triplets with the same value b_i, then their intervals must end at different right endpoints to avoid intersection. In this case:
For each triplet, we try all valid transitions from the previous triplet(s), ensuring that the chosen intervals do not overlap and the total length is maximized. Because at most two triplets have the same middle value, only a constant number of transitions must be considered.
The final answer is the maximum value among all valid DP states after processing all triplets; if no such state exists, the answer is . The overall time complexity is O(n \log n) due to sorting.