PROBLEM LINK:
Author: Kamil Dębowski
Testers: Hasan Jaddouh, Sergey Kulik
Editorialist: Pawel Kacprzak
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic programming
PROBLEM:
For given N special days t_1 < t_2 < \ldots t_N, and integers A, B, the goal is perform haircuts on some days, not necessarily special ones, in a way which maximize the number of special days t_i, for which the most recently performed haircut before t_i was performed at least A days before t_i and at most B days before t_i.
EXPLANATION:
Subtask 1
In the first subtask, we have N, t_i, A, B \leq 50. This allows us to solve the problem by examining all the possible days at which performing a haircut is reasonable. Notice that in other subtasks, values of t_i can be huge, and thus we are not allowed there to iterate over all possible days.
The problem can be solved with dynamic programming approach. Let’s define:
At the beginning we initialize dp_i for all i to 0.
Now, we can iterate over all days from 0 (remember that the haircut was initially performed at that day) to the maximum special day in the input, let’s call this day M.
Let’s assume that we are at a fixed day i. First of all, we can assign dp_i := max(dp_i, dp_{i-1}) if i \geq 2. It means that the answer for the first i-2 days can be considered as the answer for the first i-1 days. Then, we can try to see what happens if a haircut is performed on day i. Specifically, we are going to iterate over all days from i + A to \min(i+B, M), so over all days affected by the haircut performed at day i. Now, let’s assume that we are at such affected day j and let k be the number of special days in a range [i + A, j]. Then, we can assign dp_{j+1} := max(dp_{j+1}, dp_{i} + k), because a possible answer for the first j days, so dp_{j+1}, can be obtained by taking the best answer for the first i-1 days, performing a haircut on day i, and finally adding all special days not greater than j, which were affected by this haircut. Just notice that k can be updated during the iteration over affected days, so it doesn’t affect the complexity at all.
The final answer is the value dp_{M+1}. Dynamic programming approach helps us to compute the best possibility, capturing all necessary information in an efficient way. The total time complexity of this approach per one test case is O(N \cdot (B-A)), because M can be at most O(N) and the length of a range [i+A, \min(i+B,M)] is bounded by B-A. Since in this subtask we have 1 \leq A,B \leq N, the complexity can be written as O(N^2).
For implementation details of this method please refer to this solution.
Subtask 2
Will be added later
Subtask 3
Will be added later
Subtask 4
Will be added later.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution can be found here.
First tester’s solution can be found here.
Second tester’s solution can be found here.
