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

View as PDF

Points: 10
Time limit: 0.1s
Java 1.0s
Python 1.0s
Memory limit: 256M

Author:
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 on the first line, the length of the string .

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

#### 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

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

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

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

I don't think is possible.

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

is possible, but it's best not to discuss solutions to an ongoing contest problem.

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

Is every case guaranteed to have a substring?

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

or a palindrome, rather.

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

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

Thanks,

hob

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

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

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

:D

hob

• 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? >:(

• commented on Jan. 16, 2015, 5:30 p.m. edited

hob shh