Page 1 of 2
11404 - Palindromic Subsequence
Posted: Sun Feb 24, 2008 9:33 am
by ssangbuja
I used DP solution to solve this problem, but I got TLE. It probably take O(n^3) to fill matrix.
[deleted]
any suggestion??
Re: 11404 Palindromic Subsequence
Posted: Sun Feb 24, 2008 11:27 am
by Robert Gerbicz
ssangbuja wrote:
any suggestion??
There is a fast O(n^2) dp method (space requirement is also O(n^2) ) to determine the length of the longest palindrom, it's well known. But in this problem you have to print the lexicographically smallest palindrom, which is the longest, and you can do that in O(|size of alphabet|*n) time. (So the total time is O(n^2))
Re: 11404 Palindromic Subsequence
Posted: Mon Feb 25, 2008 9:12 am
by ssangbuja
Robert Gerbicz wrote:
So the total time is O(n^2)
Thanks Robert I got AC.
Posted: Mon Feb 25, 2008 11:26 pm
by w k
I'm getting WA using DP method. Are there any special inputs for this problem?
Wojciech
Posted: Tue Feb 26, 2008 12:04 am
by Robert Gerbicz
w k wrote:I'm getting WA using DP method. Are there any special inputs for this problem?
Wojciech
There is no special case (but make sure that the word can be very long!).
But here some handgenerated small tests:
Code: Select all
h
hh
hy
yh
bab
abb
bba
abba
baba
abc
pu
bard
puma
abca
wyzw
wwww
book
The correct output is:
Code: Select all
h
hh
h
h
bab
bb
bb
abba
aba
a
p
a
a
aba
wyw
wwww
oo
And here it is computer generated (random) input:
Code: Select all
dj
inc
klje
f
tgsmb
camd
wuqrgoa
mnl
byjfwdy
fvzzgke
rqe
mvwkohogfsx
cuhpqfxiunxo
fnwfghlxlg
gwxbp
ptutmv
ixdzjgqulmofs
adooewvkzskhdshhb
ltr
vllszwcfmg
idqqbqjertwskxan
n
sthucm
oduartneikjrdwokcenazl
miymgoxfaikovni
olfjkahkhwepcoyrhsaeed
ykbpchdphhvtqjjqijzmfpbinxhr
mwpvynkyxvwz
httxnbkqg
yyusciwqurzxwqopscyfaorv
oturynskpb
pkgoxdyddjau
itylavuwslcgjqccaglzfifhiynudssgb
fjpnhawxcftjnrrrflpwfou
evxmcftyfvhpahl
zpdpurzruypsihwqk
qdqkvyeybyrjx
bokenrlnlrcsgbczi
fnajtziuuiasselcov
gmpiqbsrkwsffrlytak
knprzizjinmhaoesymmhzregsxudbanvwd
ksefaihytncrtqhwvhytpzxhh
grriqcxmtepetanjpiqvlsyyermepwcwdeluxzwx
fjyxnicmnppxwkntjdhyh
ndkkjzbaouql
siuhfovapcwpedsmxknkspsdueazeucocf
oguodmhctxglulbneieqdgdotczmpabtmbn
bngsoicogmbajkkinjukmzovvkrqpbcgwrulpzzfaafrolqz
bygsgvjjhwamsv
qxtalhgqdykgivewohltbkdfinmrtma
lczdrsfargkjgb
clzcqcxvrtdifzvbkjhhm
qeptxcuyppyydtpkefxsbhkteggmkmtqpnnjvgfxxcpesgjns
bhfczpzyawklrnaoarzshujggfpjqaxi
pqrodtkwpfyycjphtijvdnjc
vzcofter
vxywaztuw
zbynpvykntuibgwmq
dnpvirovb
kczjrozzjkjvonvfzyxlxdxpmpcqqbxarcexvjau
bksuivw
tys
See Rio's post to get the correct output for this input set!
Posted: Tue Feb 26, 2008 12:33 am
by w k
OK. I got it.
Wojciech
Re: 11404 Palindromic Subsequence
Posted: Tue Feb 26, 2008 10:49 am
by srrajesh
Robert Gerbicz wrote:
But in this problem you have to print the lexicographically smallest palindrom, which is the longest, and you can do that in O(|size of alphabet|*n) time. (So the total time is O(n^2))
Can you explain how you print lexicographically least palindrome with O(|size of alphabet|*n) time? I thought hard, i am not able to get how to do it! Do you use any other array, other than the one used to compute the length of the longest palindrome?
Thanks in advance.
Posted: Tue Feb 26, 2008 5:59 pm
by emotional blind
To show the longest palindromic subsequence from index i to j, find first 'a' and last 'a' between i and j and calculate the length of longest subsequence of s[i+1] to s[j-1], do same thing with 'b' to 'z'. take the character for which it gives the largest subsequence, if two character gives the same result smaller one should be considered. and this character will be the first and last character of longest palindromic subsequence in between s and s[j]. Let the character first exists in index x and last exists in y, then do the same thing in s[x+1] to x[y-1].
RTE
Posted: Thu Feb 28, 2008 7:45 am
by Anindya
I am getting RTE,can any one help?
Robert,how for the input:
u get:
PLZ expain.I can't see any 'a' in the input string.
Does ur AC code produces this output?
Posted: Thu Feb 28, 2008 9:30 am
by rio
My code outputs below for Robert's second input:
Code: Select all
d
c
e
f
b
a
a
l
ydy
zz
e
oho
ufu
glxlg
b
tut
d
dkskd
l
ll
qbq
n
c
anekdkena
ioaoi
ahcha
bpqjjqpb
wvykyvw
tt
ycqrqcy
b
ddd
ilacccali
fpfrrrfpf
vftfv
purzrup
qdq
brlnlrb
aiuuia
kffk
nrzhmmhzrn
hthvhth
xepeyyepex
jxncnxj
kk
foaedsknksdeaof
mctgeiegtcm
gcomjkkjmocg
sjjs
alhgdghla
gjg
zcqcz
epcptkebektpcpe
fzraoarzf
dtpyyptd
c
waw
bnknb
viv
jvxxpmpxxvj
b
s
This problem could also be solved by modified Hunt-Szymanski algorithm, an algorithm for LCS.
In this case, you could get the lexicographically smallest palindrome by calculating the lexicographically smallest LCS.
-----
Rio
Posted: Thu Feb 28, 2008 3:01 pm
by sohel
rio wrote:
This problem could also be solved by modified Hunt-Szymanski algorithm, an algorithm for LCS.
Could you please describe this algorithm? I couldn't find enough information on the net!
Posted: Thu Feb 28, 2008 8:05 pm
by srrajesh
rio wrote:
This problem could also be solved by modified Hunt-Szymanski algorithm, an algorithm for LCS.
In this case, you could get the lexicographically smallest palindrome by calculating the lexicographically smallest LCS.
If the algorithm you claimed is not based on the fact that all LCS must be palindromic, then it is ok. The problem with LCS is that, there are some common subsequences which may not be palindromic. I found
this thread, discussing on the topic.
Posted: Thu Feb 28, 2008 8:07 pm
by srrajesh
Thanks a lot, for a good explanation.
Posted: Fri Feb 29, 2008 2:25 am
by rio
Could you please describe this algorithm? I couldn't find enough information on the net!
Brief explanation of Hunt-Szymanski algorithm:
For two strings x and y, (i, j) is called match iff x[ i ] = y[ j ].
For two matches (i1, j1) and (i2, j2), (i1, j1) < (i2, j2) iff i1<i2 and j1<j2.
Common sequence of x and y is an increasing sequence of match of x and y.
So LCS problem came down to LIS problem on the match set.
And I think you know that LIS could be solved with O(nlogn).
If the algorithm you claimed is not based on the fact that all LCS must be palindromic, then it is ok. The problem with LCS is that, there are some common subsequences which may not be palindromic.
Yes. The algorithm I'm talking is not simple adaption of LCS on s and reverse s.
To adapt Hunt-Szymanski algorithm to solve palindrome, you have to redefine the match definition.
Also there is a problem to care with the parity of length of the longest palindrome.
But after you get the match set, rest is as same as Hunt-Szymanski.
-----
Rio
Re: RTE
Posted: Fri Feb 29, 2008 2:42 am
by Robert Gerbicz
Anindya wrote:I am getting RTE,can any one help?
Robert,how for the input:
u get:
PLZ expain.I can't see any 'a' in the input string.
Does ur AC code produces this output?
Sorry for that! There was an error in the random generation. (some invalid spaces in the word).