Using only one loop USACO Bronze February 2019 - Measuring Traffic

Problems and Contests
#1 
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <limits.h>

int main(void)
{
	freopen("traffic.in", "r", stdin);
	int m;
	scanf("%d", &m);

	struct {
		int a;
		int b;
	} end = {0, INT_MAX}, pre = {0, INT_MAX}, extra = {0, 0};
	bool first_none = false, next_nones = false;

	for (int i = 0; i < m; i++) {
		int p, q;
		char *s;
		scanf("%ms %d %d", &s, &p, &q);
		if (strcmp(s, "none") == 0) {
			end.a = std::max(p, end.a);
			end.b = std::min(q, end.b);
			if (!next_nones) {
				pre.a = end.a - extra.b;
				pre.b = end.b - extra.a;
				first_none = true;
			}
		}

		if (strcmp(s, "on") == 0) {
			extra.a += p;
			extra.b += q;
			if (first_none) {
				next_nones = true;
				end.a += p;
				end.b += q;
			}
		}

		if (strcmp(s, "off") == 0) {
			extra.a -= q;
			extra.b -= p;
			if (first_none) {
				next_nones = true;
				end.a -= q;
				end.b -= p;
			}
		}
	}
	pre.a = std::max(end.a - extra.b, pre.a);
	pre.b = std::min(end.b - extra.a, pre.b);
	
	if (pre.a < 0)
		pre.a = 0;
	if (end.a < 0)
		end.a = 0;
	if (pre.b < 0)
		pre.b = 0;
	if (end.b < 0)
		end.b = 0;
	freopen("traffic.out", "w", stdout);
	printf("%d %d\n%d %d", pre.a, pre.b, end.a, end.b);
}

I first_none = true when none has appeared for first time; next_nones = true when consecutive nones occurred the first time; if next_nones is false we find s = “none” we find the pre values. I calculate the extras from on/off till the end. After the for loop, since pre’s value can be tightened from end interval, we use extras struct for that purpsose.

But the code fails in two cases 4 and 7; in both only pre is wrong

#2

Hello,

I believe that it is necessary to update “pre” everytime a “none” appears because that might provide more strict / skewed data which will reduce your current range for “pre”. Such information may be missed out if you only update pre for the first “none” and at the end.

I have submitted your code with one change and it passes(removing the if statement in the “none” case and assigning the max/min value for the pre.a and pre.b respectively):

if (strcmp(s, "none") == 0) {
    end.a = std::max(p, end.a);
    end.b = std::min(q, end.b);
    // if (!next_nones) {
    pre.a = std::max(end.a - extra.b, pre.a);
    pre.b = std::min(end.b - extra.a, pre.b);
    first_none = true;
    // }
}

Hope that helps,
Eric Liu

2 Likes