Prefix Sum Solution for USACO Bronze December 2015 Problem 2: Speeding Ticket

Problems and Contests
#1

Hello,

I am working on USACO Bronze December 2015 Problem 2: Speeding Ticket. Link: Speeding Ticket.

I’ve read through the USACO Guide official solution for it. Link: solution

I feel like it can be done faster with prefix sums. The idea being that instead of breaking everything up into segments of length 1, you can iterate with 2 pointers. You increment the road pointer when Bessie has traveled more than the prefix sum of the current road index. You increment Bessie’s index when there is more road left to traverse.

I coded it up and it passed 6/10 test cases. I cannot seem to figure out why it does not work. What is the counter example?

Here is my current code:


#include <cstdio>
using namespace std;

inline int max(int a, int b) {
    return (a >= b ? a : b);
}

inline int min(int a, int b) {
    return (a <= b ? a : b);
}

int main() {

    FILE* input_file = fopen("speeding.in", "r");
    FILE* output_file = fopen("speeding.out", "w");

    int n, m;
    fscanf(input_file, "%d %d", &n, &m);

    int* road_prefix_sum = new int[n];
    int* road_speed = new int[n];
    int* travel_length = new int[m];
    int* travel_speed = new int[m];

    int speed, dist, total=0;

    for (int i = 0; i < n; i++) {
        fscanf(input_file, "%d %d", &dist, &speed);
        total += dist;
        road_prefix_sum[i] = total;
        road_speed[i] = speed;
    }

    for (int i = 0; i < m; i++) {
        fscanf(input_file, "%d %d", &dist, &speed);
        travel_length[i] = dist;
        travel_speed[i] = min(100, speed);
    }

    int road_index = 0;
    int travel_index = 0;
    int travel_total = 0;
    int max_speeding = 0;

    while (travel_total < 100 || road_index < n) {
        if (travel_total < road_prefix_sum[road_index]) {
            max_speeding = max(max_speeding,  travel_speed[travel_index] - road_speed[road_index]);
            travel_total += travel_length[travel_index];
            travel_index++;
        } else {
            if (travel_total != road_prefix_sum[road_index]) {
                max_speeding = max(max_speeding, travel_speed[travel_index] - road_speed[road_index]);
            }
            road_index++;
        }
    }

    fprintf(output_file, "%d", max_speeding);

    fclose(input_file);
    fclose(output_file);

    return 0;
}

Appreciate the help. Thanks in advance!

#2

bro’s using c-style io and arrays in c++ :skull:

1 Like
#3

I think it has something to do with the part

max_speeding = max(max_speeding, travel_speed[travel_index] - road_speed[road_index]);

in the else statement. I’m pretty sure it should be

max_speeding = max(max_speeding, travel_speed[travel_index-1] - road_speed[road_index+1]);

A couple of other things: Technically prefix sums doesn’t actually improve the big O time complexity, because the speed could change every unit. And even if it does, the code is just more complicated that way. That being said, if you just wanted practice with prefix sums, why are you handling bessie’s segments differently than the road’s segments? You are using prefix sums for the road, but with bessie you’re keeping track of the overall sum? And furthermore, the indexing is inconsistent – road_index is the road segment last traveled, while travel_index is the segment to be traveled next. I think that’s what’s causing the error.

#4

@TheBeast5520 Thanks so much for the help! Really appreciate it.

#5

Bro lemme cook :sob: :sob: