ICPC 2008 - F. Glenbow Museum
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/2008/F-glenbow-museum. Edit
competitive_programming/icpc/2008/F-glenbow-museum/solution.tex to update the written solution and
competitive_programming/icpc/2008/F-glenbow-museum/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.
Problem F
Glenbow Museum
Input file: museum.in
The famous Glenbow Museum in Calgary is Western Canada’s largest museum, with exhibits ranging from art to
cultural history to mineralogy. A brand new section is being planned, devoted to brilliant computer programmers just
like you. Unfortunately, due to lack of space, the museum is going to have to build a brand new building and relocate
into it.
The size and capacity of the new building differ from those of the original building. But the floor plans of both
buildings are orthogonal polygons. An orthogonal polygon is a polygon whose internal angles are either 90° or 270°.
If 90° angles are denoted as R (Right) and 270° angles are denoted as O (Obtuse) then a string containing only R and
O can roughly describe an orthogonal polygon. For example, a rectangle (Figure 1) is the simplest orthogonal
polygon and it can be described as RRRR (the angles are listed in counter-clockwise order, starting from any corner).
Similarly, a cross-shaped orthogonal polygon (Figure 2) can be described by the sequence RRORRORRORRO,
RORRORRORROR, or ORRORRORRORR. These sequences are called angle strings.
Figure 1: A rectangle Figure 2: A cross-shaped polygon
Of course, an angle string does not completely specify the shape of a polygon – it says nothing about the length of
the sides. And some angle strings cannot possibly describe a valid orthogonal polygon (RRROR, for example).
To complicate things further, not all orthogonal polygons are acceptable floor plans for the museum. A museum
contains many valuable objects, and these objects must be guarded. Due to cost considerations, no floor can have
more than one guard. So a floor plan is acceptable only if there is a place within the floor from which one guard can
see the entire floor. Similarly, an angle string is acceptable only if it describes at least one acceptable polygon. Note
that the cross-shaped polygon in Figure 2 can be guarded by someone standing in the center, so it is acceptable. Thus
the angle string RRORRORRORRO is acceptable, even though it also describes other polygons that cannot be
properly guarded by a single guard.
Help the designers of the new building determine how many acceptable angle strings there are of a given length.
Input
The input file contains several test cases. Each test case consists of a line containing a positive integer L (1≤L≤1000),
which is the desired length of an angle string.
The input will end with a line containing a single zero.
Output
For each test case, print a line containing the test case number (beginning with 1) followed by the number of
acceptable angle strings of the given length. Follow the format of the sample output.
Sample Input Output for the Sample Input
4 Case 1: 1
6 Case 2: 6
0
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 2008\\F. Glenbow Museum}
\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;
}