OJ Board

Can you give more hints?

shiplu_1320 wrote:for the input given by rio above,
LIS[0]=4
LDS[0]=5

for the input above

LIS ARRAY IS 3 2 3 2 1 2 1 2 1 1
LDS ARRAY IS 2 4 1 3 4 2 3 1 2 1

then the best value is at

LDS[1]+LIS[1] = 4 + 2 -1 = 5

RC's wrote:By the way, could you share your algorithm here ? Brute force will certainly get Time Limit Exceeded...

1. Compute LIS and LDS using DP O(n^2)
2. loop and compute max(LIS+LDS-1) for all i

UVA 10234, 760,10679,11107,10580,10526
TopCoder DNAMultiMatcher
SPOJ 694,705
Live archive 3628
Timus Bacon’s Cypher
Timus Freedom of Choice

i got this solution from the ACM problem set archive http://www.acm.inf.ethz.ch/ProblemSetArchive.html and i thought that i did not understand the problem statement correctly anyway thank you maybe there was a problem in the judge solution in the contest itself and they corrected here.

Thanks again

Can anyone tell what is the correct output for this problem for the following input:


baabbbbaabaaaaa
aabbababbbaaa
b
abb

according to what is written in this thread

a --> baabbbbaabaaaaa
b --> aabbababbbaaa
start --> b
z --> aab



so starting with


b


and applying one Direct derivation


b ...