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

I. A Safe Bet

Problem ID: safe Safe Ltd. is a company that manufactures high-quality safes. Its latest invention is an optical closure mechanism that uses a laser beam passing through a rectangular grid with several mirrors. Laser- @ @...

Updated May 21, 2026
Track ICPC
Year 2012
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

Safe Ltd. is a company that manufactures high-quality safes. Its latest invention is an optical closure mechanism that uses a laser beam passing through a rectangular grid with several mirrors.

Laser-          @
                @                                      Laser-         @
                                                                      @
                              @
                              @                                                      @
                                                                                     @
    @                                                     @                      -
    @                                                     @
                  @        - Detector                                    @            Detector
                  @                                                      @
Beam detected, safe open                            Beam not detected, alarm raised

When the laser is activated, a beam enters the top row of the grid horizontally from the left. The beam is reflected by every mirror that it hits. Each mirror has a 45 degree diagonal orientation, either or . If the beam exits the bottom row of the grid horizontally to the right, it is detected and the safe opens (see the left side of the figure above). Otherwise the safe remains closed and an alarm is raised. Each safe has a missing mirror, which prevents the laser beam from traveling successfully through the grid (see the right side of the figure above). The safe has a mechanism that enables the user to drop a single mirror into any empty grid cell. A legitimate user knows the correct position and orientation of the missing mirror ( in row 4 column 3 above) and can thus open the safe. Without this knowledge the user has to guess correctly, which can be difficult for safes with large grids. Your job is to determine if particular safes are actually secure. A secure safe does not open right away without inserting a mirror, and there is at least one valid location and orientation for the missing mirror. There may indeed be multiple such locations and orientations.

Input

Each test case describes a single safe and starts with a line containing four integer numbers r, c, m, and n (1 ≤ r, c ≤ 1 000 000 and 0 ≤ m, n ≤ 200 000). The mechanism’s grid has r rows and c columns. Each of the next m lines contains two integer numbers ri and ci (1 ≤ ri ≤ r and 1 ≤ ci ≤ c) specifying that there is a mirror in row ri column ci . The following n lines specify the positions of the  mirrors in the same way. The m + n positions of the mirrors are pairwise distinct.

Output

For each test case, display its case number followed by:

  • 0 if the safe opens without inserting a mirror.
  • k r c if the safe does not open without inserting a mirror, there are exactly k positions where inserting a mirror opens the safe, and (r, c) is the lexicographically smallest such row, column position. A position where both a and a  mirror open the safe counts just once.
  • impossible if the safe cannot be opened with or without inserting a mirror.

Sample Input Output for Sample Input 5 6 1 4 Case 1: 2 4 3 2 3 Case 2: 0 1 2 Case 3: impossible 2 5 4 2 5 5 100 100 0 2 1 77 100 77 100 100 0 0

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/2012/I-a-safe-bet/solution.texC++ implementationcompetitive_programming/icpc/2012/I-a-safe-bet/solution.cppStatement textcompetitive_programming/icpc/2012/I-a-safe-bet/statement.txtStatement PDFcompetitive_programming/icpc/2012/I-a-safe-bet/statement.pdfMetadatacompetitive_programming/icpc/2012/I-a-safe-bet/meta.jsonYear packetcompetitive_programming/icpc/2012/contest_problems.pdf