ICPC 2011 - J. Pyramids
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/2011/J-pyramids. Edit
competitive_programming/icpc/2011/J-pyramids/solution.tex to update the written solution and
competitive_programming/icpc/2011/J-pyramids/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 J
Pyramids
Problem ID: pyramids
It is not too hard to build a pyramid if you have a lot of identical cubes. On a flat foundation you lay, say, 10 × 10
cubes in a square. Centered on top of that square you lay a 9 × 9 square of cubes. Continuing this way you end up
with a single cube, which is the top of the pyramid. The height of such a pyramid equals the length of its base, which
in this case is 10. We call this a high pyramid.
If you think that a high pyramid is too steep, you can proceed as follows. On the 10 × 10 base square, lay an 8 × 8
square, then a 6 × 6 square, and so on, ending with a 2 × 2 top square (if you start with a base of odd length, you end
up with a single cube on top, of course). The height of this pyramid is about half the length of its base. We call this a
low pyramid.
Once upon a time (quite a long time ago, actually) there was a pharaoh who inherited a large number of stone cubes
from his father. He ordered his architect to use all of these cubes to build a pyramid, not leaving a single one unused.
The architect kindly explained that not every number of cubes can form a pyramid. With 10 cubes you can build a low
pyramid with base 3. With 5 cubes you can build a high pyramid of base 2. But no pyramid can be built using exactly
7 cubes.
The pharaoh was not amused, but after some thinking he came up with new restrictions.
1. All cubes must be used.
2. You may build more than one pyramid, but you must build as few pyramids as possible.
3. All pyramids must be different.
4. Each pyramid must have a height of at least 2.
5. Satisfying the above, the largest of the pyramids must be as large as possible (i.e., containing the most cubes).
6. Satisfying the above, the next-to-largest pyramid must be as large as possible.
7. And so on...
Drawing figures and pictures in the sand, it took the architect quite some time to come up with the best solution.
Write a program that determines how to meet the restrictions of the pharaoh, given the number of cubes.
Input
The input consists of several test cases, each one on a single line. A test case is an integer c, where 1 ≤ c ≤ 106 ,
giving the number of cubes available.
The last test case is followed by a line containing a single zero.
ICPC 2011 World Finals Problem J: Pyramids
Output
For each test case, display its case number followed by the pyramids to be built. The pyramids should be ordered
with the largest first. Pyramids are specified by the length of their base followed by an L for low pyramids or an
H for high pyramids. If two differenct pyramids have the same number of cubes, list the high pyramid first. Print
“impossible” if it is not possible to meet the requirements of the pharaoh.
Follow the format of the sample output.
Sample input Output for the Sample Input
29 Case 1: 3H 3L 2H
28 Case 2: impossible
0
ICPC 2011 World Finals Problem J: Pyramids
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 2011\\J. Pyramids}
\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;
}