ICPC 2013 - I. Pirate Chest
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/2013/I-pirate-chest. Edit
competitive_programming/icpc/2013/I-pirate-chest/solution.tex to update the written solution and
competitive_programming/icpc/2013/I-pirate-chest/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.
ICPC 2013
2013 World Finals
St. Petersburg
HOSTED BY ITMO
Problem I
Pirate Chest
Time Limit: 15 seconds
Pirate Dick finally had enough of fighting, marauding, theft, and making life miserable for many on
the open seas. So he decided to retire, and he found the perfect island to spend the rest of his days on,
provided he does not run out of money. He has plenty of gold coins now, and he wants to store them in a
chest (he is a pirate after all). Dick can construct a rectangular chest with integer dimensions of any size
up to a specified maximum size for the top but with an arbitrary integer height. Now he needs a place to
hide the chest. While exploring the island, he found the perfect solution.
Dick will hide his chest by submerging it in a murky pond. The pond has a rectangular surface, and it
completely fills the bottom of a valley that has high vertical rocky walls. Dick surveyed the pond and
knows its depth for each of the squares of a Cartesian coordinate grid system placed on the pond surface.
When Dick submerges the chest, it will sink as far as possible until it touches the bottom. The top of the
chest will remain parallel to the pond’s surface and the chest will be aligned with the grid squares. The
water displaced by the submerged chest will raise the level of the pond’s surface (this will occur even
if there is no space around the chest for the displaced water to rise). The walls of the valley are high
enough that the water can never splash out of the valley. Of course, since the chest must be invisible, its
top must be strictly below the surface of the pond. Your job is to find the volume of the largest chest that
Pirate Dick can hide this way.
In Figure I.1, the leftmost image shows a pond, the middle image shows a possible placement of a chest
of volume 3, and the rightmost image shows a placement of a chest of volume 4, which is the maximum
possible volume. Note that if the second chest were made one unit taller, its top would be visible because
it would be at exactly the same height as the surface of the water.
Figure I.1: Illustration of Sample Input 1.
Input
The input consists of a single test case. A test case starts with a line containing four integers a, b, m, and
n (1 ≤ a, b, m, n ≤ 500). The pond’s surface dimensions are m × n and the maximum size of the top
(and bottom) of the chest is a × b. In addition, a and b are small enough that it is not possible to cover
the entire pond with a chest with top size a × b. Each of the remaining m lines in a test case contains n
integers di,j specifying the pond’s depth at grid square (i, j), where 0 ≤ di,j ≤ 109 for each 1 ≤ i ≤ m
and 1 ≤ j ≤ n.
ICPC 2013
2013 World Finals
St. Petersburg
HOSTED BY ITMO
Output
Display the maximum volume of a rectangular chest with integer dimensions (where one of the dimen-
sions of the top is bounded by a and the other is bounded by b) that can be completely submerged below
the surface of the pond. If no chest can be hidden in the pond, display 0.
Sample Input 1 Sample Output 1
3 1 2 3 4
2 1 1
2 2 1
Sample Input 2 Sample Output 2
4 1 1 5 12
2 0 2 2 2
Sample Input 3 Sample Output 3
2 3 3 5 18
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2
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 2013\\I. Pirate Chest Time Limit: 15 seconds}
\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;
}