ICPC 2009 - B. My Bad
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/2009/B-my-bad. Edit
competitive_programming/icpc/2009/B-my-bad/solution.tex to update the written solution and
competitive_programming/icpc/2009/B-my-bad/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 B
My Bad
Input file: bad.in
A logic circuit maps its input through various gates to its output with no feedback loops in the circuit. The input
and output are an ordered set of logical values, represented here by ones and zeros. The circuits we consider are
comprised of and gates (which output 1 only when their two inputs are both 1), or gates (which output 1 when
one or both of their inputs are 1), exclusive or (xor) gates (which output 1 only when exactly one of the two
inputs is 1), and not gates (which output the complement of their single input). The figures below show two
circuits.
i1
or not o1
i2 g1 g2
Figure 1: Circuit with 2 gates
Figure 2: Circuit with 4 gates
Unfortunately, real gates sometimes fail. Although the failures may occur in many different ways, this problem
limits attention to gates that fail in one of three ways: 1) always inverting the correct output, 2) always yielding
0, and 3) always yielding 1. In the circuits for this problem, at most one gate will fail.
You must write a program that analyzes a circuit and a number of observations of its input and output to see if
the circuit is performing correctly or incorrectly. If at least one set of inputs produces the wrong output, your
program must also attempt to determine the unique failing gate and the way in which this gate is failing. This
may not always be possible.
Input
The input consists of multiple test cases, each representing a circuit with input and output descriptions. Each test
case has the following parts in order.
1. A line containing three positive integers giving the number of inputs (N ≤ 8), the number of gates (G ≤ 19),
and the number of outputs (U ≤ 19) in the circuit.
2. One line of input for each gate. The first line describes gate g1. If there are several gates, the next line
describes gate g2, and so on. Each of these lines contains the gate type (a = and, n = not, o = or, and
x = exclusive or), and identification of the input(s) to the gate. Gate input comes from the circuit inputs
(i1, i2, …) or the output of another gate (g1, g2, …).
3. A line containing the numbers of the gates connected to the U outputs u1, u2, …. For example, if there are
three outputs, and u1 comes from g5, u2 from g1, and u3 from g4, then the line would contain: 5 1 4
4. A line containing an integer which is the number of observations of the circuit’s behavior (B).
5. Finally B lines, each containing N values (ones and zeros) giving the observed input values and U values
giving the corresponding observed output values. No two observations have the same input values.
Consecutive entries on any line of the input are separated by a single space. The input is terminated with a line
containing three zeros.
Output
For each circuit in the input, print its case number (starting with 1), followed by a colon and a blank, and then
the circuit analysis, which will be one of the following (with # replaced by the appropriate gate number):
No faults detected
Gate # is failing; output inverted
Gate # is failing; output stuck at 0
Gate # is failing; output stuck at 1
Unable to totally classify the failure
The circuits pictured in Figure 1 and Figure 2 are used in the first and last sample test cases.
Sample Input Output for the Sample Input
2 2 1 Case 1: No faults detected
o i1 i2 Case 2: Unable to totally classify the failure
n g1 Case 3: Gate 1 is failing; output stuck at 1
2 Case 4: Gate 1 is failing; output inverted
2 Case 5: Gate 2 is failing; output stuck at 0
1 0 0
0 0 1
2 1 1
a i1 i2
1
1
1 0 1
2 1 1
a i1 i2
1
2
1 0 1
1 1 1
1 1 1
n i1
1
2
1 1
0 0
3 4 4
n g4
a i1 i2
o i2 i3
x i3 i1
2 3 4 1
4
0 1 0 0 1 0 1
0 1 1 0 1 1 0
1 1 1 0 1 0 1
0 0 0 0 0 0 1
0 0 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 2009\\B. My Bad}
\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;
}