ICPC 2023 - I. Waterworld
The planet is partitioned into n horizontal bands and m equal rotation slices. For each band-slice cell we are given the percentage covered by water, and we must compute the percentage of the whole planet covered by w...
Source-first archive entry
This page is built from the copied files in competitive_programming/icpc/2023/I-waterworld. Edit
competitive_programming/icpc/2023/I-waterworld/solution.tex to update the written solution and
competitive_programming/icpc/2023/I-waterworld/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.
World Finals | ICPC 2023 Luxor
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 .
47th ICPC World Championship Problem I: Waterworld © ICPC Foundation 17
World Finals | ICPC 2023 Luxor
47th Annual hosted by
ICPC World
Championship AASTMT
Sample Input 1 Sample Output 1
3 7 51.809523810
63 61 55 54 77 87 89
73 60 38 5 16 56 91
75 43 11 3 16 20 95
Sample Input 2 Sample Output 2
4 3 10.000000000
10 10 10
10 10 10
10 10 10
10 10 10
47th ICPC World Championship Problem I: Waterworld © ICPC Foundation 18
Editorial
Rendered from the copied solution.tex file. The original TeX source remains
available below.
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
Exact copied C++ implementation from solution.cpp.
#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
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 2023\\I. Waterworld}
\author{}
\date{}
\begin{document}
\maketitle
\section*{Problem Summary}
The planet is partitioned into $n$ horizontal bands and $m$ equal rotation slices. For each band-slice
cell we are given the percentage covered by water, and we must compute the percentage of the whole
planet covered by water.
\section*{Key Observations}
\begin{itemize}[leftmargin=*]
\item On a sphere of radius $R$, the surface area of a horizontal band of height $h$ is $2\pi Rh$.
\item Therefore, in the cylindrical equal-area projection, equal vertical heights correspond to equal
surface areas.
\item 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.
\end{itemize}
\section*{Algorithm}
\begin{enumerate}[leftmargin=*]
\item Read all $nm$ percentages.
\item Compute their arithmetic mean.
\item Output that mean.
\end{enumerate}
\section*{Correctness Proof}
We prove that the algorithm returns the correct answer.
\paragraph{Lemma 1.}
All $nm$ cells represented by the input have equal surface area on the sphere.
\paragraph{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. \qed
\paragraph{Theorem.}
The algorithm outputs the true percentage of the planet covered by water.
\paragraph{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. \qed
\section*{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.
\section*{Implementation Notes}
\begin{itemize}[leftmargin=*]
\item Using floating point only for the final average is enough; the input values themselves are integers.
\end{itemize}
\end{document}
#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;
}