×

# HAIRCUT - Editorial

Author: Kamil Dębowski
Editorialist: Pawel Kacprzak

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:

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 := \text{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.

# 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.

This question is marked "community wiki".

73484792
accept rate: 12%

 3 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. :P answered 27 Mar '17, 15:05 6★nibnalin 161●1●5●15 accept rate: 0%
 0 Can I get the logic for solving when A,B and t[i] is large ? answered 26 Mar '17, 09:32 5★adijimmy 123●5●9●17 accept rate: 0%
 0 How to solve original problem? answered 26 Mar '17, 21:48 4★okhterov 1 accept rate: 0%
 0 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. answered 27 Mar '17, 00:17 1 accept rate: 0%
 0 "TR−a<=TL−b<=TR−a" some typo? @nibnalin answered 27 Mar '17, 15:34 6★s_65 31●2 accept rate: 0% 2 @s_65 sorry, i swapped $a$,$b$ in my notation. Even my code/brain processed them that way :P (27 Mar '17, 16:25) nibnalin6★ Yeah i got it thanks! ^^ (27 Mar '17, 16:40) s_656★
 0 please post the tutorial for subtask #4 answered 27 Mar '17, 16:45 71●4 accept rate: 0%
 0 '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. answered 30 Oct '17, 20:20 5★kvsk 43●1●4 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,010
×2,474
×1,887
×29
×4

question asked: 26 Mar '17, 01:22

question was seen: 1,722 times

last updated: 30 Oct '17, 20:20