Statistics

Problem Statement for "ConstructLCSEasy"

Problem Statement

A string S is a subsequence of a string T if we can obtain S from T by erasing some (possibly all or none) of its characters. For example, "000" is a subsequence of "01010".

The longest common subsequence (LCS) of two strings A and B is a string C that is a subsequence of each of them and has the largest length among all strings with this property. Let f(A,B) be the length of the LCS of strings A and B. For example, we have f("101", "111000") = 2, f("101", "110011") = 3, and f("00", "1111") = 0.

You are given three small positive integers ab, bc, and ca. Please find three strings A, B, C such that:
  • Each of the strings contains only the characters '0' and '1'.
  • The length of each string is between 1 and 1,000, inclusive.
  • f(A, B) = ab
  • f(B, C) = bc
  • f(C, A) = ca
Return a String formed as follows: A + " " + B + " " + C. (I.e., the returned string should contain the three strings A, B, C, separated by single spaces.)

You may assume that a solution always exist. If there are multiple solutions you may return any of them.

Definition

Class:
ConstructLCSEasy
Method:
construct
Parameters:
int, int, int
Returns:
String
Method signature:
String construct(int ab, int bc, int ca)
(be sure your method is public)

Constraints

  • ab will be between 1 and 50, inclusive.
  • bc will be between 1 and 50, inclusive.
  • ca will be between 1 and 50, inclusive.
  • ab <= bc <= ca.

Examples

  1. 2

    3

    4

    Returns: "1111 101 1010101"

    The returned string corresponds to the following solution: A = "1111" B = "101" C = "1010101" We can easily verify that the only LCS of A and B is "11", the only LCS of B and C is "101", and the only LCS of C and A is "1111".

  2. 4

    4

    7

    Returns: "10101010 1011 1010101"

    Another solution is: a = "0000111", b = "0000", c = "0000111".

  3. 6

    7

    8

    Returns: "10101010 1111010 110101010"

  4. 7

    8

    8

    Returns: "10101010 010101101 110101001011"

  5. 15

    17

    19

    Returns: "000100101101111011000 11110111010011101010 100100001010101001010101000011111"

  6. 50

    50

    50

    Returns: "11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111"

  7. 9

    23

    32

    Returns: "00000000000000000000000000000000 00000000011111111111111 0000000000000000000000000000000011111111111111"

  8. 16

    25

    32

    Returns: "00000000000000000000000000000000 0000000000000000111111111 00000000000000000000000000000000111111111"

  9. 6

    14

    37

    Returns: "0000000000000000000000000000000000000 00000011111111 000000000000000000000000000000000000011111111"

  10. 22

    32

    37

    Returns: "0000000000000000000000000000000000000 00000000000000000000001111111111 00000000000000000000000000000000000001111111111"

  11. 5

    8

    35

    Returns: "00000000000000000000000000000000000 00000111 00000000000000000000000000000000000111"

  12. 13

    35

    36

    Returns: "000000000000000000000000000000000000 00000000000001111111111111111111111 0000000000000000000000000000000000001111111111111111111111"

  13. 9

    17

    28

    Returns: "0000000000000000000000000000 00000000011111111 000000000000000000000000000011111111"

  14. 14

    35

    45

    Returns: "000000000000000000000000000000000000000000000 00000000000000111111111111111111111 000000000000000000000000000000000000000000000111111111111111111111"

  15. 2

    22

    30

    Returns: "000000000000000000000000000000 0011111111111111111111 00000000000000000000000000000011111111111111111111"

  16. 10

    21

    39

    Returns: "000000000000000000000000000000000000000 000000000011111111111 00000000000000000000000000000000000000011111111111"

  17. 20

    21

    45

    Returns: "000000000000000000000000000000000000000000000 000000000000000000001 0000000000000000000000000000000000000000000001"

  18. 28

    34

    47

    Returns: "00000000000000000000000000000000000000000000000 0000000000000000000000000000111111 00000000000000000000000000000000000000000000000111111"

  19. 4

    24

    39

    Returns: "000000000000000000000000000000000000000 000011111111111111111111 00000000000000000000000000000000000000011111111111111111111"

  20. 2

    14

    28

    Returns: "0000000000000000000000000000 00111111111111 0000000000000000000000000000111111111111"

  21. 10

    13

    14

    Returns: "00000000000000 0000000000111 00000000000000111"

  22. 2

    28

    28

    Returns: "0000000000000000000000000000 0011111111111111111111111111 000000000000000000000000000011111111111111111111111111"

  23. 10

    39

    39

    Returns: "000000000000000000000000000000000000000 000000000011111111111111111111111111111 00000000000000000000000000000000000000011111111111111111111111111111"

  24. 28

    35

    45

    Returns: "000000000000000000000000000000000000000000000 00000000000000000000000000001111111 0000000000000000000000000000000000000000000001111111"

  25. 8

    38

    49

    Returns: "0000000000000000000000000000000000000000000000000 00000000111111111111111111111111111111 0000000000000000000000000000000000000000000000000111111111111111111111111111111"

  26. 2

    11

    32

    Returns: "00000000000000000000000000000000 00111111111 00000000000000000000000000000000111111111"

  27. 12

    30

    32

    Returns: "00000000000000000000000000000000 000000000000111111111111111111 00000000000000000000000000000000111111111111111111"

  28. 1

    11

    28

    Returns: "0000000000000000000000000000 01111111111 00000000000000000000000000001111111111"

  29. 11

    16

    37

    Returns: "0000000000000000000000000000000000000 0000000000011111 000000000000000000000000000000000000011111"

  30. 13

    22

    23

    Returns: "00000000000000000000000 0000000000000111111111 00000000000000000000000111111111"

  31. 27

    28

    35

    Returns: "00000000000000000000000000000000000 0000000000000000000000000001 000000000000000000000000000000000001"

  32. 34

    39

    49

    Returns: "0000000000000000000000000000000000000000000000000 000000000000000000000000000000000011111 000000000000000000000000000000000000000000000000011111"

  33. 26

    31

    40

    Returns: "0000000000000000000000000000000000000000 0000000000000000000000000011111 000000000000000000000000000000000000000011111"

  34. 8

    9

    18

    Returns: "000000000000000000 000000001 0000000000000000001"

  35. 38

    46

    49

    Returns: "0000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000011111111 000000000000000000000000000000000000000000000000011111111"

  36. 2

    5

    6

    Returns: "000000 00111 000000111"

  37. 18

    31

    41

    Returns: "00000000000000000000000000000000000000000 0000000000000000001111111111111 000000000000000000000000000000000000000001111111111111"

  38. 7

    25

    32

    Returns: "00000000000000000000000000000000 0000000111111111111111111 00000000000000000000000000000000111111111111111111"

  39. 3

    47

    50

    Returns: "00000000000000000000000000000000000000000000000000 00011111111111111111111111111111111111111111111 0000000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111"

  40. 25

    41

    49

    Returns: "0000000000000000000000000000000000000000000000000 00000000000000000000000001111111111111111 00000000000000000000000000000000000000000000000001111111111111111"

  41. 34

    36

    49

    Returns: "0000000000000000000000000000000000000000000000000 000000000000000000000000000000000011 000000000000000000000000000000000000000000000000011"

  42. 10

    33

    47

    Returns: "00000000000000000000000000000000000000000000000 000000000011111111111111111111111 0000000000000000000000000000000000000000000000011111111111111111111111"

  43. 24

    26

    34

    Returns: "0000000000000000000000000000000000 00000000000000000000000011 000000000000000000000000000000000011"

  44. 11

    21

    40

    Returns: "0000000000000000000000000000000000000000 000000000001111111111 00000000000000000000000000000000000000001111111111"

  45. 14

    22

    24

    Returns: "000000000000000000000000 0000000000000011111111 00000000000000000000000011111111"

  46. 8

    28

    47

    Returns: "00000000000000000000000000000000000000000000000 0000000011111111111111111111 0000000000000000000000000000000000000000000000011111111111111111111"

  47. 2

    7

    13

    Returns: "0000000000000 0011111 000000000000011111"

  48. 23

    35

    45

    Returns: "000000000000000000000000000000000000000000000 00000000000000000000000111111111111 000000000000000000000000000000000000000000000111111111111"

  49. 1

    40

    42

    Returns: "000000000000000000000000000000000000000000 0111111111111111111111111111111111111111 000000000000000000000000000000000000000000111111111111111111111111111111111111111"

  50. 5

    22

    44

    Returns: "00000000000000000000000000000000000000000000 0000011111111111111111 0000000000000000000000000000000000000000000011111111111111111"

  51. 11

    12

    37

    Returns: "0000000000000000000000000000000000000 000000000001 00000000000000000000000000000000000001"

  52. 15

    16

    18

    Returns: "000000000000000000 0000000000000001 0000000000000000001"

  53. 14

    26

    50

    Returns: "00000000000000000000000000000000000000000000000000 00000000000000111111111111 00000000000000000000000000000000000000000000000000111111111111"

  54. 34

    35

    43

    Returns: "0000000000000000000000000000000000000000000 00000000000000000000000000000000001 00000000000000000000000000000000000000000001"

  55. 35

    38

    46

    Returns: "0000000000000000000000000000000000000000000000 00000000000000000000000000000000000111 0000000000000000000000000000000000000000000000111"

  56. 6

    11

    19

    Returns: "0000000000000000000 00000011111 000000000000000000011111"

  57. 8

    22

    27

    Returns: "000000000000000000000000000 0000000011111111111111 00000000000000000000000000011111111111111"

  58. 8

    42

    48

    Returns: "000000000000000000000000000000000000000000000000 000000001111111111111111111111111111111111 0000000000000000000000000000000000000000000000001111111111111111111111111111111111"

  59. 34

    36

    41

    Returns: "00000000000000000000000000000000000000000 000000000000000000000000000000000011 0000000000000000000000000000000000000000011"

  60. 17

    39

    40

    Returns: "0000000000000000000000000000000000000000 000000000000000001111111111111111111111 00000000000000000000000000000000000000001111111111111111111111"

  61. 9

    14

    37

    Returns: "0000000000000000000000000000000000000 00000000011111 000000000000000000000000000000000000011111"

  62. 1

    34

    50

    Returns: "00000000000000000000000000000000000000000000000000 0111111111111111111111111111111111 00000000000000000000000000000000000000000000000000111111111111111111111111111111111"

  63. 26

    26

    49

    Returns: "0000000000000000000000000000000000000000000000000 00000000000000000000000000 0000000000000000000000000000000000000000000000000"

  64. 17

    26

    36

    Returns: "000000000000000000000000000000000000 00000000000000000111111111 000000000000000000000000000000000000111111111"

  65. 16

    25

    38

    Returns: "00000000000000000000000000000000000000 0000000000000000111111111 00000000000000000000000000000000000000111111111"

  66. 3

    19

    40

    Returns: "0000000000000000000000000000000000000000 0001111111111111111 00000000000000000000000000000000000000001111111111111111"

  67. 5

    23

    27

    Returns: "000000000000000000000000000 00000111111111111111111 000000000000000000000000000111111111111111111"

  68. 7

    21

    50

    Returns: "00000000000000000000000000000000000000000000000000 000000011111111111111 0000000000000000000000000000000000000000000000000011111111111111"

  69. 1

    21

    26

    Returns: "00000000000000000000000000 011111111111111111111 0000000000000000000000000011111111111111111111"

  70. 2

    43

    45

    Returns: "000000000000000000000000000000000000000000000 0011111111111111111111111111111111111111111 00000000000000000000000000000000000000000000011111111111111111111111111111111111111111"

  71. 11

    22

    41

    Returns: "00000000000000000000000000000000000000000 0000000000011111111111 0000000000000000000000000000000000000000011111111111"

  72. 15

    47

    47

    Returns: "00000000000000000000000000000000000000000000000 00000000000000011111111111111111111111111111111 0000000000000000000000000000000000000000000000011111111111111111111111111111111"

  73. 33

    36

    43

    Returns: "0000000000000000000000000000000000000000000 000000000000000000000000000000000111 0000000000000000000000000000000000000000000111"

  74. 5

    14

    38

    Returns: "00000000000000000000000000000000000000 00000111111111 00000000000000000000000000000000000000111111111"

  75. 33

    41

    41

    Returns: "00000000000000000000000000000000000000000 00000000000000000000000000000000011111111 0000000000000000000000000000000000000000011111111"

  76. 16

    24

    41

    Returns: "00000000000000000000000000000000000000000 000000000000000011111111 0000000000000000000000000000000000000000011111111"

  77. 2

    30

    42

    Returns: "000000000000000000000000000000000000000000 001111111111111111111111111111 0000000000000000000000000000000000000000001111111111111111111111111111"

  78. 9

    33

    41

    Returns: "00000000000000000000000000000000000000000 000000000111111111111111111111111 00000000000000000000000000000000000000000111111111111111111111111"

  79. 8

    36

    43

    Returns: "0000000000000000000000000000000000000000000 000000001111111111111111111111111111 00000000000000000000000000000000000000000001111111111111111111111111111"

  80. 19

    44

    44

    Returns: "00000000000000000000000000000000000000000000 00000000000000000001111111111111111111111111 000000000000000000000000000000000000000000001111111111111111111111111"

  81. 13

    23

    47

    Returns: "00000000000000000000000000000000000000000000000 00000000000001111111111 000000000000000000000000000000000000000000000001111111111"

  82. 4

    7

    28

    Returns: "0000000000000000000000000000 0000111 0000000000000000000000000000111"

  83. 6

    24

    28

    Returns: "0000000000000000000000000000 000000111111111111111111 0000000000000000000000000000111111111111111111"

  84. 12

    21

    29

    Returns: "00000000000000000000000000000 000000000000111111111 00000000000000000000000000000111111111"

  85. 9

    13

    32

    Returns: "00000000000000000000000000000000 0000000001111 000000000000000000000000000000001111"

  86. 1

    7

    15

    Returns: "000000000000000 0111111 000000000000000111111"

  87. 1

    1

    1

    Returns: "0 0 0"

  88. 50

    50

    50

    Returns: "11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111"

  89. 1

    50

    50

    Returns: "00000000000000000000000000000000000000000000000000 01111111111111111111111111111111111111111111111111 000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111"

  90. 1

    1

    50

    Returns: "00000000000000000000000000000000000000000000000000 0 00000000000000000000000000000000000000000000000000"

  91. 2

    10

    40

    Returns: "0000000000000000000000000000000000000000 0011111111 000000000000000000000000000000000000000011111111"

  92. 1

    2

    3

    Returns: "000 01 0001"

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: