Search found 7 matches

by wahab
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?
by wahab
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
by wahab
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

you can read about them at

http://en.wikipedia.org/wiki/Longest_in ... ubsequence
by wahab
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
by wahab
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
by wahab
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
by wahab
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...

Go to advanced search