EP Ethan Pham Project Euler, competitive programming, and notes on the things I keep studying.
ICPC 2011
ICPC 2011

I. Mummy Madness

Problem ID: mummy During an excursion to the desert at the 2011 ACM-ICPC World Finals, you come across an old Egyptian tomb. Unfortunately, opening the tomb turns out to be a bad idea: all of a sudden, what was just a few moments ago an empty desert has now...

Updated May 21, 2026
Track ICPC
Year 2011
Statement Text + PDF
TeXC++Statement textStatement PDF
Problem statement

Problem Statement

Formatted from the contest statement text, with sample tests broken out into copyable blocks.

Statement text Statement PDF

During an excursion to the desert at the 2011 ACM-ICPC World Finals, you come across an old Egyptian tomb. Unfortunately, opening the tomb turns out to be a bad idea: all of a sudden, what was just a few moments ago an empty desert has now become a desert crawling with grumpy mummies (you would be grumpy too if you were suddenly awakened after a few thousand years of peaceful sleep).2 Faced with this murderous mass of mad mummies, your only chance is to run for it and try to escape before they catch you. The question is: how long will it take before a mummy catches you, assuming neither you nor the mummies ever get tired? We model the desert as a grid of squares. You and the mummies take turns making moves on the grid. You make the first move. In your turns, you can move to any of the eight squares adjacent to your current location, or you can choose to stand still. In the mummies’ turns, each mummy simply moves to the adjacent square that brings it closest to you (measured by Euclidean distance, assuming that you and all the mummies stand in the centers of their respective squares). It is possible for two mummies to occupy the same square. A time step consists of your move followed by the mummies’ moves. A mummy catches you if it moves to the square where you are located, or if you move to the square occupied by the mummy. Of course, you try to avoid being caught for as long as possible. After how many time steps will you be caught?

Figure I.1: A mummy chase

The figure illustrates what might happen if you are being chased by four mummies. The square labeled H is your initial position, and the squares labeled M are the initial positions of mummies. After four time steps, you are caught by the mummy whose initial position was (3, 4) with respect to your initial position. 2 Fortunately, after solving this problem, you woke up safe and sound in a hotel room in Florida. The enraged mummies had just been a dream.

Or had they?

ICPC 2011 World Finals Problem I: Mummy Madness

Input

The input consists of several test cases. Each test case begins with an integer n (0 ≤ n ≤ 105 ) giving the number of mummies in the desert. The following n lines each contain two integers x and y, indicating that there is initially a mummy at coordinates (x, y) of the desert, where x and y are both bounded by 106 in absolute value. Your starting position is (0, 0), and no mummy starts at this position. The last test case is followed by a line containing the number −1.

Output

For each test case, display its test case number followed by the maximum number of time steps until you are caught (measured as the total number of turns that you get), or the word “never” if you can avoid capture indefinitely. Follow the format of the sample output.

Sample Tests

Sample
Sample Input 
  4
  -3 5
  3 4
  -6 -2
  1 -5
  1
  0 -1
  -1

ICPC 2011 World Finals Problem I: Mummy Madness
Sample Output 
Case 1: 4
Case 2: never
Editorial

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

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

  1. Describe the data structures and the state maintained by the algorithm.

  2. Explain the processing order and why it is sufficient.

  3. 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.

Implementation

Code

C++ solution used for this page.

C++

Clean code view with a raw-file link when you want the original source.

Raw file 
#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;
}
Resources

Source Files and Assets

Raw files are still available here when you want the original TeX, C++, or statement assets.

Show raw files
TeX write-upcompetitive_programming/icpc/2011/I-mummy-madness/solution.texC++ implementationcompetitive_programming/icpc/2011/I-mummy-madness/solution.cppStatement textcompetitive_programming/icpc/2011/I-mummy-madness/statement.txtStatement PDFcompetitive_programming/icpc/2011/I-mummy-madness/statement.pdfMetadatacompetitive_programming/icpc/2011/I-mummy-madness/meta.jsonYear packetcompetitive_programming/icpc/2011/contest_problems.pdf