ConstructLCSEasy
SRM 716 · 2017-05-20 · by cgy4ever
SRM 716 · 2017-05-20 · by cgy4ever · String Manipulation
Problem Statement
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: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.
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
You may assume that a solution always exist. If there are multiple solutions you may return any of them.
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
0)
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".
1)
4 4 7 Returns: "10101010 1011 1010101"
Another solution is: a = "0000111", b = "0000", c = "0000111".
2)
6 7 8 Returns: "10101010 1111010 110101010"
3)
7 8 8 Returns: "10101010 010101101 110101001011"
4)
15 17 19 Returns: "000100101101111011000 11110111010011101010 100100001010101001010101000011111"
Submissions are judged against all 92 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ConstructLCSEasy with a public method string construct(int ab, int bc, int ca) · 92 test cases · 2 s / 256 MB per case