CandidateKeys

SRM 386 · 2008-01-05 · by eleusive

SRM 386 · 2008-01-05 · by eleusive · Brute Force, Simple Search, Iteration

Show categories

Class Name: CandidateKeys

Return Type: int[]

Method Name: getKeys

Arg Types: (vector<string>)

Problem Statement

A database table consists of a set of columns called attributes, and a set of rows called entries. A superkey is a set of attributes such that each entry's values for those attributes forms a unique ordered set. That is, for any superkey, each pair of entries differs in at least one of the attributes contained within the superkey. A candidate superkey is a superkey such that no proper subset of its attributes forms a superkey.

Return a int[] with exactly two elements. The first element should be the number of attributes in the smallest candidate superkey of the table, and the second element should be the number of attributes in the largest candidate superkey of the table. If there is no valid candidate superkey, return an empty int[] instead.

The input is described by a String[] table. Each String in table represents one entry, while characters contained in the String are attribute values for that entry.

Notes

A proper subset of a superkey is a set of attributes that is formed by removing one or more attributes from the superkey.

Constraints

table will contain between 2 and 50 elements, inclusive.
Each element of table will contain between 1 and 10 characters, inclusive.
Each element of table will contain the same number of characters.
Each character in table will be an uppercase letter ('A'-'Z').

Examples

{
"ABC",
"ABC",
"ABC"
}
Returns: { }

Since all entries are the same, there is no set of attributes that can differentiate between them. Therefore, this table has no candidate superkeys.

{
"ABC",
"ABD",
"ABE"
}
Returns: {1, 1 }

There are four superkeys here: {column 0, column 1, column 2} {column 0, column 2} {column 1, column 2} {column 2} Note that the fourth superkey is a subset of all the other superkeys, so it is the only candidate superkey.

{
"ABC",
"ACD",
"BBE"
}
Returns: {1, 2 }

{"BDC", "AFC", "BFG", "GAD", "DBA", "BCB", "ACC"}
Returns: {2, 2 }

{"AABAA", "ABABA", "ABBAA", "BBBAA", "BBBAB", "ABBBB", "BBBAA", "AAABB"}
Returns: { }

{
"AAC",
"ABD",
"BAC",
"BBD"
}
Returns: {2, 2 }

bad greedy: min

10)

{
"ACB",
"ACA",
"BDB",
"BDA"
}
Returns: {2, 2 }

bad greedy: min

11)

{
"ACEB",
"ACEA",
"BDFB",
"BDFA"
}
Returns: {2, 2 }

bad greedy: min

12)

{
"ABA",
"BAA",
"CAB",
"ACA",
"DBC",
"CAC"
}
Returns: {2, 2 }

bad greedy: min

13)

{
"AA",
"AB",
"AC",
"BD"
}
Returns: {1, 1 }

bad greedy: max

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

Coding Area

Language: C++17 · define a public class CandidateKeys with a public method vector<int> getKeys(vector<string> table) · 151 test cases · 2 s / 256 MB per case