MaterialImplication
2016 TCO Algo 3B · 2016-03-24 · by cgy4ever
Problem Statement
The n variables we will use will be denoted by the first n uppercase English letters. For example, if n=3, our three variables are "A", "B", and "C".
The only operator allowed in this task is the implication, denoted "->". The implication "x->y" is True when both "x" and "y" are True. The implication "x->y" is also True whenever "x" is False, regardless of whether "y" is True or not. In other words, the implication "x->y" is only False if "x" is True and "y" is False.
The set of valid expressions is defined as follows:
- Each variable is a valid expression.
- If "P" and "Q" are valid expressions, "(P->Q)" is also a valid expression.
- An expression that cannot be constructed by repeatedly using the above rules is not valid.
For example, "A", "(A->A)", "(((P->Q)->P)->P)", and "((A->B)->(B->A))" are valid expressions (if the value of n is large enough). On the other hand, "(A)", "", and "A->B" are not valid expressions. Note that some variables may be unused. For example, "(A->C)" is a valid expression for n=4.
For a valid expression with n variables there are 2^n assignments of truth values to the variables. (Each of the n variables can be True or False.) Your task is to find a valid expression such that exactly k of these assignments make the expression True.
If there is no such expression, return "Impossible".
If there are multiple such expressions, you may return any of them. However, the length of your return value must not exceed 1000 characters. (It can be shown that whenever the answer is not "Impossible", there are suitable expressions that do not exceed 1000 characters.)
Constraints
- n will be between 1 and 20, inclusive.
- k will be between 0 and 2^n, inclusive.
1 1 Returns: "A"
When A = True, the expression is True. When A = False, the expression is False. So exactly 1 of them will be True.
2 4 Returns: "(A->A)"
The expression "(A->A)" is a tautology. This means that in all 2^2=4 assignments the expression will be True. Note that even though "B" does not appear in this expression, we still consider all 2^2 ways of assigning truth values to variables. There are other valid expressions. For example, "(((A->B)->A)->A)" is also a tautology called Peirce's law.
2 3 Returns: "(A->B)"
3 0 Returns: "Impossible"
There is no such expression. We can easily show that any valid expression is True if all three variables are True.
4 13 Returns: "(((A->B)->(C->D))->((A->C)->(D->B)))"
Submissions are judged against all 186 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MaterialImplication with a public method string construct(int n, int k) · 186 test cases · 2 s / 256 MB per case