ACM ICPC Regional Problem

ACM ICPC componental difficultySiti Nazihah Binti Sarpin (L)Nurul Aini Binti Mohd HisanTable of Contents (Jump to)Introduction line of work DescriptionProblem StatisticsProblem DetailsACM ICPC Regional ProblemReason to Choose This ProblemPreliminary AnalysisMathematical ModelingTest slipperiness 1 ( example gossip and output from the caper)Test Case 2 (New input and output)Possible Algorithm Design Technique tool ForceDynamic program0-1 knapsacksReferencesIntroductionProblem DescriptionBessie has gone on a trip, and shes riding a curlicue coaster Bessie reall(a)y likes riding the roller coaster, but unfortunately she often gets dizzy.The roller coaster has a number of distinct sections that Bessie rides in order. At the beginning of the ride, Bessies vertigo and romp levels are both at 0. For each section of the roller coaster, Bessie rat either keep her look open or keep them closed (and must keep them that way for the whole section). If she keeps her eyeball open for a section, her descend cheer increases by a sportsman factor for that section, and her giddiness increases by a Dizziness factor for that section. However, if she keeps her eye closed for the section, her do mutant pull up stakes non change, but her silliness will decrease by a value thats constant for the entire roller coaster. (Note that her lightheadedness cigarette never go below 0.)If, at any point, Bessies giddiness is above a certain put, Bessie will get sick. Write a program to find the level best core of diversion Bessie can have without getting sick.InputThere will be several streak instances in the input. Each establish persona will begin with a line with three integersN K LWhere N (1 N 1,000) is the number of sections in this particular roller coaster, K (1 K 500) is the come that Bessies giddiness level will go down if she keeps her eyes closed on any section of the ride, and L (1 L 300,000) is the limit of dizziness that Bessie can tolerate if her dizziness ever becomes larger than L, Bessie will get sick, and thats not funEach of the next N lines will describe a section of the roller coaster, and will have two integersF DWhere F (1 F 20) is the increase to Bessies issue forth fun that shell get if she keeps her eyes open on that section, and D (1 D 500) is the increase to her dizziness level if she keeps her eyes open on that section. The sections will be listed in order. The input will end with a line with three 0s.OutputFor each test upshot, output a single integer, representing the upper limit inwardness of fun Bessie can have on that roller coaster without exceeding her dizziness limit. Print each integer on its own line with no spaces. Do not print any blank lines between answers.Sample Input3 1 22 13 15 210 5 120 212 43 310 620 319 919 71 50015 54 20 0 0Sample Output70Problem StatisticsAccording to ACM-ICPC archive website, the count submission of this bother is 2226. There are 183 users have solved this problem while 246 users that tried this problem (last update on 10 Dec 2014).This problem can be found at https//icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudgeItemid=8category=410page=show_problemproblem=2871.Problem DetailsACM ICPC Regional ProblemRegion ACM ICPC Regionals 2010 North America Southeast USAYear 2010Problem H, 4870 Roller Coaster 4.500 secondsLinkhttps//icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudgeItemid=8category=410page=show_problemproblem=2871Source Code https//github.com/depstein/programming-competitions/blob/master/problems/04-10-14%20intro/4870%20(Roller%20Coaster)/rollercoaster.javaProgrammer N/A.Reason to Choose This ProblemThis problem is chosen to fulfill a requirement of CSC750, Advance Algorithm and Analysis that needed the problem that can be solved using Dynamic Programming. This problem belongs to 0-1 rucksack problem which require us to find the upper limit amount of fun can Bessie have without reservation her sick.Prelim inary AnalysisThis problem is to obtain the level best amount of fun Bessie can have when riding a roller coaster without getting sick, in which national without exceeding her dizziness limit.The constraints of the problem includeThe roller coaster has a distinct number of sections that Bessie rides in order.Bessies fun and dizziness levels are both at 0 at the beginning of the ride.For each section, Bessie has two options either to keeps her eyes open or close and she must keep them that way for the whole section.At any section, when Bessie keeps her eyes open, her score dizziness increases by a dizziness factor and her total fun also increases by a fun factor. *At any section, when Bessie keeps her eyes closed, her total dizziness will be subtracted by a value that is constant for the entire roller coaster, but her total fun is maintain. *Bessies dizziness can never go below 0.Bessie will get sick if her dizziness is above a given limit. ** Tricky constraint.The parameters for this problem are listed as belowN (1 N 1000), the number of sections in a particular roller coaster.K (1 K 500), the amount that Bessies dizziness level will be subtracted if she keeps her eyes closed on any section of the ride.L (1 L 300,000), limit of dizziness that Bessie can stand.F (1 F 20), the increases to Bessies total fun if she keeps her eyes open on that section.D (1 D 500), the increases to her dizziness level if she keeps her eyes open on that section.000, the c unflinching command line for tenia the test causes.This problem belongs to 0-1 Knapsack problem. This is due to the same properties this problem had as with a Knapsack problem in which it contains a set of distributor points where each item consists of weight and value, the total weight must be less than or equal to the given limit, and a maximum total value (in which case it must consider the given limit of the sack can carry) 1. Thus, for this Roller Coaster problem, the properties listed below have adapted the knapsack tooth rootThe item in this problem consists of Bessies dizziness level (weight) and fun level (value).Her dizziness is how much she can carries in her sack (total weight of the items she carries in the sack).Her fun is what she would like to maximize (total value of the items she carries).Now, we want to get the maximum total fun she could have without making her too dizzy (maximum total fun = maximum total value in her sack) (limit of dizziness = weight limit for the sack).Furthermore, this problem is tied with another tricky constraints in which it affected the dizziness level and fun level at each distinct section, in which case Bessie has two options either to open or close her eyes during riding that roller coaster (in Knapsack problem, whether an item is in the sack or not). If she keeps her eyes open, both dizziness and fun level will increase. Meanwhile, if she keeps her eyes close, her fun level will expect the same as with the previous section, but her dizziness level will increase.In conjunction with these tricky constraints, it can be broken down into legion(predicate) sub-problems 2, hence the Knapsack solution to this problem does not have to perform backtracking or recursion. This is because the previously solved sub-problems are stack awayd in tables and can be employ again instead of re-computing the solution each time 2. In summary, this Knapsack problem is more suitable if it is solve by using Dynamic Programming technique compare with brute draw and quarter algorithm.Mathematical ModelingInputThe number of sections in a particular roller coaster.The amount that Bessies dizziness level will be subtracted if she keeps her eyes closed on any section of the ride.The limit of dizziness that Bessie can stand.The increases to Bessies total fun if she keeps her eyes open on that section.The increases to her dizziness level if she keeps her eyes open on that section.The fixed command line for stopping the test cases.O utput The maximum amount of fun Bessie can have on that roller coaster without exceeding her dizziness limit.Let,the number of sections in a particular roller coaster = N, where N 1 and N 1000,the amount that Bessies dizziness level will be subtracted if she keeps her eyes closed on any section of the ride = K, where K 1 and K 500,the limit of dizziness that Bessie can stand = L, where L 1 and L 300000,the increases to Bessies total fun if she keeps her eyes open on that section = F, where F 1 and F 20,the increases to her dizziness level if she keeps her eyes open on that section = D, where D 1 and D 500, andthe fixed command line for stopping the test cases = 000.To mathematically model this problem, it uses array tables to obtain the maximum total fun Bessie could have without getting sick 4.It is important to make sure total dizziness (DTotal) can never go below zero and must not exceed the given limit. Hence, DTotal 0 and DTotal L.Moreover, depending on Bessies eyes trail (either open or close), it will affect each of the total fun and total dizziness. Hence,F wanton = F + Ffun at nth section,D unmortgaged = D + Ddizzy at nth section,FClose = Ffun at nth section,DClose = Ddizzy at nth section K,where F open, DOpen, FClose, DClose N.Thus a solution for the problem is to find the minimum dizziness Bessie could have with the maximum fun 4.DPNF is the minimum dizziness Bessie can have, with fun = F.DPNF = max(DPN 1F (fun at the nth section) + (dizziness at the nth section), DPN 1F K).First table is to store the sections number N and the other one is to store the total fun F. Note that both initial arrays of fun and dizziness level are set to 0.The track of the roller coaster must pass all section meaning to move to the next section both table will become N-1 F FunN. By using those tables, for each section, we can obtain the maximum fun Bessie can have. When move to the next section, it just retrieves the previously stored result in order t o get the new result for the new section.Test Case 1 (Sample input and output from the problem)Sample inputSample output3 1 22 13 15 27Table 1 Sample input and output of test case 1Table 2 illustrates the optimal solution for test case 1 from the sample input given by the Roller Coaster problem. This roller coaster track has a total of 3 sections, the amount that Bessies dizziness level will be subtracted if she keeps her eyes closed on any section of the ride is 1, and the limit of dizziness that Bessie can stand is 2. The maximum total fun Bessie could have without getting sick is 7 and her dizziness is 2. During riding that roller coaster, Bessie had her eyes open in section 1 and 3, and close her eyes in section 2. look break take aim ofFunDizzinessInitial00Open contribution 12 10 + 2 = 20 + 1 = 1CloseSection 23 121 1 = 0OpenSection 35 25 + 2 = 70 + 2 = 2Table 2Optimal solution for test case 1 from sample input Roller Coaster problemTest Case 2 (New input and output)InputOutpu t12 3 85 43 28 26 112 518 212 310 415 216 510 36 180Table 3 input and output from test case 2This roller coaster track has a total of 12 sections, the amount that Bessies dizziness level will be subtracted if she keeps her eyes closed on any section of the ride is 3, and the limit of dizziness that Bessie can stand is 8. The maximum total fun Bessie could have without getting sick is 80 and her dizziness is 6. During riding that roller coaster, Bessie had her eyes close in section 2 5, 8 and 10, and open her eyes in other sections. Meanwhile, Table 4 shows how the solution is achieved.Eyes ConditionLevel ofFunDizzinessInitial00OpenSection 15 40 + 5 = 50 + 4 = 4CloseSection 23 254 3 = 1OpenSection 38 25 + 8 = 131 + 2 = 3OpenSection 46 113 + 6 = 193 + 1 = 4CloseSection 512 5194 3 = 1OpenSection 618 219 + 18 = 371 + 2 = 3OpenSection 712 337 + 12 = 493 + 3 = 6CloseSection 810 4496 3 = 3OpenSection 915 249 + 15 = 643 + 2 = 5CloseSection 1016 5645 3 = 2OpenSection 1110 364 + 10 = 742 + 3 = 5OpenSection 126 174 + 6 = 805 + 1 = 6Table 4 An modeling of input for Roller Coaster problemPossible Algorithm Design TechniqueRoller coaster problem can be solved using brute force technique or dynamic programming. There is no doubt that this problem can be solved using brute force and it can stick the correct output but it will caused an exponential time to the program. Therefore, Dynamic Programming is the better approach to solve Roller Coaster problem.Brute ForceBrute force technique is not recommended to solve this problem because it will result in an exponential solution 3 as we have to modify the spring (either Bessies eyes open or close) and compare each result every time in order to obtain the optimal solution. In addition, if the number of test cases is getting bigger, it is quite impossible to get a short period of time taken as to calculate every sub-problem. Since there is no limit on the test case, user can state their input as much as they want. Lets take s ample test case 1 as an example shown in Table 1.3 1 22 13 15 23 1 2 N = 3, K = 1, and L = 2.2 1, 3 1, and 5 2 F = 2, 3, 5 and D = 1, 1.Table 5 Sample test case 1 from the Roller Coaster problemBrute force algorithm will test all the possibilities of Bessies eyes condition, either she had her eyes opened or closed.Eyes ConditionLevel ofFunDizzinessInitial00OpenSection 12 10 + 2 = 20 + 1 = 1OpenSection 23 12 + 3 = 51 + 2 = 3OpenSection 35 25 + 5 = 103 + 2 = 5Table 6 First conditionThe first condition fails because Bessies dizziness level exceeds her limit even though she got so much fun.Eyes ConditionLevel ofFunDizzinessInitial00CloseSection 12 100OpenSection 23 10 + 3 = 30 + 1 = 1OpenSection 35 23 + 5 = 81 + 2 = 3Table 7 Second conditionThe second condition also fails because her dizziness level exceeds her limit.Eyes ConditionLevel ofFunDizzinessInitial00OpenSection 12 10 + 2 = 20 + 1 = 1CloseSection 23 121 1 = 0OpenSection 35 25 + 2 = 70 + 2 = 2Table 8 Third conditionThe third co ndition is a triumph because of her dizziness level does not exceed her limit and she got so much fun.Eyes ConditionLevel ofFunDizzinessInitial00OpenSection 12 10 + 2 = 20 + 1 = 1OpenSection 23 12 + 3 = 51 + 1 = 2CloseSection 35 252 1 = 1Table 9 Fourth condition steady though this condition can be considered as a success because of Bessies dizziness level does not exceed her limit but the fun she got is not much.Eyes ConditionLevel ofFunDizzinessInitial00CloseSection 12 100CloseSection 23 100OpenSection 35 20 + 5 = 50 + 2 = 2Table 10 Fifth conditionEven though this condition can be considered as a success because of Bessies dizziness level does not exceed her limit but she does not have much fun.Eyes ConditionLevel ofFunDizzinessInitial00OpenSection 12 10 + 2 = 20 + 1 = 1CloseSection 23 121 1 = 0CloseSection 35 220Table 11 Sixth conditionEven though this condition can be considered as a success because of Bessies dizziness level does not exceed her limit but she does not have muc h fun.Eyes ConditionLevel ofFunDizzinessInitial00CloseSection 12 100OpenSection 23 10 + 3 = 30 + 1 = 1CloseSection 35 231 1 = 0Table 12 Seventh conditionEven though this condition can be considered as a success because Bessies dizziness level does not exceed her limit but she does not have much fun.Eyes ConditionLevel ofFunDizzinessInitial00CloseSection 12 100CloseSection 23 100CloseSection 35 200Table 13 Eighth conditionThis condition fails because Bessies does not have fun at all.Therefore, Table 8 which illustrates the third condition is the most optimal solution where it satisfies as the maximum amount of fun Bessie can have when riding a roller coaster without getting sick.Dynamic Programming0-1 KnapsacksThe key idea to solve this problem is by adapting the Knapsack solution in which total amount of dizziness as the total weight she carries in her sack without exceeding the given limit and maximum fun as the maximum total value carries in that sack. To obtain the most optimal solution, we have to select the most maximum of total fun. However, in selecting the maximum total fun, we need to consider the total amount of dizziness because if it exceeds the limit, Bessie will get sick and thus we should avoid it.References1 Knapsack Problem, http//en.m.wikipedia.org/wiki/Knapsack_problem2 Slide 4 in Dynamic Programming 1, CSC752 Advanced Algorithms Analysis, Syed Ahmad Aljunid.3 Brute Force Search, en.wikipedia.org/wiki/Brute-force_search4 Southeast Regionals 2010 Solutions, https//sites.google.com/site/ubcprogrammingteam/news