ARTICLES

USACO Jan 2020 Bronze - Race

By adam

\(O(1)\) solution

I am surprised that the solution posted is \(O(n)\) since \(n\) can be as large as \(10^9\).

In coming up with a solution for \(O(1)\) we consider three phases. The first phase accelerates the ‘left hand’ speed until it reaches the terminal speed. If it can’t reach the terminal speed then it just reaches whatever speed it can and terminates.

The second phase is like a palindrome stage, where I remove similar increasing speeds from both ends, kind of like climbing up a tall peak from both ends. This happens because I would like to accelerate as much as possible but I have to leave a similar region for deacceleration into the terminal speed.

The last phase we take care of any remaining distance that needs to be covered.

All these three phases occur in \(O(1)\) time, note that there is a binary search occuring in the second phase, but because I only look at three numbers, i.e. the lower and upper bounds are tight for the binary search. I could have been done in a fixed size loop as well.


import math
k, n = map(int, input().split())
debug = False


def solve(remainder, terminal_speed):
    if remainder == 0:
        return terminal_speed + 1

    # (rs+high)(high-rs+1) = remainder
    # high^2 - rs^2 + rs + high = remainder
    # high(high+1) = remainder+rs^2-rs
    right_speed = terminal_speed + 1
    close = int(math.sqrt(remainder + right_speed*right_speed
                          - right_speed)) + 1
    if debug:
        print("Upper bound guess", close)
    left = max(right_speed, close-2)
    right = close
    while left <= right:
        mid = (left+right)//2
        dist = (right_speed+mid)*(mid-right_speed+1)
        # print("Guessing", mid, dist, remainder)
        if dist > remainder:
            right = mid-1
        elif dist == remainder:
            right = mid
            break
        else:
            left = mid+1

    time_spent = (right-right_speed+1)*2 + right_speed
    remainder -= (right_speed+right)*(right-right_speed+1)
    if debug:
        print("Guess", right, "remainder", remainder, "time", time_spent)
    if remainder == 0 or remainder < terminal_speed:
        return time_spent
    else:
        while True:
            right += 1
            remainder -= right
            time_spent += 1
            # print("remainder", remainder, "time", time_spent)
            if remainder < terminal_speed:
                return time_spent
            remainder -= right
            time_spent += 1
            # print("remainder", remainder, "time", time_spent)
            if remainder < terminal_speed:
                return time_spent


for _ in range(n):
    right_speed = int(input())
    # time to reach the same speed as the terminal speed
    # (1+k)*k/2
    if (1+right_speed)*right_speed//2 >= k:
        close = int(math.sqrt(k*2))-1
        while (1+close)*close//2 < k:
            close += 1
        print(close)
    else:
        remainder = k - (1+right_speed)*right_speed//2 - 1
        if debug:
            print("Solving for", right_speed)
            print("Remainder after", right_speed+1, "s", remainder)
        print(solve(remainder, right_speed))

How to create tight bounds

Note that a lot of computation involves summing up an increasing sequence of numbers, such as \(1 \cdots k\) or \(k \cdots l\). These all take the form

\[ \frac{(k+l)(l-k+1)}{2} \]

Since we typically want to achieve a certain distance without overshooting we can do the following:

\[ \frac{l^2+l-k^2+k}{2} = d \]

For the phases above the lower number \(k\) is fixed, so we just need to bound \(l\). Rewriting the above

\[ l(l+1) = 2d+k^2-k \]

Then an upper bound for \(l\) and a lower bound for \(l\) is

\begin{eqnarray} l_{\text{upper}} &=& \sqrt{2d+k^2-k}\\\
l_{\text{lower}} &=& l_{\text{upper}} - 1 \end{eqnarray}

This simplifies searching for an \(l\).

End conditions

The only other tricky part is considering the remainder. Note that right edge of remainder must abut some terminal speed. That means that if the remainder itself can be covered within the terminal speed then that is sufficient to cover the remaining distance and to cross over into the terminal speed region.