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

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


Sample Output



  • 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.

  • 0
    bobhob314  commented on Jan. 17, 2015, 5:13 p.m. edited

    Since this problem is only N == 25000 characters or less, a O(N) solution is not required, correct?

    • -2
      quantum  commented on Jan. 17, 2015, 5:19 p.m. edited

      I don't think O(n) is possible.

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

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

  • -1
    omaewamoushindeiru  commented on Jan. 16, 2015, 6:02 p.m. edited

    Is every case guaranteed to have a substring?

    • -1
      omaewamoushindeiru  commented on Jan. 16, 2015, 6:02 p.m. edited

      or a palindrome, rather.

      • -1
        thorthugnasty  commented on Jan. 16, 2015, 6:16 p.m. edited

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

  • 0
    bobhob314  commented on Jan. 15, 2015, 7:34 p.m. edited

    I'm using Python 3 and for the first test case my code always prints out a list even when I use "".join(alist) in the end, always. Is this a unique situation? If it is, feel free to mention so.



    • 0
      FatalEagle  commented on Jan. 15, 2015, 7:36 p.m. edited

      Line 8 of your solution is printing something before the end of your solution.

      • 1
        bobhob314  commented on Jan. 15, 2015, 7:37 p.m. edited

        Thanks FatalEagle. Caught that right when you did. ;)

        By the way, I love how DMOJ is going. I hope you get 1000 users soon!



  • 1
    bobhob314  commented on Jan. 15, 2015, 6:03 p.m. edited

    I hope that this is not considered spam, but you should really put a spoiler alert in here. Aang dies? >:(