You are not logged in. Please login at www.codechef.com to post your questions!

×

HAIRCUT - Editorial

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

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.

This question is marked "community wiki".

asked 26 Mar '17, 01:22

pkacprzak's gravatar image

5★pkacprzak ♦♦
73484792
accept rate: 12%

edited 26 Mar '17, 01:57


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

link

answered 27 Mar '17, 15:05

nibnalin's gravatar image

6★nibnalin
1611515
accept rate: 0%

edited 27 Mar '17, 16:43

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

link

answered 26 Mar '17, 09:32

adijimmy's gravatar image

5★adijimmy
1235917
accept rate: 0%

How to solve original problem?

link

answered 26 Mar '17, 21:48

okhterov's gravatar image

4★okhterov
1
accept rate: 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.

link

answered 27 Mar '17, 00:17

morphine_cc's gravatar image

1★morphine_cc
1
accept rate: 0%

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

link

answered 27 Mar '17, 15:34

s_65's gravatar image

6★s_65
312
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★

please post the tutorial for subtask #4

link

answered 27 Mar '17, 16:45

chinmay0906's gravatar image

6★chinmay0906
714
accept rate: 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.

link

answered 30 Oct '17, 20:20

kvsk's gravatar image

5★kvsk
4314
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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