Tourism Editorial

Author: sinsane | Original solution: kuruluu

This editorial will cover one of the multiple ways to solve this problem.

Subtask 1 (~10\%~)

As ~2K \geq N~, the solution must take at most 2 days. Loop through all indices, recording the sum of the maximal attraction score to the left and right of the index. The answer is the maximum over these sums. Range maximum queries can be answered in constant time with a sparse table after an ~\mathcal{O}(N \log N)~ preprocessing.

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

Subtask 2 (~10\%~)

We can use dynamic programming to solve this subtask. Let ~dp[i]~ be the maximum score we can achieve under the condition that the number of days used is minimal, and ~t_i~ be the minimum number of days to reach the ~i~'th attraction. Then, $$\displaystyle dp[i] = \max_{i-k\ \leq\ j\ <\ i\; \text{and}\; t_j\ =\ t_i - 1} \left\{ dp[j] + \max(a_{j+1}, \dots, a_{i}) \right\} $$

Time Complexity: ~\mathcal{O}(N \log N + NK)~

Full Solution:

Our current transition time is too slow. We can use two monoqueues: red and blue, to get the optimal ~j~ to transition from in constant time! Consider the sample case.

A = 2 5 7 | 1 4

The critical observation is that once we enter a new "block" of days (in this case attractions ~4~ and ~5~ both require 2 days to reach), the monoqueues for the previous block are static. We then consider two cases:

• For the best ~j~ to transition from, the maximum ~a~ is in the current block of days.
• For the best ~j~ to transition from, the maximum ~a~ is in the previous block of days.

For the first case, let the red monoqueue store only the ~j~ values such that ~dp[j]~ is in decreasing order, and we can simply grab the front of the red monoqueue and sum it with the maximum ~a~ we identified earlier.

For the second case, let the blue monoqueue store only the ~j~ values such that ~dp[j]~ + the maximum ~a~ from ~j~ to the start of the current block is in decreasing order.

The value of ~dp[i]~ will then be the maximum over the two cases.

To maintain the monoqueues, clear them upon entering a new block of days, and insert all of the indices in the previous block. In our example, upon entering the new block at attraction ~4~, we insert attractions ~1-3~ into our monoqueues.

Psuedocode:

initialize monoqueues red, blue

for i -> 1, 2, .. N:
    if newBlock:
        clear monoqueues
        for j -> i-k, .. i-1:
            push j into red, comparing dp[red.back] and dp[j]
            push j into blue, comparing dp[blue.back] + rmq(blue.back+1, i-1) and dp[j], rmq(j+1, i-1)

    dp[i] = max(redScore, blueScore)

    pop expired elements from monoqueues

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

• 169p on Dec 6 2022
• 300p on April 22 2024
• 400p on June 2 2024
• Tourism slain on Sep 1, 2024 (thanks kuruluu)

Editorials: https://dmoj.ca/user/KurbyDoo