Editorial for DMOPC '22 Contest 4 P4 - Anki Reviews
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1
Solution
We can just loop over the reviews to find the longest streak.
Subtask 2
Hint 1
Looping over allSolution
We observe that there are unique configurations of reviews, and they occur when at least one review satisfies
for some integer
. Thus, we can find the answer by looping over all
reviews for each configuration, and counting the longest streak for the given configuration.
Subtask 3
Hint 2
Looping over allHint 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 . 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
time, as it suffices to "walk up" the tree for each transition, updating nodes as we go.
Comments