Editorial for DMOPC '22 Contest 4 P4 - Anki Reviews

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: X_Ray

Subtask 1

Solution

We can just loop over the $N$ ~N~ reviews to find the longest streak.

Time Complexity: $\mathcal{O}(N)$

Subtask 2

Hint 1

Looping over all $D$ possible values of $x$ is too slow. How many unique configurations of reviews are there?

Solution

We observe that there are $N$ ~N~ unique configurations of reviews, and they occur when at least one review satisfies $t_i=x+kD$ ~t_i=x+kD~ for some integer $k$ ~k~. Thus, we can find the answer by looping over all $N$ ~N~ reviews for each configuration, and counting the longest streak for the given configuration.

Time Complexity: $\mathcal{O}(N^2)$

Subtask 3

Hint 2

Looping over all $N$ values for each configuration is now too slow. How can we optimize calculations for the longest streak?

Hint 3

Can we loop over the configurations in some order so that re-calculating the longest streak is faster?

Solution

We can loop over the configurations in increasing order of $x$ ~x~. Note that to transition between configurations, some reviews are moved between adjacent days, and that each review is moved at most once. We can maintain a segment-tree like data structure, maintaining the longest streak over an interval at each node. Updating takes $\mathcal{O}(\log N)$ ~\mathcal{O}(\log N)~ time, as it suffices to "walk up" the tree for each transition, updating nodes as we go.

Time Complexity: $\mathcal{O}(N\log N)$

Comments

There are no comments at the moment.