Algorithm for Contest Schedule -

can explain algorithm solve problem? http://community.topcoder.com/stat?c=problem_statement&pm=6708&rd=10000. explanation given here hard understand http://community.topcoder.com/tc?module=static&d1=match_editorials&d2=srm320

i believe not pity did not understand "solution", because explained without giving essential details and... incorrect well.

first of all, there should no real importance whether start search optimal solution start , going forward or start search end , go backwards towards start. off course, there slight difference, because if john manages finish tasks on contest earlier end time, might able still catch next contest. therefore, if direction matters @ all, should start planning start time , should go forward, end time might earn possibility participate on other contests well. let not dwelve ourselves deep details, small difference not important little task, important in serious project.

i have been harsh solution called incorrect. repeat: incorrect. if again @ pseudo-code , forget in-elegant backwards direction (which might useful in other problems, not here) notice contest chosen or not chosen when iterate time. imagine case when there contest takes place in time span of day, john participate in 4 other contests in meantime, should choose between participating in long contest or in other 4 contests. let's suppose john has high probability win long contest , lower probability win other 4 contests. in iteration given can see whether long contest or 4 other contests better choices after 1 or 2 shorter contests taken out of contention.

a backtrack solution, generating possible scenarios , finding best choice solve problem, have exponential complexity.

"then value of a[s] can computed backward." yes, can computed backwards. writer giving reason why should computed backwards, why better choice compute backwards? no. yes, common approach in dynamic programming attack problem backwards , in many cases there reason, here not see valid reason why should compute backwards, problem symmetric in time, difference between "forward" , "backward" being start of time , end of time in question, 2 constants.

let's elaborate example given earlier. let's suppose there 5 contests:

1. s = 1, t = 24, p = 0.99
2. s = 2, t = 3, p = 0.66
3. s = 4, t = 5, p = 0.66
4. s = 6, t = 7, p = 0.66
5. s = 8, t = 9, p = 0.66

as see, in each time, contest 1. more attractive each of contest 2, 3, 4 , 5. far more attractive contest 1.

so, algorithm having exponential complexity better. slow hell, hey, correct in contrast "solution" given. if want solution, can stop reading here. if want hear better solution, read on.

let's suppose define logical operator of "exclusion", symmetric. if contest c1 excludes contest c2, c2 excludes c1 well.

let's suppose further while read input building data-structure holding exclusion clusters: each cluster maximal set of contests each c1 , c2 either directly or transitively exclude each-other. find best solution each cluster divide et impera , when know solution clusters, task need finish job merge sub-results have whole result.