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

View as PDF
Submit solution
Points: 10
Time limit: 0.1s
Java 1.0s
Python 1.0s
Memory limit: 256M
Author:
thorthugnasty
Problem type

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


  • 0
    htoshiro  commented on April 30, 2024, 1:26 a.m.

    https://dmoj.ca/problem/cco97p1


  • 4
    AndrewVII  commented on May 4, 2017, 2:25 a.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.


  • 0
    bobhob314  commented on Jan. 17, 2015, 10:13 p.m. ← edit 2

    Since this problem is only N = 25\,000 characters or less, an \mathcal{O}(N) solution is not required, correct?


    • -3
      quantum  commented on Jan. 17, 2015, 10:19 p.m. ← edit 2

      I don't think \mathcal{O}(N) is possible.


      • 0
        FatalEagle  commented on Jan. 17, 2015, 10:30 p.m. ← edited

        \mathcal{O}(N) is possible, but it's best not to discuss solutions to an ongoing contest problem.


  • 0
    omaewamoushindeiru  commented on Jan. 16, 2015, 11:02 p.m. ← edited

    Is every case guaranteed to have a substring?


    • 0
      omaewamoushindeiru  commented on Jan. 16, 2015, 11:02 p.m. ← edited

      or a palindrome, rather.


      • 1
        thorthugnasty  commented on Jan. 16, 2015, 11:16 p.m. ← edited

        A single letter is a palindrome, and the input string will have length greater or equal to 1, so yes.