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 \ldots 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; }