ICPC 2013 - E. Harvard
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/2013/E-harvard. Edit
competitive_programming/icpc/2013/E-harvard/solution.tex to update the written solution and
competitive_programming/icpc/2013/E-harvard/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.
ICPC 2013
2013 World Finals
St. Petersburg
HOSTED BY ITMO
Problem E
Harvard
Time Limit: 10 seconds
The term “Harvard architecture” applies to a
computer that has physically separate memories
for instructions and data. The term originated
with the Harvard Mark I computer, delivered by
IBM in 1944, which used paper tape for instruc-
tions and relays for data.
Some modern microcontrollers use the Harvard
architecture – but not paper tape and relays!
Data memory is organized in banks, each con-
taining the same number of data items. Each
data-referencing instruction has a byte offset f Picture from Wikimedia Commons
to a bank, and a bit a that is used to select the
bank to be referenced. If a is 0, then bank 0 is referenced. If a is 1, then the value in a bank select
register (BSR) identifies the bank to be used. Assume each instruction takes the same time to execute,
and there is an instruction that can set the BSR’s value.
For example, suppose there are 4 banks of 8 bytes each. To access location 5, either use a single
instruction with a = 0 and f = 5, or set the BSR to 0 in one instruction and then use an instruction with
a = 1 and f = 5. The first approach is faster since it does not require setting the BSR.
Now suppose (with the same memory) the location to access is 20. Only one approach will work here:
execute an instruction that sets the BSR to 2 (unless the BSR already has the value 2) and then use an
instruction with a = 1 and f = 4.
A program is a sequence of operations. Each operation is either
• a variable reference, written as Vi, where i is a positive integer, or
• a repetition, written as Rn <program> E, where n is a positive integer and <program> is an
arbitrary program. This operation is equivalent to n sequential occurrences of <program>.
Your problem is to determine the minimum running time of programs. In particular, given the number
and size of the memory banks and a program to be executed, find the minimum number of instructions
(which reference memory location and possibly set the BSR) that must be executed to run the program.
To do this you must identify a mapping of variables to memory banks that yields the smallest execution
time, and report that execution time – that is, the number of memory references and BSR register settings
required. The BSR’s value is initially undefined, and changes only when an instruction explicitly sets its
value.
ICPC 2013
2013 World Finals
St. Petersburg
HOSTED BY ITMO
Input
The input consists of a single test case. A test case consists of two lines. The first line contains two
integers b and s, where 1 ≤ b ≤ 13 is the number of memory banks and 1 ≤ s ≤ 13 is the number of
variables that can be stored in each memory bank. The second line contains a non-empty program with
at most 1 000 space-separated elements (each Rn, Vi, and E counts as one element).
You may assume the following:
• In a repetition Rn, the number of repetitions satisfies 1 ≤ n ≤ 106 .
• In a loop operation Rn <program> E, the loop body <program> is not empty.
• In a variable reference Vi, the variable index satisfies 1 ≤ i ≤ min(b · s, 13).
• The total number of variable references performed by an execution of the program is at most 1012 .
Output
Display the minimum number of instructions that must be executed to complete the program.
Sample Input 1 Sample Output 1
1 2 5
V1 V2 V1 V1 V2
Sample Input 2 Sample Output 2
2 1 6
V1 V2 V1 V1 V2
Sample Input 3 Sample Output 3
1 2 30
R10 V1 V2 V1 E
Sample Input 4 Sample Output 4
4 1 17
V1 R2 V2 V4 R2 V1 E V3 E
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 2013\\E. Harvard Time Limit: 10 seconds The term “Harvard architecture” applies to a}
\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;
}