Race Car


  • 0

    Click here to see the full article post


  • 1
    K

    In the approach 1, the sentence 'if dist[targ] > steps: continue' is redundant since the condition is never satisfied.


  • 0
    I

    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 be y units further from the target (y = 2^k and y > x). So now we have 2 options, either go back x or add 1 more A then go back x+y
    Let f(target) is the function to solve our original problem, we can easy tell that f is not monotone, so how can we be so sure that go back x is better than add 1 more A, then go back x+y?


  • 0
    D

    can you explain why you do target + 3 here??? where does this 3 come from. thanks


  • 0
    S

    I am not sure, but I think I got O(logT) time and space. My C++ solution took 4ms to run. This was a tough/fun problem though. Thanks!


  • 0
    B

    "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?


  • 0

    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.


  • 0
    K

    Really thanks for your post!!!


  • 0
    J
    This post is deleted!

  • 1
    T

    i need some help understanding the part where we turn back immediately after passing the target. why would it always be the case when not continue going be better? how would we prove f(n) < f(n+2**m) where m>=1?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.