Let's first focus on predicting the range of possible rates of traffic at the end of the highway (past mile N). To do this, we start with a large possible range [a,b] (initially set to [−999999999,+999999999]) and narrow / modify it as we scan through the different highway components from miles 1…N. Every time we see a sensor reading directly from the highway, this clips the possible range [a,b] to the range given by the sensor. Every time we see an on-ramp with range [a′,b′], the new range of possible traffic flows is [a+a′,b+b′]. Similarly, when we see an off-ramp with range [a′,b′], the new range of possible traffic flow values is [a−b′,b−a′] (after this update, we set the lower end of the range to zero if it goes negative, since we can't have a negative rate of traffic flow).
Predicting the range of possible initial flows is similar and essentially symmetric, where we scan backwards and keep track of a working range [a,b] that is narrowed / modified appropriately by each highway feature.
My C++ code for solving the problem is the following. It should hopefully be easy to read even for those using other languages.
#include <iostream> #include <fstream> using namespace std; int main(void) { int N, A[100], B[100]; string T[100]; ifstream fin ("traffic.in"); fin >> N; for (int i=0; i<N; i++) fin >> T[i] >> A[i] >> B[i]; ofstream fout ("traffic.out"); int a = -999999999, b = 999999999; for (int i=N-1; i>=0; i--) { if (T[i] == "none") { a = max(a, A[i]); b = min(b, B[i]); } if (T[i] == "off") { a += A[i]; b += B[i]; } if (T[i] == "on") { a -= B[i]; b -= A[i]; a = max(0,a); } } fout << a << " " << b << "\n"; a = -999999999, b = 999999999; for (int i=0; i<N; i++) { if (T[i] == "none") { a = max(a, A[i]); b = min(b, B[i]); } if (T[i] == "on") { a += A[i]; b += B[i]; } if (T[i] == "off") { a -= B[i]; b -= A[i]; a = max(0,a); } } fout << a << " " << b << "\n"; return 0; }