StringEquations
TCO12 Wildcard Round · 2012-03-27 · by lyrically
TCO12 Wildcard Round · 2012-03-27 · by lyrically · Graph Theory, String Manipulation
Problem Statement
Problem Statement
In this problem, we consider 26 variables A, B, C, ..., Z, each of which represents a (possibly empty) string consisting of lowercase letters.
You are given a String[] equations.
Each element of equations is formatted as "VAR1 = VAR2 + VAL", where VAR1 and VAR2 will each be an uppercase letter representing a variable, and VAL is a non-empty string consisting of lowercase letters.
This equation claims that variable VAR1 is equal to the concatenation of variable VAR2 and string VAL (in this order).
If there is no (A, B, C, ..., Z) satisfying all given equations, return -1. Otherwise, return the minimum possible sum of the lengths of A, B, C, ..., Z.
If there is no (A, B, C, ..., Z) satisfying all given equations, return -1. Otherwise, return the minimum possible sum of the lengths of A, B, C, ..., Z.
Constraints
- equations will contain between 1 and 50 elements, inclusive.
- Each element of equations will contain between 9 and 50 characters, inclusive.
- Each element of equations will be formatted as "VAR1 = VAR2 + VAL", where VAR1 and VAR2 will each be an uppercase letter, and VAL will be a non-empty string consisting of lowercase letters.
Examples
0)
{ "B = A + top", "C = B + coder", "C = A + topcoder" }
Returns: 11
If we assign B = top, C = topcoder and the empty string to each of the other variables, these three equations are satisfied and the sum of the lengths is minimized.
1)
{ "B = A + coder", "C = B + top", "C = A + topcoder" }
Returns: -1
The first two equations imply "C = A + codertop", which contradicts the third one.
2)
{ "A = B + p", "C = A + q", "D = F + r", "E = B + x", "G = A + y", "H = F + z" }
Returns: 8
3)
{ "X = X + a" }
Returns: -1
4)
{ "Y = X + a", "Y = X + b" }
Returns: -1
Submissions are judged against all 165 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class StringEquations with a public method int getMinimum(vector<string> equations) · 165 test cases · 2 s / 256 MB per case