Magic Strings

Problem code: J5

All submissions for this problem are available.

Magic strings, invented by the Bytelandians, are strings that contain immense magical power within themselves. Magic strings could bring luck and happiness to the Bytelandian citizens. Formally, a string S of length n is a magic string if it satisfies the following conditions:

  • All letters of S are lowercase letters of the English alphabet.
  • Si is lexicographically smaller than Sn-i+1 for all odd i from 1 to [n/2].
  • Si is lexicographically greater than Sn-i+1 for all even i from 1 to [n/2].

(Si (1 ≤ i ≤ n) denotes the ith character of S). For example, the word "difference" is a magic string, while "similar" is not.

Given a string S of lowercase English letters, write a program to find the longest magic string than can be obtained by removing some letters of S. If there are more than one solutions, choose the longest magic string which is lexicographically smallest.

Input

The first line contains t, the number of test cases (about 10). Then t test cases follow. Each test case contains a string S written in a single line. S does not contain more than 2000 letters.

Output

For each test case, print the longest magic string that is lexicographically smallest in a single line.

Example

Input
3
difference
similarq
caaat

Output
difference
imilaq
aat
Date: 2009-10-15
Time limit: 2s
Source limit: 50000
Languages: C C99 strict C++ PAS gpc PAS fpc JAVA NICE JAR C# NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK CAML CLPS PRLG WSPC BF ICK TEXT JS


Comments

Can any 1 eloborate w.r.t

santhosh somashekaraiah - 2nd Nov,2009 12:03:28.

Can any 1 eloborate w.r.t "similarq"?

 

How we get "imilaq"? I thought  it to be  "imilarq" ?

The sample output is correct.

Stephen Merriman - 2nd Nov,2009 13:58:12.

The sample output is correct.

Re-read the problem

Aniruddha (Codechef) - 2nd Nov,2009 14:01:12.

Re-read the problem statement. 'imilarq' is not a magic string.

admin, please delete the

Stephen Merriman - 3rd Nov,2009 09:26:02.

admin, please delete the previous two comments ASAP :(

plz xplain the xample:-- for

gurpreet - 3rd Nov,2009 14:22:02.
plz xplain the xample:-- for difference isn't it that ceeffiendr the corrsct answer because cd,ee,fa alsso of length 5 and lexicographically smaller than caaat also if we cionsider for 3 letters word isn't it that aac is correct answer because aat>aac lexicographically plz correct me if i m wrng thnx in advance

plz xplain the xample:-- for

gurpreet - 3rd Nov,2009 14:29:11.
plz xplain the xample:-- for difference isn't it that ceeffiendr the corrsct answer because cd,ee,fa alsso of length 5 and lexicographically smaller than caaat also if we cionsider for 3 letters word isn't it that aac is correct answer because aat>aac lexicographically plz correct me if i m wrng thnx in advance

sry my mistake must have read

gurpreet - 3rd Nov,2009 15:02:40.

sry my mistake

must have read the question carefullyy

i hv understood the question now......

I have a few doubts, would

Prashanth K S - 4th Nov,2009 22:09:39.

I have a few doubts, would appreciate it a lot of someone can clarify these.

1) According to the magic string condition, lesser than and greater than conditions are specified. What about equal to condition? Maybe my next question would answer this.

2) Are the inputs provided all already magic strings? As in, in the test cases on the server.

3) In the first test case in the example, there is no change in the output as compared to the input string. Why is this so? Shouldn't I mandatorily remove some characters to form a new magic string? I am unable to understand what happened here.

4) I am unable to understand the meaning of "longest string that is lexicographically smallest".

I am sorry if I throwing some clues in with these questions. Please ignore in such a case.

@Prashanth I guess equal is

Shilp Gupta - 5th Nov,2009 01:09:11.

@Prashanth I guess equal is not to be considered either smaller or greater because of sample test 3. Otherwise answer would have been "aaat" or at least "aaa"

My interpretation of "longest string that is lexicographically smallest" rests on a case like "similarq". obviously "imilar" and "imilaq" both are longest magic strings, but "imilaq" is smaller lexicographically - so, consider the set of solutions with longest magic strings and choose the lexicographically smallest among them

unfortunately, the solution is not so obvious to me (yet?)

are the judge's pc is pentium

Shiplu - 5th Nov,2009 22:43:36.

are the judge's pc is pentium 1 or even more backdated, my codes time complexity is about

8 * 10 ^7 in total(including 10 test cases). I am getting TLE, this is redicolous.

 

10^9 runs in 1 sec in a normal pc like celeron D.

The machine configurations

Aniruddha (Codechef) - 6th Nov,2009 13:52:12.

The machine configurations can be found on the wiki at www.codechef.com/wiki .

I think you shouldn't blame

Ngô Minh Đức - 7th Nov,2009 08:03:57.

I think you shouldn't blame the speed of the server. The fact that there are many people solved this problem on this server means that your algorithm may be just not fast enough.

Time Limit is Too strict. My

rushel - 9th Nov,2009 09:14:01.

Time Limit is Too strict. My O(N^2) solution got TLE

Therefore your O(N^2)

Stephen Merriman - 9th Nov,2009 09:16:27.

Therefore your O(N^2) solution is too slow. 26 people have solved this problem, so the time limit is fine.

I got accepted Thanks for

rushel - 9th Nov,2009 20:18:08.

I got accepted

Thanks for your reply

Again poor time limit got AC

rushel - 9th Nov,2009 23:31:48.

Again poor time limit got AC vai using scanf

well got on quite late..

abhishek agarwala - 11th Nov,2009 02:24:15.

well got on quite late.. tried 3 questions.. the magic string .. the sudokux.. and the box..

the box was pretty simple..

was able to develop algorithm but probably some error in writing the code so did not get the right answer..

guess you cant do 3 problems in a stretch of 12 hours after all..

no point continuing further.....

best of luck to all the guyz still trying...

:)

submit page for this prob is

Anshul Goel - 11th Nov,2009 03:53:46.

submit page for this prob is not loading :(

now it is..   admin, a good

Anshul Goel - 11th Nov,2009 04:14:17.

now it is..

 

admin, a good feature wud be showin the amount of time exceeded

There's no way of knowing

Stephen Merriman - 11th Nov,2009 05:29:16.

There's no way of knowing that; your program is stopped as soon as it exceeds the time limit, otherwise it could run for hours.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM: