Magic StringsProblem 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
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
Can any 1 eloborate w.r.t
Can any 1 eloborate w.r.t "similarq"?
How we get "imilaq"? I thought it to be "imilarq" ?
The sample output is correct.
The sample output is correct.
Re-read the problem
Re-read the problem statement. 'imilarq' is not a magic string.
admin, please delete the
admin, please delete the previous two comments ASAP :(
plz xplain the xample:-- for
plz xplain the xample:-- for
sry my mistake must have read
sry my mistake
must have read the question carefullyy
i hv understood the question now......
I have a few doubts, would
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
@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
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
The machine configurations can be found on the wiki at www.codechef.com/wiki .
I think you shouldn't blame
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
Time Limit is Too strict. My O(N^2) solution got TLE
Therefore your O(N^2)
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
I got accepted
Thanks for your reply
Again poor time limit got AC
Again poor time limit got AC vai using scanf
well got on quite late..
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
submit page for this prob is not loading :(
now it is.. admin, a good
now it is..
admin, a good feature wud be showin the amount of time exceeded
There's no way of knowing
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.