WinterAndReindeers
SRM 601 · 2013-06-25 · by Witaliy
Problem Statement
It's winter time! Time to play some games.
Four reindeers are playing the following game. The first three of them choose three non-empty strings: A, B, and C. (The strings are not necessarily distinct.) Then, the fourth one (and it happens to be the youngest one) finds a string S that satisfies the following conditions:
- S is a subsequence of A. (I.e., either S equals A, or S can be obtained from A by removing some of its characters.)
- S is a subsequence of B.
- C is a (contiguous) substring of S.
- There is no string longer than S that satisfies the previous three conditions.
You are given three
Constraints
- allA, allB and allC will each contain between 1 and 50 elements, inclusive.
- Each element of allA, allB and allC will contain between 1 and 50 characters, inclusive.
- Each element of allA, allB and allC will consist only of uppercase English letters ('A'-'Z').
{"X"}
{"X", "Y"}
{"X"}
Returns: 1
In this case, A = "X", B = "XY", C = "X". The longest possible string that satisfies conditions from the statement is "X". Thus, the answer is 1.
{"ABCXD"}
{"BCDEF"}
{"CD"}
Returns: 3
The longest possible string in this case is "BCD".
{"WE", "LOVE"}
{"WORKING", "FOR", "SANTA"}
{"JK"}
Returns: 0
No string satisfies all criteria in this case. Thus, the answer is 0.
{"ABCDE"}
{"CDEAB"}
{"B"}
Returns: 2
{"A"}
{"A"}
{"A"}
Returns: 1
Submissions are judged against all 69 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class WinterAndReindeers with a public method int getNumber(vector<string> allA, vector<string> allB, vector<string> allC) · 69 test cases · 2 s / 256 MB per case