PROBLEM LINK:Author: Kamil Dębowski 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 1In 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, i1$. 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_{i1})$ if $i \geq 2$. It means that the answer for the first $i2$ days can be considered as the answer for the first $i1$ 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 $i1$ 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 (BA))$, because $M$ can be at most $O(N)$ and the length of a range $[i+A, \min(i+B,M)]$ is bounded by $BA$. 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 2Will be added later Subtask 3Will be added later Subtask 4Will be added later. AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 26 Mar '17, 01:22

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(idx1)$ 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_Lb$ and only if $T_Rb <= T_Lb <= T_Ra$. 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 $Ti$ in range $[T_Lb, T_L)$, so jump to that DP, while taking maximum over this. Formally, if you do range $[L, R]$ answer is $DP(prev)+RL+1$ where $prev =$ maximum index s.t. $T_{prev} < T_Lb$. 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

Can I get the logic for solving when A,B and t[i] is large ? answered 26 Mar '17, 09:32

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

'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
