Race Car


RA^k1RA^k2 can't always be written as A^k2RRA^k1, for example:
RARAA ends up at 2 while AARRA ends up at 4.
Also, when we drive pass the target, let's say we are
x
units passed the target, if we add 1 more A, we'll bey
units further from the target (y
= 2^k andy
>x
). So now we have 2 options, either go backx
or add 1 more A then go backx+y
Letf(target)
is the function to solve our original problem, we can easy tell thatf
is not monotone, so how can we be so sure that go backx
is better than add 1 more A, then go backx+y
?

"A key claim is that k_i is bounded by a+1, where a is the smallest integer such that 2^a ≥ target  basically, if you drive past the target, you don't need to keep driving. This is because it adds another power of two (as 2^k_i −1=∑{j<k_i} 2^j
) to the position that must get erased by one or more negative terms later (in whole or in part), as it is not part of the target."Did anyone else understand this part?

Hey @brendon4565 to me, that basically means if you drive past your target, you always choose to turn around. You never choose to keep accelerating away from the target. I’d you did choose to keep accelerating away from the target, you’d do so by a power of 2 each time, those additional power of 2s away are a waste of effort and if we eventually choose to stop accelerating away from the target, then we have the reverse pattern to perform all the way back till we correct our original incorrect choice to accelerate away from the target which we passed.