ConstructLCS | Topcoder Archive

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:: ConstructLCS
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.

Examples

```
3
```
```
4
```
```
2
```
```
Returns: "101 1010101 1111"
```
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".
```
7
```
```
4
```
```
4
```
```
Returns: "10101010 1010101 1011"
```
There are other solutions like: A = "1110000", B = "1110000", C = "0000".

Returns: "110101001011 010101101 10101010"

Returns: "110101010 10101010 1111010"

Returns: "000100101101111011000 11110111010011101010 100100001010101001010101000011111"

Returns: "11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111"

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.