XCODE06 - Editorial

Problem Link



Author: Sahil Rajput

Tester: Sahil Rajput

Editorialist: Sahil Rajput




Maths, Dynamic Programming, Segment Tree, Sparse Table, Moving Window


You can tackle this question with multiple approaches, one is simple DP algorithm, make an array dp[i][j] which will store the maximum happiness value that you can gain when you're on poisition j at i th launching.

You can calculate value by this formula:

dp[i][j] = max [k =  - t * d…t * d] (dp[i — 1][j + k] + b[i] — |a[i] — j|) where t = t[i] — t[i — 1].

If you look up for all k, since the table’s size is O(mn), the overall complexity will be O(mn^2). You can also use segment tree or sparse table but the original and intended solution uses sliding window maximum since the interval [j — t * d, j + t * d] is independent for all the fireworks. It can be implemented by simple array or deque. This will speed up to calculate formula, and overall complexity will be O(mn).

Solution Link

[Setter's Solution][6]
1 Like