## Search found 7 matches

Fri Jan 09, 2009 6:52 pm
Forum: Volume 108 (10800-10899)
Topic: 10881 - Piotr's Ants
Replies: 12
Views: 6958

### Re: 10881 - Piotr's Ants

Can you give more hints?
Mon Jun 23, 2008 10:11 pm
Forum: Volume 114 (11400-11499)
Topic: 11456 - Trainsorting
Replies: 20
Views: 10571

### Re: 11456 - Trainsort

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
Mon Jun 23, 2008 7:11 pm
Forum: Volume 114 (11400-11499)
Topic: 11456 - Trainsorting
Replies: 20
Views: 10571

### Re: 11456 - Trainsort

rest wrote:plz.. explain what do you mean by LIS or LDS ?

LIS = Longest_increasing_subsequence starting at location i
LDS = Longest_decreasing_subsequence starting at location i

http://en.wikipedia.org/wiki/Longest_in ... ubsequence
Sun Jun 22, 2008 5:12 am
Forum: Volume 114 (11400-11499)
Topic: 11456 - Trainsorting
Replies: 20
Views: 10571

### Re: 11456 - Trainsort

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
Fri Jun 20, 2008 5:24 pm
Forum: Algorithms
Topic: Need for string problems
Replies: 1
Views: 2020

### Re: Need for string problems

UVA 10234, 760,10679,11107,10580,10526
TopCoder DNAMultiMatcher
SPOJ 694,705
Live archive 3628
Timus Bacon’s Cypher
Timus Freedom of Choice
Tue Apr 17, 2007 2:06 am
Forum: Volume 3 (300-399)
Topic: 310 - L--system
Replies: 29
Views: 8738
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
Tue Apr 17, 2007 1:38 am
Forum: Volume 3 (300-399)
Topic: 310 - L--system
Replies: 29
Views: 8738
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 --> aabbababbba...