kgargdun's blog

By kgargdun, history, 3 years ago, In English

Hi, I am on my adventure to solve CSES problem set. I found this nice editorial for Range Query section here

But i guess some new problems were added or were skipped there. I am struggling in one such problem. here Any hint/approach will be highly appreciated!

EDIT: Yay AC ! I tried to code it as simple as possible.

AC solution
  • Vote: I like it
  • -2
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The main challenge with the problem is finding $$$cost(i) = \min\limits_{1 \leq j \leq n}(p_j + |i-j|)$$$ quickly

We can split the cost into two parts: $$$cost(i) = \min(p_j + (i - j))$$$ when $$$j \leq i$$$ and $$$cost(i) = \min(p_j + (j - i))$$$ when $$$j \geq i$$$

Combining them together, we get $$$cost(i) = \min(\min\limits_{1 \leq j \leq i} (p_j - j) + i, \min\limits_{i \leq j \leq n}(p_j + j) - i)$$$

We can use two point-update, range-minimum-query segment trees to achieve this. One stores $$$p_i - i$$$ and the other stores $$$p_i + i$$$.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by kgargdun (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Still, there is a bug

            lli left = query(arr, tree2, 0, n-1, **1**, a-1, 1);

should be replaced with

            lli left = query(arr, tree2, 0, n-1, **0**, a-1, 1);