11404 - Palindromic Subsequence

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

ssangbuja
New poster
Posts: 2
Joined: Sun Feb 24, 2008 9:22 am

11404 - Palindromic Subsequence

Post by ssangbuja » Sun Feb 24, 2008 9:33 am

I used DP solution to solve this problem, but I got TLE. It probably take O(n^3) to fill matrix.

[deleted]

any suggestion??
Last edited by ssangbuja on Mon Feb 25, 2008 9:13 am, edited 2 times in total.

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11404 Palindromic Subsequence

Post by Robert Gerbicz » Sun Feb 24, 2008 11:27 am

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

ssangbuja
New poster
Posts: 2
Joined: Sun Feb 24, 2008 9:22 am

Re: 11404 Palindromic Subsequence

Post by ssangbuja » Mon Feb 25, 2008 9:12 am

Robert Gerbicz wrote: So the total time is O(n^2)
Thanks Robert I got AC.

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm

Post by w k » Mon Feb 25, 2008 11:26 pm

I'm getting WA using DP method. Are there any special inputs for this problem?

Wojciech

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Post by Robert Gerbicz » Tue Feb 26, 2008 12:04 am

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!
Last edited by Robert Gerbicz on Fri Feb 29, 2008 2:46 am, edited 1 time in total.

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm

Post by w k » Tue Feb 26, 2008 12:33 am

OK. I got it.

Wojciech

srrajesh
New poster
Posts: 23
Joined: Sun Sep 30, 2007 9:02 pm

Re: 11404 Palindromic Subsequence

Post by srrajesh » Tue Feb 26, 2008 10:49 am

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.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Tue Feb 26, 2008 5:59 pm

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

Anindya
New poster
Posts: 28
Joined: Sun Feb 04, 2007 4:34 am
Location: EEE,BUET,DHAKA

RTE

Post by Anindya » Thu Feb 28, 2008 7:45 am

I am getting RTE,can any one help?

Robert,how for the input:

Code: Select all

pqrodtkwpfyycjphtijvdnjc
u get:

Code: Select all

dtpaaptd
PLZ expain.I can't see any 'a' in the input string.
Does ur AC code produces this output?

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Thu Feb 28, 2008 9:30 am

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

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Thu Feb 28, 2008 3:01 pm

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!

srrajesh
New poster
Posts: 23
Joined: Sun Sep 30, 2007 9:02 pm

Post by srrajesh » Thu Feb 28, 2008 8:05 pm

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.

srrajesh
New poster
Posts: 23
Joined: Sun Sep 30, 2007 9:02 pm

Post by srrajesh » Thu Feb 28, 2008 8:07 pm

Thanks a lot, for a good explanation.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Fri Feb 29, 2008 2:25 am

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
Last edited by rio on Fri Feb 29, 2008 4:57 am, edited 1 time in total.

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: RTE

Post by Robert Gerbicz » Fri Feb 29, 2008 2:42 am

Anindya wrote:I am getting RTE,can any one help?

Robert,how for the input:

Code: Select all

pqrodtkwpfyycjphtijvdnjc
u get:

Code: Select all

dtpaaptd
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).

Post Reply

Return to “Volume 114 (11400-11499)”