TopCoder problem "ContestSchedule" used in SRM 320 (Division I Level Two , Division II Level Three)



Problem Statement

    In the year 3006, almost all of the programming contests are interplanetary and have to be competed in online. All these interplanetary online programming contests are well scheduled. A contest time is defined by two integers s and t. That means that the contest will begin sharply at time s and end before time t. So if a contest ends at 10 and another contest starts at 10. John can participate in both of them.



John is a young talent who is keen on programming contests. For any particular contest, he can pretty accurately estimate the probability that he will win that contest. Given a set of contests, he wants to determine the subset of non-conflicting contests that will maximize his expected number of wins.



You will be given a String[] contests. Each element of contests represents a single contest and is formatted as "s t p" (quotes for clarity only), where s, t, and p are all integers. Each contest starts at time s and ends before time t, and John estimates that there is a p percent probability of winning that contest. Return the maximal expected number of contests that John will win if he participates in the optimal subset of non-conflicting contests.
 

Definition

    
Class:ContestSchedule
Method:expectedWinnings
Parameters:String[]
Returns:double
Method signature:double expectedWinnings(String[] contests)
(be sure your method is public)
    
 

Notes

-A return value with either an absolute or relative error of less than 1.0e-9 is considered correct.
 

Constraints

-contests will contain between 1 and 50 elements, inclusive.
-Each element of contests will be formatted as "s t p" (quotes for clarity only), where s, t, and p are all integers with no leading zeros.
-Each s will be between 1 and 1000000000, inclusive.
-Each t will be between 1 and 1000000000, inclusive.
-In each element of contests, s will be less than t.
-Each p will be between 1 and 100, inclusive.
 

Examples

0)
    
{"1 10 100","10 20 100","20 30 100","30 40 100"}
Returns: 4.0
Since all the contests end right before the next contest starts, John can participate in all the contests.
1)
    
{"10 20 20","30 40 60","15 35 90"}
Returns: 0.9
The third contest conflicts with the first two. John decides to participate in only the third contest because it gives him a higher chance of winning a contest than participating in both of the other two contests.
2)
    
{"1 100 85","99 102 100","101 200 60"}
Returns: 1.45
3)
    
{"1 1000000000 1"}
Returns: 0.01
4)
    
{
"1361955 8940967 10","628145516 644285978 17","883515280 910484865 36",
"762888635 769291174 52","98152102 136328674 1","9580638 20450682 50",
"646139319 664648341 20","484027666 505290970 57","841082555 879295329 99",
"940563715 966953344 4","579113528 595261527 25","925801172 962952912 9",
"285845005 307916055 45","403573723 410697485 10","9467290 25698952 90",
"631265400 650639733 3","520690249 559261759 96","491747709 531061081 86",
"643215695 672420161 94","614608448 617341712 44","456517316 491770747 24",
"806956091 828414045 88","528156706 559510719 15","158398859 190439269 4",
"743974602 761975244 49","882264704 887725893 1","877444309 884479317 59",
"785986538 806192822 19","732553407 747696021 81","132099860 148305810 97",
"555144412 572785730 99","506507263 535927950 82","489726669 505160939 90",
"793692316 804153358 99","901329638 919179990 10","29523791 44318662 58",
"570497239 595701008 73","706091347 730328348 23","118054686 135301010 39",
"307178252 337804001 93","896162463 900667971 39","271356542 273095245 80",
"865692962 891795950 91","593986003 596160000 58","807688147 831190344 59",
"468916697 496462595 92"
}
Returns: 14.12

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6708

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10000&pm=6708

Writer:

lyc1977

Testers:

PabloGilberto , brett1479 , Olexiy , Mike Mirzayanov

Problem categories:

Dynamic Programming