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 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 unique configurations of reviews, and they occur when at least one review satisfies t_i=x+kD for some integer k. Thus, we can find the answer by looping over all 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. 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) 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.