Can anyone share their approach for the problem https://atcoder.jp/contests/arc101/tasks/arc101_a?
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 150 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
Can anyone share their approach for the problem https://atcoder.jp/contests/arc101/tasks/arc101_a?
| Name |
|---|



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.
If the coordinates already have a 0, then you can simply find a window of length
kthat includes the 0. Let's say the distance you traveled from zero to theleft mostcandle in the window isdist_leftand the distance you traveled from zero to theright mostcandle in the window isdist_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_rightanddist_leftfor each window. (too much?)My submission
Thanks for the reply. Why can't we just take the nearest K candles and follow the above approach?
Consider this example -
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 go0 -> 6 -> 7, distance = 7