Can anyone share their approach for the problem https://atcoder.jp/contests/arc101/tasks/arc101_a?
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 161 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | awoo | 154 |
8 | Dominater069 | 154 |
10 | luogu_official | 150 |
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
k
that includes the 0. Let's say the distance you traveled from zero to theleft most
candle in the window isdist_left
and the distance you traveled from zero to theright most
candle 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_right
anddist_left
for 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