ICPC 2011 - B. Affine Mess
State the problem in your own words. Focus on the mathematical or algorithmic core rather than repeating the full statement.
ICPC2011TeXC++statement textstatement pdf
Source of truth
Source-first archive entry
This page is built from the copied files in competitive_programming/icpc/2011/B-affine-mess. Edit
competitive_programming/icpc/2011/B-affine-mess/solution.tex to update the written solution and
competitive_programming/icpc/2011/B-affine-mess/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
Problem Statement
Copied statement text kept beside the solution archive for direct reference.
Problem B
Affine Mess
Problem ID: affine
Tess L. Ation ran into a little problem last week when she demonstrated the beta version of her new drawing software.
On the screen she had an elegant demonstration design that illustrated every feature of her program; it had taken her
hours to produce it. She was just putting the finishing touches on it as a group of potential investors entered the room
to see the demonstration.
The presentation went well. Near the end, Tess clicked on a control panel button and told her audience, “This is
the ‘snap to grid’ control. It forces control points, such as vertices, to jump to the nearest grid point. Here, let me
show you,” and she placed three bright red dots on the screen. Each one appeared at the grid point nearest to where
she clicked. (“Luckily all control points in my demo design were already at integer coordinates. But I will have to
remember to delete these three red dots before I save my diagram,” she thought to herself.) “Now I’ll step into the next
room and get out of your way so you can discuss the system among yourselves and get a closer look at the screen, but
please don’t touch anything, since I haven’t saved that file yet.”
A few minutes later, the group joined Tess. One of the visitors stepped up to Tess and said, “I hope you don’t mind,
but I wanted to try it myself. Don’t worry, I just played with the x-scale and y-scale controls a little bit.” The next
person said, “Sorry if this is a problem, but I really wanted to get a feel for the speed of display, so I just played around
with the translation tool.” And a third person said, “I couldn’t resist just one tiny test: I rotated the image just so I
could see all of the vertices snap to the nearest grid points after the rotation.”
The person who played with the rotation tool remembered going first, but the other two could not recall their order. The
three remembered only a few details of the changes. The x- and y-scaling factors had been (possibly negative) non-
zero integers; the center of scaling was the origin (0, 0). The x- and y-translation amounts had been integers. Rotation
had been specified by a point with integer coordinates (x, y) on the perimeter of a square of width 20 centered at the
origin (hence, −10 ≤ x, y ≤ 10 and the absolute value of x or y or both was 10). The tool rotated the drawing around
the origin such that the positive x-axis would pass through (x, y) afterwards. Snapping took place after this rotation
(coordinates with a fractional part of 0.5 were rounded away from zero).
After they left, Tess looked at her design – it was completely changed! She had not yet implemented the “undo” feature,
and she had not saved the diagram prior to giving the demonstration. However, the three identical red dots were still
there (transformed to other integer grid locations, of course), and Tess could remember the integer coordinates where
she had originally placed them. Obviously, someone else might have altered the drawing without saying anything to
her, but she could write a program to see if it was possible to reconstruct the sequence of alterations. Can you too?
Input
The input contains several test cases. Each test case consists of six pairs of integers xi and yi (−500 ≤ xi , yi ≤ 500
for 1 ≤ i ≤ 6), three pairs per input line. The first three pairs represent the distinct initial locations of the three red
dots. The last three pairs represent the distinct final locations of the three dots. The indexing of the pairs in each group
of three is not significant: for example, (x1 , y1 ) could have been mapped to any of (x4 , y4 ), (x5 , y5 ) or (x6 , y6 ).
The last test case is followed by a line with six zeros.
ICPC 2011 World Finals Problem B: Affine Mess
Output
For each test case, display its case number followed by one of the following three messages:
• “equivalent solutions” to indicate that there are one or more valid transformations, and all of them
have the same effect on the whole drawing (no matter what the whole drawing looks like).
• “inconsistent solutions” to indicate that there are several valid transformations, but in general not all
of them map the entire drawing in the same way (some drawing is mapped differently by two valid transforma-
tions).
• “no solution” to indicate that neither of the first two cases occurs.
A valid transformation is a combination of rotation, translation and scaling (or rotation, scaling and translation) which
satisfies the restrictions described above and maps the initial set of red dots to the final set (occupying all three final
locations).
Follow the format of the sample output.
Sample input Output for the Sample Input
3 0 4 0 1 4 Case 1: equivalent solutions
-2 -4 -1 3 3 -4 Case 2: inconsistent solutions
0 1 1 1 2 1 Case 3: no solution
1 2 2 2 3 2 Case 4: inconsistent solutions
1 0 2 0 3 0 Case 5: equivalent solutions
3 3 1 1 2 2
1 0 2 0 3 0
3 2 1 1 2 2
2 3 0 6 1 2
2 3 0 6 1 2
0 0 0 0 0 0
ICPC 2011 World Finals Problem B: Affine Mess
Editorial
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.
Source code
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
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\\B. Affine Mess}
\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;
}