decoder__'s blog

By decoder__, history, 4 years ago, In English

Can anyone share their approach for the problem https://atcoder.jp/contests/arc101/tasks/arc101_a?

  • Vote: I like it
  • +4
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

One observation is that since you always start with 0, you will go light some candles(possibly zero) on the left of zero and some candles(again, possibly zero) on the right of zero. Now you will have to travel some distance twice, either the left or right. This is what the best path would look like.

Here's what I mean,
1. Go left
2. Go back to 0
3. Go right
(1)<------0-------->(3)
(2)------->
OR
1. Go right
2. Go back to 0
3. Go left
(3)<------0--------> (1)
          <--------- (2)

If the coordinates already have a 0, then you can simply find a window of length k that includes the 0. Let's say the distance you traveled from zero to the left most candle in the window is dist_left and the distance you traveled from zero to the right most candle in the window is dist_right.

Answer for this window will be min( dist_left*2 + dist_right, dist_left + dist_right*2 ).

Final answer will be the minimum over all such windows that include 0.

If the coordinates don't have a 0, you can simply insert one, sort the array again and increment the window length by 1. Then perform the above operations. You can use some sort of a difference array to get absolute differences of coordinates, and then store the position of zero, and then a prefix array to find the dist_right and dist_left for each window. (too much?)

My submission

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the reply. Why can't we just take the nearest K candles and follow the above approach?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Consider this example -

      7 3
      -100 -5 0 6 7 8 9
      

      If you try to start from 0 and go to the nearest K candles, you'd go like this 0 -> -5 -> 6, distance = 16, whereas you can go 0 -> 6 -> 7, distance = 7