ICPC 2017 - C. Mission Improbable
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/2017/C-mission-improbable. Edit
competitive_programming/icpc/2017/C-mission-improbable/solution.tex to update the written solution and
competitive_programming/icpc/2017/C-mission-improbable/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.
Rapid City
event
sponsor
ICPC 2017
Problem C
Mission Improbable
Time limit: 1 second
It is a sunny day in spring and you are about to meet Patrick, a close friend and former partner in crime.
Patrick lost most of his money betting on programming contests, so he needs to pull off another job. For this
he needs your help, even though you have retired from a life of crime. You are reluctant at first, as you have
no desire to return to your old criminal ways, but you figure there is no harm in listening to his plan.
There is a shipment of expensive consumer widgets in a nearby warehouse and Patrick intends to steal as
much of it as he can. This entails finding a way into the building, incapacitating security guards, passing
through various arrays of laser beams – you know, the usual heist techniques. However, the heart of the
warehouse has been equipped with a security system that Patrick cannot disable. This is where he needs
your help.
The shipment is stored in large cubical crates, all of which have the same dimensions. The crates are stacked
in neat piles, forming a three-dimensional grid. The security system takes pictures of the piles once per hour
using three cameras: a front camera, a side camera and a top camera. The image from the front camera
shows the height of the tallest pile in each column, the image from the side camera shows the height of the
tallest pile in each row, and the image from the top camera shows whether or not each pile is empty. If the
security system detects a change in any of the images, it sounds an alarm.
Once Patrick is inside, he will determine the heights of the piles and send them to you. Figure C.1 shows a
possible layout of the grid and the view from each of the cameras.
1 4 0 5 2
2 1 2 0 1
Side camera 0 2 3 4 4
0 3 0 3 1
1 2 2 1 1
Front view Side view Top view
Front camera
Figure C.1: Grid of heights and the corresponding camera views.
1 4 0 5 1
2 1 1 0 1
0 1 3 1 4
0 3 0 1 1
2 1 1 1 1
Figure C.2: Possible grid of heights after the heist
Patrick wants to steal as many crates as possible. Since he cannot disable the security system, he plans to
fool it by arranging the remaining crates into piles so that the next set of camera images are the same. In
the above example, it is possible to steal nine crates. Figure C.2 shows one possible post-heist configuration
that appears identical to the security system.
Rapid City
event
sponsor
ICPC 2017
Patrick asks you to help him determine the maximum number of crates that can be stolen while leaving a
configuration of crates that will fool the security system. Will you help him pull off this final job?
Input
The first line of input contains two integers r (1 ≤ r ≤ 100) and c (1 ≤ c ≤ 100), the number of rows and
columns in the grid, respectively. Each of the following r lines contains c integers, the heights (in crates) of
the piles in the corresponding row. All heights are between 0 and 109 inclusive.
Output
Display the maximum number of crates that can be stolen without being detected.
Sample Input 1 Sample Output 1
5 5 9
1 4 0 5 2
2 1 2 0 1
0 2 3 4 4
0 3 0 3 1
1 2 2 1 1
Sample Input 2 Sample Output 2
2 3 30
50 20 3
20 10 3
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 2017\\C. Mission Improbable}
\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;
}