F. Contour Mapping
Problem ID: contour A contour map represents the topography of a given region. Lines on a contour map represent constant elevations. For example, a contour map might contain a line that represents points with an elevation of 100 meters above mean sea level,...
Problem Statement
Formatted from the contest statement text, with sample tests broken out into copyable blocks.
A contour map represents the topography of a given region. Lines on a contour map represent constant elevations. For example, a contour map might contain a line that represents points with an elevation of 100 meters above mean sea level, another line representing 200 meters elevation, and so on.
The Association for Contour Mapping (ACM) needs a program to produce contour maps from data files containing elevation measurements collected by a satellite. They are especially interested in the total length of all contour lines on each map. The elevation data is in the form of sequences of integers that represent elevations measured at regular intervals along scan lines that run from west to east. The spacing of the scan lines is such that each elevation measurement in the interior of the data set has six nearest neighbors and is equidistant from them (when elevation is ignored), as shown in Figure 5 and Figure 6.
Figure 5 Figure 6The policy of the ACM is to approximate the actual terrain by a set of triangles constructed by connecting each elevation measurement to its nearest neighbors by straight line segments. Each of these triangles is then treated as a planar surface, where the plane is determined by the coordinates, including elevation, of the vertices. If the triangles are projected onto the zero-elevation plane, they form a set of equilateral triangles.
In the figures above, the black numbers represent elevation data and the red dashed lines and numbers represent contour lines. Figure 5 contains a single contour line at elevation 5. Figure 6 contains multiple contour lines at elevations 6 and 9. A contour line may pass through the interior of a triangle or run along an edge of a triangle.
Because of the way the data points are interlaced, even-numbered scan lines contain one more data point than odd-numbered scan lines. In each figure, the first scan line is shown at the top.
Input
The input consists of several test cases, each containing a set of elevation data. Each test case begins with a line containing four integers as follows:
- s (2 ≤ s ≤ 100) is the number of scan lines of data in the test case.
- p (1 ≤ p ≤ 100) is the number of elevation measurements on the odd numbered scan lines. The even- numbered scan lines contain p + 1 elevation measurements.
- d (1 ≤ d ≤ 10) is the distance between each elevation measurement and its nearest neighbors when elevation is ignored (equals the side-length of the equilateral triangles in the figures.)
- h (1 ≤ h ≤ 1000) is the elevation increment between contour lines in the desired map. The final contour map contains a contour line wherever the elevation is an exact multiple of h. Note that a map may contain multiple contour lines for a given elevation. Where a region is level, contour lines are shown only for the boundaries. (See for example the contour line of elevation 9 in Figure 6.)
The first line of each test case is followed by additional lines containing elevation data as a sequence of non- negative integers no larger than 106. The first p integers represent the elevation measurements on the first scan line, from left to right. The next p + 1 integers represent the elevation measurements on the second scan line, reading from left to right. The data continues in order, providing p integers for each odd-numbered scan line and p + 1 integers for each even-numbered scan line, until all the elevation data has been provided. Each test case ends with an empty line.
The input is terminated with a line containing a single zero.
Output
For each test case, display its case number followed by the total length of all the contour lines on the contour map, rounded to the nearest integer. Follow the format of the sample output.
Sample Tests
3 2 5 5
1 1
1 9 1
1 1
4 4 5 3
5 7 7 5
5 9 9 9 5
9 9 9 9
7 9 9 9 7
0Case 1: 15
Case 2: 54Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
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
C++ solution used for this page.
#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 and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.
Show raw files
competitive_programming/icpc/2010/F-contour-mapping/solution.texC++ implementationcompetitive_programming/icpc/2010/F-contour-mapping/solution.cppStatement textcompetitive_programming/icpc/2010/F-contour-mapping/statement.txtStatement PDFcompetitive_programming/icpc/2010/F-contour-mapping/statement.pdfMetadatacompetitive_programming/icpc/2010/F-contour-mapping/meta.jsonYear packetcompetitive_programming/icpc/2010/contest_problems.pdf