Vera and LCS

View as PDF

Submit solution

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

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
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 S is a string obtained by deleting some letters of S (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 A and B is a string that is a subsequence of both A and B that has the maximum length among all strings that are a subsequence of both A and B. 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 A, B, both of length N and she had to determine the length of the LCS of A and B. She determined the answer to be K but lost B. Given A and K, help her find a possible value of B. It is possible that Vera may have made a mistake and no such B exists, in that case output WRONGANSWER.

Constraints

  • 1 \le N \le 2000
  • 0 \le K \le 2000
  • N, K are integers
  • A consists of N lowercase letters

Input Specification

The input will be in the format:

N K

A

Output Specification

Output one line consisting of the string B of N lowercase letters, or WRONGANSWER if no B is valid. If there are multiple correct B 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

Comments


  • 0
    vpro8725  commented on Oct. 30, 2019, 9:48 a.m.

    Hey guys. I'm getting WA on a few test cases, but the others are right. Some notable examples are #8, #10, and #16... Any help?


    • 1
      kingW3  commented on Oct. 30, 2019, 9:24 p.m.

      Your string doesn't necessarily satisfy LCS of A and B is equal to K.