Various Programming Challenge Solutions

I don't provide the full problem specifications on this page due to possible copyright issues. Links to the original problem specs are provided below along with the date accessed, which should allow you to use Internet Archive if the original URL hosting a problem specification ever meaningfully changes.

Kattis: Need for Speed [Spec] (2024-03-21)

This problem was solved in the context of competitive programming practice, solving problems in a group setting. I was the writer, but other members of the group provided the vast majority of the thinking/solving.

The group’s original solution:

I also did a little bit of cleanup afterwards on my own for a nicer solution:

#!/usr/bin/env python3

from sys import stdin

(n, t) = [int(s) for s in stdin.readline().strip().split()]
data = [[int(x) for x in s.strip().split()] for s in stdin.readlines()]

(lo, hi) = (float(-1e7), float(1e7))
while hi - lo >= 1e-7:
    c = (hi + lo) / 2
    real_t = 0
    for dist, speed in data:
        real_speed = speed + c
        if real_speed <= 0:
            real_t = 2 * t  # arbitrary large value
        # speed = dist / time  -->  time = dist / speed
        real_t += dist / real_speed
    if real_t > t:
        lo = c
        hi = c