Waterloo 2017 Winter B - Vera and LCS

View as PDF

Points: 10
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
2017 Winter Waterloo Local ACM Contest, Problem B

Vera is learning about the longest common subsequence problem.

A string is a (possibly empty) sequence of lowercase letters. A subsequence of a string is a string obtained by deleting some letters of (possibly none or all). For example vra, a,  (empty string), and vera are all subsequences of vera. The longest common subsequence (LCS) of two strings and is a string that is a subsequence of both and that has the maximum length among all strings that are a subsequence of both and . There could be multiple LCS for two given strings. For example, a LCS of vera and eats is ea.

For homework, she was given two strings , , both of length and she had to determine the length of the LCS of and . She determined the answer to be but lost . Given and , help her find a possible value of . It is possible that Vera may have made a mistake and no such exists, in that case output WRONGANSWER.

Constraints

• , are integers
• consists of lowercase letters

Input Specification

The input will be in the format:

Output Specification

Output one line consisting of the string of lowercase letters, or WRONGANSWER if no is valid. If there are multiple correct output any of them.

Sample Input 1

4 2
vera

Sample Output 1

eats

Explanation of Sample Output 1

Another possible answer is uber.

Sample Input 2

4 5
vera

Sample Output 2

WRONGANSWER