HAIRCUT - Editorial

dynamic-programming
editorial
haircut
ltime46
medium

#1

PROBLEM LINK:

Practice
Contest

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:

dp_i := ext{solution for days with numbers $j < i$ , so for days $0, 1, \ldots, i-1$. Remember that we do not include day $i$ here}

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][333]. First tester's solution can be found [here][444]. Second tester's solution can be found [here][444].

#2

Can I get the logic for solving when A,B and t* is large ?


#3

How to solve original problem?


#4

can you please explain a bit more…about the algorithm instead of just telling to use dp and that max function…makes it easy to grasp the concept for those who had not yet mastered dynamic programming. thanks in advance.


#5

Since there is no editorial yet, here is my solution. It is slightly different than the editorial subtask DP, but nevertheless it works in O(N \log N).

Let DP(idx) define maximum good day we can get in prefix 1...idx. First let us come up with O(N^2) for this. If we want day idx to not be a good day, we call DP(idx-1) otherwise we know that day idx is definitely in some range [L, R](why a range? I’ll touch on this later) and as we consider only prefix it must be R = idx. So let us iterate over possible values of L. For some range [L, R], we can cover these days by getting haircut on day T_L-b and only if T_R-b <= T_L-b <= T_R-a. It is easy to see this would also satisfy entire range [L, R]. If we do range [L, R], it is for certain that we won’t be able to cover any days having T-i in range [T_L-b, T_L), so jump to that DP, while taking maximum over this. Formally, if you do range [L, R] answer is DP(prev)+R-L+1 where prev = maximum index s.t. T_{prev} < T_L-b.

If you understood the O(N^2) formulation it is easy to see that our operations are more or less only dependent on L for a DP(+/- constant current index). So we can put these values on a segment tree and do range query for finding maximum good days in O(N \log N). My code is quite straightforward: link. Some people also solved it exploiting the trivial DP nature that answer will remain same for long ranges.

UPD: Sorry, I swapped a, b in my notation. :stuck_out_tongue:


#6

“TR−a<=TL−b<=TR−a” some typo? @nibnalin


#7

please post the tutorial for subtask #4


#8

‘M can be at most O(N)’. How is this possible? As M can be up to 10^9 and maximum value of N is just 150000.


#9

@s_65 sorry, i swapped a,b in my notation. Even my code/brain processed them that way :stuck_out_tongue:


#10

Yeah i got it thanks! ^^