VM7WC '15 #2 Silver - 4 Nations, 1 Secret

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

After the death of Avatar 安昂 (Aang), the world of Avatar changed forever. People did not feel safe anymore without him. Without a world leader, the Red Lotus was created with the intention of destroying all order and bringing the world back into "natural" chaos. Members of the Red Lotus are scattered throughout the world of Avatar and they communicate using a complicated system. The members send lines to each other, but only the longest palindrome has value. You must crack the code to keep the world safe until Korra grows up.

The message will consist of a single string of uppercase letters. You are to write a program which finds the longest palindrome in the given string of characters.

Hint: Each palindrome has a "center" around which one side of the palindrome is a mirror image of the palindrome. For example, for abcba, the center is the letter c, because ab is the reverse of ba. For abba, the center lies between the two bs, because ab is the reverse of ba. Try using this fact to come up with an algorithm that is fast enough.

Input Specification

The input file starts with a single integer N on the first line, the length of the string (1 \le N \le 25\,000).

The next line is the message, a string of length N.

Output Specification

Your program should output a pair of lines with the longest palindrome on the first line and the length of the palindrome on the second line. In the event of a tie for the longest palindrome, the one closest to the beginning of the line should be printed.

Sample Input

36
AHAHJHFYUBNMLOIUYTRERTYUIOLMNBAGWOIS

Sample Output

BNMLOIUYTRERTYUIOLMNB
21

Comments


  • 5
    AndrewVII  commented on May 3, 2017, 10:25 p.m. edited

    Is it possible that the longest palindrome has a length of one? If so, what is the output?

    EDIT: I guess if it has a length of one, you would output the first character and length one, but I do not believe that any of the test cases has a longest palindrome of length one.