I. Waterworld
47th Annual hosted by ICPC World Championship AASTMT Problem I Waterworld Time limit: 3 seconds...
Problem Statement
Formatted from the contest statement text, with sample tests broken out into copyable blocks.
47th Annual hosted by
ICPC World
Championship AASTMT Problem I
Waterworld
Time limit: 3 seconds
Thousands of planets outside the Solar System have been discovered in recent years. An important factor
for potential life support is the availability of liquid water. Detecting water on faraway planets is not easy.
For rotating planets, a brand-new technology using relativistic quantum-polarized spectroscopy can help.
It works as follows (this is a simplified description as only three people on this planet understand how it
really works).
Assume the telescope shows the planet such that its rotating
axis is vertical and its equator is horizontal. Only the vertical
line at the center of the image (the line that covers the rotating
axis) is analyzed, because it provides the highest resolution of
the planet’s surface.
The analysis proceeds in steps of d degrees. In one step, data is
aggregated while the planet rotates by d degrees, so each step
gives information about a slice of d degrees of the planet’s
surface. The image is split into n segments of equal height,
which are analyzed separately. So the slice of d degrees is
partitioned into n areas A1 , . . . , An . For each area Ai , image
analysis produces a number that gives the percentage of Ai
covered by water. The areas Ai for one step are highlighted in
the diagram on the right.
You may assume the planet’s surface is a sphere. This means each area A2 , . . . , An−1 is a spherical
quadrilateral: it has four vertices, two sides parallel to the equator (that is, in planes parallel to the
equator’s plane) and two sides on great circles through the planet’s poles, where the great circles are d
degrees apart. At either pole, two of the four vertices collapse into the pole, so A1 and An are spherical
triangles with only one side parallel to the equator. Due to the curvature of the surface, sides that are
parallel to the equator are longer if they are closer to the equator, while sides on great circles are longer
if they are closer to the poles.
The above process is repeated for the next d degrees of rotation, and so on, a total number of m times,
until the whole surface of the planet has been covered (that is, md = 360 degrees). Your task is to
compute the percentage of the planet’s surface covered by water from the given data.Input
The first line of input contains the two integers n and m (2 ≤ n, m ≤ 1000). Each of the following n lines contains m integers ai,j (0 ≤ ai,j ≤ 100 for 1 ≤ i ≤ n and 1 ≤ j ≤ m). Each column of this matrix describes the measurements for a single step, that is, a rotation by d degrees. The number ai,j is the percentage of area Ai that is covered by water in the j th step.
Output
Output the percentage of the planet’s surface covered by water. Your answer should have an absolute error of at most 10−6 .
World Finals | ICPC 2023 Luxor
47th Annual hosted by
ICPC World
Championship AASTMTSample Tests
3 7
63 61 55 54 77 87 89
73 60 38 5 16 56 91
75 43 11 3 16 20 9551.8095238104 3
10 10 10
10 10 10
10 10 10
10 10 1010.000000000Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Key Observations
On a sphere of radius $R$, the surface area of a horizontal band of height $h$ is $2\pi Rh$.
Therefore, in the cylindrical equal-area projection, equal vertical heights correspond to equal surface areas.
Each input row describes one horizontal band of equal height, and each input column describes one rotation slice of equal angle. So every matrix entry corresponds to exactly the same surface area.
Algorithm
Read all $nm$ percentages.
Compute their arithmetic mean.
Output that mean.
Correctness Proof
We prove that the algorithm returns the correct answer.
Lemma 1.
All $nm$ cells represented by the input have equal surface area on the sphere.
Proof.
Each row has the same height, so by the equal-area formula for spherical bands each row occupies the same total surface area as every other row. Each column splits a row into equal angles, so it also splits that row into equal areas. Hence every row-column cell has the same surface area. □
Theorem.
The algorithm outputs the true percentage of the planet covered by water.
Proof.
By Lemma 1, the whole planet is partitioned into $nm$ equal-area cells, and the input value of each cell is its water percentage. The global water percentage is therefore the average of those $nm$ percentages, which is exactly what the algorithm computes. □
Complexity Analysis
The algorithm reads the matrix once, so the running time is $O(nm)$ and the memory usage is $O(1)$ besides the input values being streamed.
Implementation Notes
Using floating point only for the final average is enough; the input values themselves are integers.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
namespace {
void solve() {
int n, m;
cin >> n >> m;
long double sum = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
int x;
cin >> x;
sum += x;
}
}
cout << fixed << setprecision(9) << sum / (n * m) << '\n';
}
} // 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/2023/I-waterworld/solution.texC++ implementationcompetitive_programming/icpc/2023/I-waterworld/solution.cppStatement textcompetitive_programming/icpc/2023/I-waterworld/statement.txtStatement PDFcompetitive_programming/icpc/2023/I-waterworld/statement.pdfMetadatacompetitive_programming/icpc/2023/I-waterworld/meta.jsonYear packetcompetitive_programming/icpc/2023/contest_problems.pdf