Connection Status:
Competition Arena > TheDevice

TheDevice

SRM 569 · 2012-12-13 · by gojira_tc

SRM 569 · 2012-12-13 · by gojira_tc · Simple Search, Iteration
Class Name: TheDevice
Return Type: int
Method Name: minimumAdditional
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Manao works at a laboratory on a highly classified project. From time to time, he is given a special device and has to determine its exact structure. Every such device operates on special plates. There are M bits written on each of the plates from left to right. The device has two inputs and a screen. Each input requires a plate. When two plates are connected to the device, M bits of output appear on the screen. Each bit of output is either a binary OR, AND or XOR of the corresponding bits of the input plates. Manao's task is to determine what operation is carried out for each of the bits.

Manao has N plates. He is going to test the device on each possible pair of these plates and determine its structure by the outputs on the screen. It might be that the plates Manao has are not enough to uniquely identify every possible device. You are given String[] plates, where each element describes a plate Manao has. Return the minimum number of additional plates Manao needs to be able to determine the structure of any device.

Constraints

  • plates will contain between 1 and 50 elements, inclusive.
  • Each element of plates will be between 1 and 50 characters long, inclusive.
  • All elements of plates will be of equal length.
  • Each element of plates will contain characters from the set {'0', '1'} only.

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
{"010",
 "011",
 "101"}
Returns: 1

It is possible to find two different devices such that no pair of Manao's plates will distinguish between them. To fix this it is sufficient to add one more plate. An example of such a plate is "101". There are also other plates that would work in its place.

1)
{"0",
 "1",
 "0",
 "1"}
Returns: 0

With these plates, Manao can test the output for every possible pair of bits, which allows him to distinguish between AND, OR and XOR.

2)
{"01010101",
 "10101010"}
Returns: 1
3)
{"10010101011",
 "00010101001",
 "00100010111",
 "00101010101",
 "01010111101"}
Returns: 1
4)
{"1101001011010",
 "0010000010101",
 "1010101011110",
 "1101010100111",
 "1011111110111"}
Returns: 0

Submissions are judged against all 129 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TheDevice with a public method int minimumAdditional(vector<string> plates) · 129 test cases · 2 s / 256 MB per case

Submitting as anonymous