ICPC 2009 - E. Fare and Balanced
State the problem in your own words. Focus on the mathematical or algorithmic core rather than repeating the full statement.
Source-first archive entry
This page is built from the copied files in competitive_programming/icpc/2009/E-fare-and-balanced. Edit
competitive_programming/icpc/2009/E-fare-and-balanced/solution.tex to update the written solution and
competitive_programming/icpc/2009/E-fare-and-balanced/solution.cpp to update the implementation.
The website does not replace those files with hand-maintained HTML. It reads the copied source tree during the build and exposes the exact files below.
Problem Statement
Copied statement text kept beside the solution archive for direct reference.
Problem E
Fare and Balanced
Input: fare.in
Handling traffic congestion is a difficult challenge for young urban planners. Millions of drivers, each with
different goals and each making independent choices, combine to form a complex system with sometimes
predictable, sometimes chaotic behavior. As a devoted civil servant, you have been tasked with optimizing rush-
hour traffic over collections of roads.
All the roads lie between a residential area and a downtown business district. In the morning, each person living
in the residential area drives a route to the business district. The morning commuter traffic on any particular
road travels in only one direction, and no route has cycles (morning drivers do not backtrack).
Each road takes a certain time to drive, so some routes are faster than others. Drivers are much more likely to
choose the faster routes, leading to congestion on those roads. In order to balance the traffic as much as possible,
you are to add tolls to some roads so that the perceived “cost” of every route ends up the same. However, to
avoid annoying drivers too much, you must not levy a toll on any driver twice, no matter which route he or she
takes.
Figure 5 shows a collection of five roads that form routes from the residential area (at intersection 1) to the
downtown business district (at intersection 4). The driving cost of each road is written in large blue font. The
dotted arrows show the three possible routes from 1 to 4. Initially the costs of the routes are 10, 8 and 12. After
adding a toll of cost 2 to the road connecting 1 and 4 and a toll of cost 4 to the road connecting 3 and 4, the cost
of each route becomes 12.
Figure 5: Roads connecting residential area at intersection 1 to business district at intersection 4
You must determine which roads should have tolls and how much each toll should be so that every route from
start to finish has the same cost (driving time cost + possible toll) and no route contains more than one toll road.
Additionally, the tolls should be chosen so as to minimize the final cost. In some settings, it might be impossible
to impose tolls that satisfy the above conditions.
Input
Input consists of several test cases. A test case starts with a line containing an integer N (2 ≤ N ≤ 50000), which
is the number of road intersections, and R (1 ≤ R ≤ 50000), which is the number of roads. Each of the next R
lines contains three integers xi, yi, and ci (1 ≤ xi, yi ≤ N, 1 ≤ ci ≤ 1000), indicating that morning traffic takes road i
from intersection xi to intersection yi with a base driving time cost of ci. Intersection 1 is the starting residential
area, and intersection N is the goal business district. Roads are numbered from 1 to R in the given input order.
Every intersection is part of a route from 1 to N, and there are no cycles.
The last test case is followed by a line containing two zeros.
Output
For each test case, print one line containing the case number (starting with 1), the number of roads to toll (T),
and the final cost of every route. On the next T lines, print the road number i and the positive cost of the toll to
apply to that road. If there are multiple minimal cost solutions, any will do. If there are none, print
No solution. Follow the format of the sample output.
Sample Input Output for Sample Input
4 5 Case 1: 2 12
1 3 5 4 2
3 2 1 5 4
2 4 6 Case 2: No solution
1 4 10
3 4 3
3 4
1 2 1
1 2 2
2 3 1
2 3 2
0 0
Editorial
Rendered from the copied solution.tex file. The original TeX source remains
available below.
Key Observations
Write the structural observations that make the problem tractable.
State any useful invariant, monotonicity property, graph interpretation, or combinatorial reformulation.
If the constraints matter, explain exactly which part of the solution they enable.
Algorithm
Describe the data structures and the state maintained by the algorithm.
Explain the processing order and why it is sufficient.
Mention corner cases explicitly if they affect the implementation.
Correctness Proof
We prove that the algorithm returns the correct answer.
Lemma 1.
State the first key claim.
Proof.
Provide a concise proof.
Lemma 2.
State the next claim if needed.
Proof.
Provide a concise proof.
Theorem.
The algorithm outputs the correct answer for every valid input.
Proof.
Combine the lemmas and finish the argument.
Complexity Analysis
State the running time and memory usage in terms of the input size.
Implementation Notes
Mention any non-obvious implementation detail that is easy to get wrong.
Mention numeric limits, indexing conventions, or tie-breaking rules if relevant.
Code
Exact copied C++ implementation from solution.cpp.
#include <bits/stdc++.h>
using namespace std;
namespace {
void solve() {
// Fill in the full solution logic for the problem here.
}
} // namespace
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Source Files
Exact copied source-of-truth files. Edit solution.tex for the write-up and solution.cpp for the implementation.
\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{enumitem}
\title{ICPC World Finals 2009\\E. Fare and Balanced}
\author{}
\date{}
\begin{document}
\maketitle
\section*{Problem Summary}
State the problem in your own words. Focus on the mathematical or algorithmic core rather than repeating the full statement.
\section*{Key Observations}
\begin{itemize}[leftmargin=*]
\item Write the structural observations that make the problem tractable.
\item State any useful invariant, monotonicity property, graph interpretation, or combinatorial reformulation.
\item If the constraints matter, explain exactly which part of the solution they enable.
\end{itemize}
\section*{Algorithm}
\begin{enumerate}[leftmargin=*]
\item Describe the data structures and the state maintained by the algorithm.
\item Explain the processing order and why it is sufficient.
\item Mention corner cases explicitly if they affect the implementation.
\end{enumerate}
\section*{Correctness Proof}
We prove that the algorithm returns the correct answer.
\paragraph{Lemma 1.}
State the first key claim.
\paragraph{Proof.}
Provide a concise proof.
\paragraph{Lemma 2.}
State the next claim if needed.
\paragraph{Proof.}
Provide a concise proof.
\paragraph{Theorem.}
The algorithm outputs the correct answer for every valid input.
\paragraph{Proof.}
Combine the lemmas and finish the argument.
\section*{Complexity Analysis}
State the running time and memory usage in terms of the input size.
\section*{Implementation Notes}
\begin{itemize}[leftmargin=*]
\item Mention any non-obvious implementation detail that is easy to get wrong.
\item Mention numeric limits, indexing conventions, or tie-breaking rules if relevant.
\end{itemize}
\end{document}
#include <bits/stdc++.h>
using namespace std;
namespace {
void solve() {
// Fill in the full solution logic for the problem here.
}
} // namespace
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}