Statistics

Problem Statement for "MaterialImplication"

Problem Statement

You are given the ints n and k. Your task is to construct a specific formula in propositional logic. The formula must use n logic variables, and there must be exactly k ways to make the formula true. A more precise version of this task statement follows.


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.)

Definition

Class:
MaterialImplication
Method:
construct
Parameters:
int, int
Returns:
String
Method signature:
String construct(int n, int k)
(be sure your method is public)

Constraints

  • n will be between 1 and 20, inclusive.
  • k will be between 0 and 2^n, inclusive.

Examples

  1. 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. 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.

  3. 2

    3

    Returns: "(A->B)"

  4. 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.

  5. 4

    13

    Returns: "(((A->B)->(C->D))->((A->C)->(D->B)))"

  6. 1

    0

    Returns: "Impossible"

  7. 1

    1

    Returns: "A"

  8. 1

    2

    Returns: "(A->A)"

  9. 2

    0

    Returns: "Impossible"

  10. 2

    1

    Returns: "Impossible"

  11. 2

    2

    Returns: "((B->B)->B)"

  12. 2

    3

    Returns: "(A->B)"

  13. 2

    4

    Returns: "(A->A)"

  14. 3

    0

    Returns: "Impossible"

  15. 3

    1

    Returns: "Impossible"

  16. 3

    2

    Returns: "Impossible"

  17. 3

    3

    Returns: "Impossible"

  18. 3

    4

    Returns: "((C->C)->C)"

  19. 3

    5

    Returns: "((((((C->C)->A)->B)->C)->C)->C)"

  20. 3

    6

    Returns: "((((C->C)->B)->C)->C)"

  21. 3

    7

    Returns: "((((((C->C)->A)->C)->B)->C)->C)"

  22. 3

    8

    Returns: "(A->A)"

  23. 4

    0

    Returns: "Impossible"

  24. 4

    1

    Returns: "Impossible"

  25. 4

    2

    Returns: "Impossible"

  26. 4

    3

    Returns: "Impossible"

  27. 4

    4

    Returns: "Impossible"

  28. 4

    5

    Returns: "Impossible"

  29. 4

    6

    Returns: "Impossible"

  30. 4

    7

    Returns: "Impossible"

  31. 4

    8

    Returns: "((D->D)->D)"

  32. 4

    9

    Returns: "((((((((D->D)->A)->B)->D)->C)->D)->D)->D)"

  33. 4

    10

    Returns: "((((((D->D)->B)->C)->D)->D)->D)"

  34. 4

    11

    Returns: "((((((((D->D)->A)->D)->B)->C)->D)->D)->D)"

  35. 4

    12

    Returns: "((((D->D)->C)->D)->D)"

  36. 4

    13

    Returns: "(((A->B)->(C->D))->((A->C)->(D->B)))"

  37. 4

    14

    Returns: "((((((D->D)->B)->D)->C)->D)->D)"

  38. 4

    15

    Returns: "((((((((D->D)->A)->D)->B)->D)->C)->D)->D)"

  39. 4

    16

    Returns: "(A->A)"

  40. 5

    0

    Returns: "Impossible"

  41. 5

    1

    Returns: "Impossible"

  42. 5

    2

    Returns: "Impossible"

  43. 5

    3

    Returns: "Impossible"

  44. 5

    4

    Returns: "Impossible"

  45. 5

    5

    Returns: "Impossible"

  46. 5

    6

    Returns: "Impossible"

  47. 5

    7

    Returns: "Impossible"

  48. 5

    8

    Returns: "Impossible"

  49. 5

    9

    Returns: "Impossible"

  50. 5

    10

    Returns: "Impossible"

  51. 5

    11

    Returns: "Impossible"

  52. 5

    12

    Returns: "Impossible"

  53. 5

    13

    Returns: "Impossible"

  54. 5

    14

    Returns: "Impossible"

  55. 5

    15

    Returns: "Impossible"

  56. 5

    16

    Returns: "((E->E)->E)"

  57. 5

    17

    Returns: "((((((((((E->E)->A)->B)->E)->C)->E)->D)->E)->E)->E)"

  58. 5

    18

    Returns: "((((((((E->E)->B)->C)->E)->D)->E)->E)->E)"

  59. 5

    19

    Returns: "((((((((((E->E)->A)->E)->B)->C)->E)->D)->E)->E)->E)"

  60. 5

    20

    Returns: "((((((E->E)->C)->D)->E)->E)->E)"

  61. 5

    21

    Returns: "((((((((((E->E)->A)->B)->E)->E)->C)->D)->E)->E)->E)"

  62. 5

    22

    Returns: "((((((((E->E)->B)->E)->C)->D)->E)->E)->E)"

  63. 5

    23

    Returns: "((((((((((E->E)->A)->E)->B)->E)->C)->D)->E)->E)->E)"

  64. 5

    24

    Returns: "((((E->E)->D)->E)->E)"

  65. 5

    25

    Returns: "((((((((((E->E)->A)->B)->E)->C)->E)->E)->D)->E)->E)"

  66. 5

    26

    Returns: "((((((((E->E)->B)->C)->E)->E)->D)->E)->E)"

  67. 5

    27

    Returns: "((((((((((E->E)->A)->E)->B)->C)->E)->E)->D)->E)->E)"

  68. 5

    28

    Returns: "((((((E->E)->C)->E)->D)->E)->E)"

  69. 5

    29

    Returns: "((((((((((E->E)->A)->B)->E)->E)->C)->E)->D)->E)->E)"

  70. 5

    30

    Returns: "((((((((E->E)->B)->E)->C)->E)->D)->E)->E)"

  71. 5

    31

    Returns: "((((((((((E->E)->A)->E)->B)->E)->C)->E)->D)->E)->E)"

  72. 5

    32

    Returns: "(A->A)"

  73. 9

    441

    Returns: "((((((((((((((((((I->I)->A)->B)->I)->C)->I)->I)->D)->I)->E)->I)->F)->G)->I)->I)->H)->I)->I)"

  74. 12

    3049

    Returns: "((((((((((((((((((((((((L->L)->A)->B)->L)->C)->L)->L)->D)->E)->L)->L)->F)->L)->G)->L)->H)->L)->I)->L)->J)->K)->L)->L)->L)"

  75. 11

    319

    Returns: "Impossible"

  76. 11

    1498

    Returns: "((((((((((((((((((((K->K)->B)->C)->K)->K)->D)->K)->E)->F)->K)->K)->G)->K)->H)->K)->I)->J)->K)->K)->K)"

  77. 20

    878353

    Returns: "((((((((((((((((((((((((((((((((((((((((T->T)->A)->B)->T)->C)->T)->D)->T)->T)->E)->F)->T)->G)->T)->H)->T)->T)->I)->T)->J)->T)->K)->L)->T)->M)->T)->T)->N)->T)->O)->P)->T)->T)->Q)->R)->T)->T)->S)->T)->T)"

  78. 8

    130

    Returns: "((((((((((((((H->H)->B)->C)->H)->D)->H)->E)->H)->F)->H)->G)->H)->H)->H)"

  79. 17

    44385

    Returns: "Impossible"

  80. 11

    2043

    Returns: "((((((((((((((((((((((K->K)->A)->K)->B)->C)->K)->K)->D)->K)->E)->K)->F)->K)->G)->K)->H)->K)->I)->K)->J)->K)->K)"

  81. 7

    12

    Returns: "Impossible"

  82. 9

    42

    Returns: "Impossible"

  83. 11

    1686

    Returns: "((((((((((((((((((((K->K)->B)->K)->C)->D)->K)->K)->E)->F)->K)->G)->K)->K)->H)->I)->K)->K)->J)->K)->K)"

  84. 7

    84

    Returns: "((((((((((G->G)->C)->D)->G)->G)->E)->F)->G)->G)->G)"

  85. 20

    629017

    Returns: "((((((((((((((((((((((((((((((((((((((((T->T)->A)->B)->T)->C)->T)->T)->D)->T)->E)->F)->T)->G)->T)->H)->T)->T)->I)->J)->T)->K)->T)->T)->L)->T)->M)->N)->T)->O)->T)->T)->P)->T)->Q)->R)->T)->S)->T)->T)->T)"

  86. 15

    10580

    Returns: "Impossible"

  87. 8

    137

    Returns: "((((((((((((((((H->H)->A)->B)->H)->C)->H)->H)->D)->E)->H)->F)->H)->G)->H)->H)->H)"

  88. 9

    161

    Returns: "Impossible"

  89. 15

    27901

    Returns: "((((((((((((((((((((((((((((((O->O)->A)->B)->O)->O)->C)->O)->D)->O)->E)->O)->F)->O)->G)->O)->H)->I)->O)->J)->O)->O)->K)->O)->L)->M)->O)->O)->N)->O)->O)"

  90. 10

    1011

    Returns: "((((((((((((((((((((J->J)->A)->J)->B)->C)->J)->D)->J)->J)->E)->J)->F)->J)->G)->J)->H)->J)->I)->J)->J)"

  91. 13

    748

    Returns: "Impossible"

  92. 12

    252

    Returns: "Impossible"

  93. 19

    23529

    Returns: "Impossible"

  94. 10

    762

    Returns: "((((((((((((((((((J->J)->B)->C)->J)->J)->D)->J)->E)->J)->F)->J)->G)->J)->H)->I)->J)->J)->J)"

  95. 12

    2670

    Returns: "((((((((((((((((((((((L->L)->B)->L)->C)->L)->D)->E)->L)->L)->F)->L)->G)->H)->L)->I)->L)->L)->J)->K)->L)->L)->L)"

  96. 8

    203

    Returns: "((((((((((((((((H->H)->A)->H)->B)->C)->H)->H)->D)->E)->H)->F)->H)->H)->G)->H)->H)"

  97. 11

    1807

    Returns: "((((((((((((((((((((((K->K)->A)->K)->B)->K)->C)->K)->D)->E)->K)->F)->K)->G)->K)->H)->K)->K)->I)->K)->J)->K)->K)"

  98. 12

    3610

    Returns: "((((((((((((((((((((((L->L)->B)->C)->L)->L)->D)->L)->E)->F)->L)->G)->L)->H)->L)->I)->L)->L)->J)->L)->K)->L)->L)"

  99. 10

    559

    Returns: "((((((((((((((((((((J->J)->A)->J)->B)->J)->C)->J)->D)->E)->J)->J)->F)->G)->J)->H)->J)->I)->J)->J)->J)"

  100. 13

    837

    Returns: "Impossible"

  101. 11

    756

    Returns: "Impossible"

  102. 16

    34605

    Returns: "((((((((((((((((((((((((((((((((P->P)->A)->B)->P)->P)->C)->P)->D)->E)->P)->P)->F)->G)->P)->H)->P)->P)->I)->P)->J)->P)->K)->L)->P)->M)->P)->N)->P)->O)->P)->P)->P)"

  103. 19

    44679

    Returns: "Impossible"

  104. 17

    119471

    Returns: "((((((((((((((((((((((((((((((((((Q->Q)->A)->Q)->B)->Q)->C)->Q)->D)->E)->Q)->Q)->F)->G)->Q)->Q)->H)->I)->Q)->Q)->J)->K)->Q)->L)->Q)->Q)->M)->N)->Q)->Q)->O)->Q)->P)->Q)->Q)"

  105. 14

    7544

    Returns: "Impossible"

  106. 9

    161

    Returns: "Impossible"

  107. 12

    1470

    Returns: "Impossible"

  108. 11

    2007

    Returns: "((((((((((((((((((((((K->K)->A)->K)->B)->K)->C)->D)->K)->K)->E)->F)->K)->K)->G)->K)->H)->K)->I)->K)->J)->K)->K)"

  109. 20

    384601

    Returns: "Impossible"

  110. 18

    26903

    Returns: "Impossible"

  111. 9

    124

    Returns: "Impossible"

  112. 20

    224550

    Returns: "Impossible"

  113. 16

    14802

    Returns: "Impossible"

  114. 7

    44

    Returns: "Impossible"

  115. 7

    72

    Returns: "((((((((G->G)->D)->E)->G)->F)->G)->G)->G)"

  116. 13

    7881

    Returns: "((((((((((((((((((((((((((M->M)->A)->B)->M)->C)->M)->M)->D)->E)->M)->F)->M)->M)->G)->M)->H)->I)->M)->M)->J)->M)->K)->M)->L)->M)->M)"

  117. 8

    16

    Returns: "Impossible"

  118. 19

    13627

    Returns: "Impossible"

  119. 12

    3204

    Returns: "((((((((((((((((((((L->L)->C)->D)->L)->E)->L)->F)->L)->G)->L)->L)->H)->I)->L)->J)->L)->L)->K)->L)->L)"

  120. 14

    10965

    Returns: "((((((((((((((((((((((((((((N->N)->A)->B)->N)->N)->C)->D)->N)->N)->E)->F)->N)->N)->G)->N)->H)->I)->N)->N)->J)->K)->N)->N)->L)->M)->N)->N)->N)"

  121. 13

    343

    Returns: "Impossible"

  122. 12

    1643

    Returns: "Impossible"

  123. 17

    33507

    Returns: "Impossible"

  124. 18

    13357

    Returns: "Impossible"

  125. 18

    255470

    Returns: "((((((((((((((((((((((((((((((((((R->R)->B)->R)->C)->R)->D)->E)->R)->R)->F)->R)->G)->R)->H)->R)->I)->J)->R)->R)->K)->L)->R)->M)->R)->R)->N)->R)->O)->R)->P)->R)->Q)->R)->R)"

  126. 19

    302344

    Returns: "((((((((((((((((((((((((((((((((S->S)->D)->E)->S)->F)->S)->G)->S)->H)->S)->S)->I)->J)->S)->S)->K)->S)->L)->S)->M)->N)->S)->O)->S)->S)->P)->Q)->S)->R)->S)->S)->S)"

  127. 20

    443994

    Returns: "Impossible"

  128. 20

    592287

    Returns: "((((((((((((((((((((((((((((((((((((((((T->T)->A)->T)->B)->T)->C)->T)->D)->T)->E)->F)->T)->G)->T)->T)->H)->T)->I)->J)->T)->K)->T)->T)->L)->M)->T)->N)->T)->O)->T)->P)->T)->T)->Q)->R)->T)->S)->T)->T)->T)"

  129. 18

    103874

    Returns: "Impossible"

  130. 13

    1011

    Returns: "Impossible"

  131. 10

    720

    Returns: "((((((((((((J->J)->E)->F)->J)->J)->G)->J)->H)->I)->J)->J)->J)"

  132. 16

    15439

    Returns: "Impossible"

  133. 9

    319

    Returns: "((((((((((((((((((I->I)->A)->I)->B)->I)->C)->I)->D)->I)->E)->I)->F)->G)->I)->H)->I)->I)->I)"

  134. 17

    102278

    Returns: "((((((((((((((((((((((((((((((((Q->Q)->B)->Q)->C)->D)->Q)->E)->Q)->F)->Q)->G)->Q)->Q)->H)->Q)->I)->Q)->J)->Q)->K)->Q)->L)->M)->Q)->N)->Q)->O)->Q)->Q)->P)->Q)->Q)"

  135. 18

    6682

    Returns: "Impossible"

  136. 16

    19861

    Returns: "Impossible"

  137. 15

    13325

    Returns: "Impossible"

  138. 11

    1753

    Returns: "((((((((((((((((((((((K->K)->A)->B)->K)->C)->K)->K)->D)->K)->E)->F)->K)->K)->G)->K)->H)->I)->K)->K)->J)->K)->K)"

  139. 8

    183

    Returns: "((((((((((((((((H->H)->A)->H)->B)->H)->C)->D)->H)->H)->E)->H)->F)->G)->H)->H)->H)"

  140. 8

    57

    Returns: "Impossible"

  141. 9

    249

    Returns: "Impossible"

  142. 8

    202

    Returns: "((((((((((((((H->H)->B)->C)->H)->H)->D)->E)->H)->F)->H)->H)->G)->H)->H)"

  143. 19

    246339

    Returns: "Impossible"

  144. 18

    258759

    Returns: "((((((((((((((((((((((((((((((((((((R->R)->A)->R)->B)->R)->C)->D)->R)->E)->R)->F)->R)->R)->G)->R)->H)->I)->R)->R)->J)->K)->R)->L)->R)->R)->M)->R)->N)->R)->O)->R)->P)->R)->Q)->R)->R)"

  145. 10

    50

    Returns: "Impossible"

  146. 18

    79539

    Returns: "Impossible"

  147. 7

    87

    Returns: "((((((((((((((G->G)->A)->G)->B)->G)->C)->D)->G)->G)->E)->F)->G)->G)->G)"

  148. 17

    30641

    Returns: "Impossible"

  149. 19

    415307

    Returns: "((((((((((((((((((((((((((((((((((((((S->S)->A)->S)->B)->C)->S)->S)->D)->E)->S)->F)->S)->S)->G)->H)->S)->I)->S)->S)->J)->S)->K)->L)->S)->S)->M)->N)->S)->S)->O)->P)->S)->Q)->S)->S)->R)->S)->S)"

  150. 17

    49742

    Returns: "Impossible"

  151. 20

    22316

    Returns: "Impossible"

  152. 18

    83401

    Returns: "Impossible"

  153. 7

    123

    Returns: "((((((((((((((G->G)->A)->G)->B)->C)->G)->G)->D)->G)->E)->G)->F)->G)->G)"

  154. 15

    23340

    Returns: "((((((((((((((((((((((((((O->O)->C)->O)->D)->E)->O)->O)->F)->G)->O)->H)->O)->O)->I)->O)->J)->K)->O)->O)->L)->O)->M)->N)->O)->O)->O)"

  155. 9

    208

    Returns: "Impossible"

  156. 15

    8162

    Returns: "Impossible"

  157. 15

    3907

    Returns: "Impossible"

  158. 13

    5913

    Returns: "((((((((((((((((((((((((((M->M)->A)->B)->M)->C)->M)->M)->D)->M)->E)->F)->M)->G)->M)->H)->M)->M)->I)->M)->J)->M)->K)->L)->M)->M)->M)"

  159. 7

    121

    Returns: "((((((((((((((G->G)->A)->B)->G)->C)->G)->G)->D)->G)->E)->G)->F)->G)->G)"

  160. 13

    4364

    Returns: "((((((((((((((((((((((M->M)->C)->M)->D)->E)->M)->F)->M)->G)->M)->H)->M)->M)->I)->J)->M)->K)->M)->L)->M)->M)->M)"

  161. 13

    2026

    Returns: "Impossible"

  162. 17

    21149

    Returns: "Impossible"

  163. 16

    6172

    Returns: "Impossible"

  164. 12

    624

    Returns: "Impossible"

  165. 10

    171

    Returns: "Impossible"

  166. 13

    3210

    Returns: "Impossible"

  167. 16

    60357

    Returns: "((((((((((((((((((((((((((((((((P->P)->A)->B)->P)->P)->C)->D)->P)->E)->P)->F)->P)->P)->G)->P)->H)->P)->I)->P)->J)->K)->P)->P)->L)->M)->P)->P)->N)->P)->O)->P)->P)"

  168. 20

    922747

    Returns: "((((((((((((((((((((((((((((((((((((((((T->T)->A)->T)->B)->C)->T)->T)->D)->T)->E)->T)->F)->T)->G)->H)->T)->I)->T)->J)->T)->T)->K)->L)->T)->T)->M)->N)->T)->O)->T)->P)->T)->Q)->T)->T)->R)->T)->S)->T)->T)"

  169. 9

    169

    Returns: "Impossible"

  170. 9

    46

    Returns: "Impossible"

  171. 12

    1686

    Returns: "Impossible"

  172. 14

    6226

    Returns: "Impossible"

  173. 20

    0

    Returns: "Impossible"

  174. 20

    1024

    Returns: "Impossible"

  175. 20

    1023

    Returns: "Impossible"

  176. 20

    1025

    Returns: "Impossible"

  177. 20

    524287

    Returns: "Impossible"

  178. 20

    524288

    Returns: "((T->T)->T)"

  179. 20

    524289

    Returns: "((((((((((((((((((((((((((((((((((((((((T->T)->A)->B)->T)->C)->T)->D)->T)->E)->T)->F)->T)->G)->T)->H)->T)->I)->T)->J)->T)->K)->T)->L)->T)->M)->T)->N)->T)->O)->T)->P)->T)->Q)->T)->R)->T)->S)->T)->T)->T)"

  180. 20

    1048576

    Returns: "(A->A)"

  181. 20

    1048575

    Returns: "((((((((((((((((((((((((((((((((((((((((T->T)->A)->T)->B)->T)->C)->T)->D)->T)->E)->T)->F)->T)->G)->T)->H)->T)->I)->T)->J)->T)->K)->T)->L)->T)->M)->T)->N)->T)->O)->T)->P)->T)->Q)->T)->R)->T)->S)->T)->T)"

  182. 20

    1048574

    Returns: "((((((((((((((((((((((((((((((((((((((T->T)->B)->T)->C)->T)->D)->T)->E)->T)->F)->T)->G)->T)->H)->T)->I)->T)->J)->T)->K)->T)->L)->T)->M)->T)->N)->T)->O)->T)->P)->T)->Q)->T)->R)->T)->S)->T)->T)"

  183. 20

    800000

    Returns: "((((((((((((((((((((((((T->T)->I)->J)->T)->T)->K)->L)->T)->T)->M)->T)->N)->O)->T)->P)->T)->Q)->T)->R)->T)->T)->S)->T)->T)"

  184. 20

    1000000

    Returns: "((((((((((((((((((((((((((((T->T)->G)->H)->T)->I)->T)->T)->J)->K)->T)->L)->T)->M)->T)->N)->T)->T)->O)->P)->T)->T)->Q)->T)->R)->T)->S)->T)->T)"

  185. 20

    531602

    Returns: "((((((((((((((((((((((((((((((((((((((T->T)->B)->C)->T)->D)->T)->T)->E)->F)->T)->G)->T)->T)->H)->I)->T)->J)->T)->T)->K)->T)->L)->T)->M)->N)->T)->O)->T)->P)->T)->Q)->T)->R)->T)->S)->T)->T)->T)"

  186. 20

    751309

    Returns: "((((((((((((((((((((((((((((((((((((((((T->T)->A)->B)->T)->T)->C)->T)->D)->E)->T)->F)->T)->T)->G)->T)->H)->I)->T)->T)->J)->T)->K)->L)->T)->T)->M)->T)->N)->T)->O)->P)->T)->T)->Q)->T)->R)->S)->T)->T)->T)"

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: