RobustScheme
TCO 22 Final · 2022-11-17 · by misof
Problem Statement
You have a scheme of a circuit you would like to build. The circuit has N inputs, one output, and it consists of logic gates: binary ANDs and ORs.
You are at an electronic store that sells the logic gates you need. However, the owner just informed you that he accidentally mixed up K defective gates among the supply he's selling.
A defective gate does not perform its logical operation. Instead, it contains a short circuit: one of its input wires is directly connected to its output (and thus the value from that input is copied to the output of the defective gate).
You cannot distinguish between good and defective gates, and if a gate is defective, you cannot tell which of its two inputs it copies to its output.
A circuit is a sequence of gates and a collection of wires.
Each wire carries the value 0 or 1. The input wires have numbers from 0 to N-1. The values on these wires can be arbitrary.
If there are G gates in the circuit, their output wires have numbers N to N+G-1 in the order in which these gates are listed. The values on these wires are the values computed by the gates that outputs them.
The inputs of each gate must be wires that already exist (i.e., input wires + outputs of previous gates). Each wire can be the input to arbitrarily many gates. The same wire may even be used for both inputs to the gate.
The output of the last gate in the circuit is the output of the circuit.
When encoding a circuit, for each gate we specify three integers { t, i1, i2 }, where t is its type (0 = AND, 1 = OR), and i1 and i2 are the numbers of the two wires it takes as inputs.
For example, for N=3 the circuit {0, 0, 2, 1, 3, 1} consists of two gates: {0, 0, 2} is a gate that computes the AND of wires 0 and 2, and then {1, 3, 1} is a gate that computes the OR of wires 3 and 1.
--------
You are given the values K and N, and the
Redesign the given circuit. The new circuit you produce must guarantee to compute the same function, even if some of the purchased gates are defective.
More precisely, for each of the 2^N possible inputs it must be true that the output given by the original circuit matches the output given by your circuit in all possible circumstances. (That is, regardless of which subset of at most K gates is defective and regardless of which input each of the defective gates copies, the output of your new circuit must remain correct.)
Your new circuit must be small enough. Notably, if G is the number of gates in the input circuit then:
- If K <= 6, the number of gates in your circuit must not exceed 33*G.
- If 7 <= K <= 15, the number of gates in your circuit must not exceed 93*G.
Return a
Constraints
- K will be between 0 and 15, inclusive.
- N will be between 1 and 8, inclusive.
- circuit will be a valid description of a circuit.
- circuit will contain between 1 and 12 gates, inclusive.
0
3
{0, 0, 1, 0, 2, 3}
Returns: {0, 0, 1, 0, 2, 3 }
The given circuit looks as follows: +--------+ i wire0 ---| gate 0 | wire3 +--------+ n | AND |--------| gate 1 | wire4=output p wire1 ---| | | AND |-------- u +--------+ +----| | t | +--------+ s wire2 ----------------+ As there are no defective parts in the store, we can simply purchase two AND gates and build the circuit according to its original plan.
1
3
{0, 0, 1, 0, 0, 2, 0, 1, 2, 1, 3, 4, 1, 5, 6, 0, 0, 0}
Returns: {1, 0, 0 }
The last gate in this circuit is an AND gate. Wire 0 is used for both of its inputs. Hence, this circuit returns the value of input wire 0. We can simply return a circuit consisting of a single OR gate such that wire 0 is used as both of its inputs. Even if the gate is defective, it will still always produce the correct output.
1
3
{0, 0, 1, 0, 0, 2, 0, 1, 2, 1, 3, 4, 1, 5, 6}
Returns: {0, 0, 1, 0, 0, 1, 0, 3, 4, 0, 0, 2, 0, 0, 2, 0, 6, 7, 0, 1, 2, 0, 1, 2, 0, 9, 10, 1, 5, 8, 1, 5, 8, 1, 12, 13, 1, 11, 14, 1, 11, 14, 1, 15, 16 }
2
3
{0, 0, 1, 0, 0, 2, 0, 1, 2, 1, 3, 4, 1, 5, 6, 1, 0, 1}
Returns: {1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 3, 4, 1, 4, 5, 1, 5, 6, 1, 7, 8, 1, 8, 9, 1, 10, 11 }
The input circuit returns the OR of wires 0 and 1. The output circuit is a bunch of OR gates that happens to have the desired property.
6
6
{1, 4, 3, 1, 2, 4, 1, 6, 0, 0, 0, 1, 0, 4, 7, 1, 5, 9, 1, 3, 3, 0, 7, 3, 1, 8, 5, 0, 9, 5, 0, 7, 1}
Returns: {1, 4, 3, 1, 4, 3, 1, 6, 7, 1, 4, 3, 1, 4, 3, 1, 9, 10, 1, 8, 11, 1, 8, 11, 1, 12, 13, 1, 4, 3, 1, 4, 3, 1, 15, 16, 1, 4, 3, 1, 4, 3, 1, 18, 19, 1, 17, 20, 1, 17, 20, 1, 21, 22, 1, 14, 23, 1, 14, 23, 1, 24, 25, 1, 14, 23, 1, 14, 23, 1, 27, 28, 1, 26, 29, 1, 26, 29, 1, 30, 31, 1, 2, 4, 1, 2, 4, 1, 33, 34, 1, 2, 4, 1, 2, 4, 1, 36, 37, 1, 35, 38, 1, 35, 38, 1, 39, 40, 1, 2, 4, 1, 2, 4, 1, 42, 43, 1, 2, 4, 1, 2, 4, 1, 45, 46, 1, 44, 47, 1, 44, 47, 1, 48, 49, 1, 41, 50, 1, 41, 50, 1, 51, 52, 1, 41, 50, 1, 41, 50, 1, 54, 55, 1, 53, 56, 1, 53, 56, 1, 57, 58, 1, 32, 0, 1, 32, 0, 1, 60, 61, 1, 32, 0, 1, 32, 0, 1, 63, 64, 1, 62, 65, 1, 62, 65, 1, 66, 67, 1, 32, 0, 1, 32, 0, 1, 69, 70, 1, 32, 0, 1, 32, 0, 1, 72, 73, 1, 71, 74, 1, 71, 74, 1, 75, 76, 1, 68, 77, 1, 68, 77, 1, 78, 79, 1, 68, 77, 1, 68, 77, 1, 81, 82, 1, 80, 83, 1, 80, 83, 1, 84, 85, 0, 0, 1, 0, 0, 1, 0, 87, 88, 0, 0, 1, 0, 0, 1, 0, 90, 91, 0, 89, 92, 0, 89, 92, 0, 93, 94, 0, 0, 1, 0, 0, 1, 0, 96, 97, 0, 0, 1, 0, 0, 1, 0, 99, 100, 0, 98, 101, 0, 98, 101, 0, 102, 103, 0, 95, 104, 0, 95, 104, 0, 105, 106, 0, 95, 104, 0, 95, 104, 0, 108, 109, 0, 107, 110, 0, 107, 110, 0, 111, 112, 0, 4, 59, 0, 4, 59, 0, 114, 115, 0, 4, 59, 0, 4, 59, 0, 117, 118, 0, 116, 119, 0, 116, 119, 0, 120, 121, 0, 4, 59, 0, 4, 59, 0, 123, 124, 0, 4, 59, 0, 4, 59, 0, 126, 127, 0, 125, 128, 0, 125, 128, 0, 129, 130, 0, 122, 131, 0, 122, 131, 0, 132, 133, 0, 122, 131, 0, 122, 131, 0, 135, 136, 0, 134, 137, 0, 134, 137, 0, 138, 139, 1, 5, 113, 1, 5, 113, 1, 141, 142, 1, 5, 113, 1, 5, 113, 1, 144, 145, 1, 143, 146, 1, 143, 146, 1, 147, 148, 1, 5, 113, 1, 5, 113, 1, 150, 151, 1, 5, 113, 1, 5, 113, 1, 153, 154, 1, 152, 155, 1, 152, 155, 1, 156, 157, 1, 149, 158, 1, 149, 158, 1, 159, 160, 1, 149, 158, 1, 149, 158, 1, 162, 163, 1, 161, 164, 1, 161, 164, 1, 165, 166, 1, 3, 3, 1, 3, 3, 1, 168, 169, 1, 3, 3, 1, 3, 3, 1, 171, 172, 1, 170, 173, 1, 170, 173, 1, 174, 175, 1, 3, 3, 1, 3, 3, 1, 177, 178, 1, 3, 3, 1, 3, 3, 1, 180, 181, 1, 179, 182, 1, 179, 182, 1, 183, 184, 1, 176, 185, 1, 176, 185, 1, 186, 187, 1, 176, 185, 1, 176, 185, 1, 189, 190, 1, 188, 191, 1, 188, 191, 1, 192, 193, 0, 59, 3, 0, 59, 3, 0, 195, 196, 0, 59, 3, 0, 59, 3, 0, 198, 199, 0, 197, 200, 0, 197, 200, 0, 201, 202, 0, 59, 3, 0, 59, 3, 0, 204, 205, 0, 59, 3, 0, 59, 3, 0, 207, 208, 0, 206, 209, 0, 206, 209, 0, 210, 211, 0, 203, 212, 0, 203, 212, 0, 213, 214, 0, 203, 212, 0, 203, 212, 0, 216, 217, 0, 215, 218, 0, 215, 218, 0, 219, 220, 1, 86, 5, 1, 86, 5, 1, 222, 223, 1, 86, 5, 1, 86, 5, 1, 225, 226, 1, 224, 227, 1, 224, 227, 1, 228, 229, 1, 86, 5, 1, 86, 5, 1, 231, 232, 1, 86, 5, 1, 86, 5, 1, 234, 235, 1, 233, 236, 1, 233, 236, 1, 237, 238, 1, 230, 239, 1, 230, 239, 1, 240, 241, 1, 230, 239, 1, 230, 239, 1, 243, 244, 1, 242, 245, 1, 242, 245, 1, 246, 247, 0, 113, 5, 0, 113, 5, 0, 249, 250, 0, 113, 5, 0, 113, 5, 0, 252, 253, 0, 251, 254, 0, 251, 254, 0, 255, 256, 0, 113, 5, 0, 113, 5, 0, 258, 259, 0, 113, 5, 0, 113, 5, 0, 261, 262, 0, 260, 263, 0, 260, 263, 0, 264, 265, 0, 257, 266, 0, 257, 266, 0, 267, 268, 0, 257, 266, 0, 257, 266, 0, 270, 271, 0, 269, 272, 0, 269, 272, 0, 273, 274, 0, 59, 1, 0, 59, 1, 0, 276, 277, 0, 59, 1, 0, 59, 1, 0, 279, 280, 0, 278, 281, 0, 278, 281, 0, 282, 283, 0, 59, 1, 0, 59, 1, 0, 285, 286, 0, 59, 1, 0, 59, 1, 0, 288, 289, 0, 287, 290, 0, 287, 290, 0, 291, 292, 0, 284, 293, 0, 284, 293, 0, 294, 295, 0, 284, 293, 0, 284, 293, 0, 297, 298, 0, 296, 299, 0, 296, 299, 0, 300, 301 }
Submissions are judged against all 100 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RobustScheme with a public method vector<int> design(int K, int N, vector<int> circuit) · 100 test cases · 2 s / 256 MB per case