ACM ICPC Regional Problem

ACM ICPC Regional Problem Siti Nazihah Binti Sarpin (L) Nurul Aini Binti Mohd Hisan Table of Contents (Jump to) Introduction Problem Description Problem Statistics Problem Details ACM ICPC Regional Problem Reason to Choose This Problem Preliminary Analysis Mathematical Modeling Test Case 1 (Sample input and output from the problem) Test Case 2 (New input and output) Possible Algorithm Design Technique Brute Force Dynamic Programming 0-1 Knapsacks References Introduction Problem Description Bessie has gone on a trip, and she’s riding a roller coaster! Bessie really 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 dizziness and fun levels are both at 0. For each section of the roller coaster, Bessie can either keep her eyes open or keep them closed (and must keep them that way for the whole section). If she keeps her eyes open for a section, her total fun increases by a Fun factor for that section, and her dizziness increases by a Dizziness factor for that section. However, if she keeps her eyes closed for the section, her total fun will not change, but her dizziness will decrease by a value that’s constant for the entire roller coaster. (Note that her dizziness can never go below 0.) If, at any point, Bessies dizziness is above a certain limit, Bessie will get sick. Write a program to find the maximum amount of fun Bessie can have without getting sick. Input There will be several test cases in the input. Each test case will begin with a line with three integers: N K L Where N (1 ≠¤ N ≠¤ 1,000) is the number of sections in this particular roller coaster, K (1 ≠¤ K ≠¤ 500) is the amount that Bessie’s dizziness 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 that’s not fun! Each of the next N lines will describe a section of the roller coaster, and will have two integers: F D Where F (1 ≠¤ F ≠¤ 20) is the increase to Bessie’s total fun that she’ll 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. Output For each test case, output a single integer, representing the maximum amount 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 Input 3 1 2 2 1 3 1 5 2 10 5 1 20 2 12 4 3 3 10 6 20 3 19 9 19 7 1 500 15 5 4 2 0 0 0 Sample Output 7 0 Problem Statistics According to ACM-ICPC archive website, the total submission of this problem 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 Details ACM ICPC Regional Problem Region: ACM ICPC Regionals 2010 North America Southeast USA Year: 2010 Problem: H, 4870 – Roller Coaster [4.500 seconds] Link:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudgeItemid=8category=410page=show_problemproblem=2871 Source Code: https://github.com/depstein/programming-competitions/blob/master/problems/04-10-14%20intro/4870%20(Roller%20Coaster)/rollercoaster.java Programmer: N/A. Reason to Choose This Problem This 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 Knapsack problem which require us to find the maximum amount of fun can Bessie have without making her sick. Preliminary Analysis This problem is to obtain the maximum amount of fun Bessie can have when riding a roller coaster without getting sick, in which case without exceeding her dizziness limit. The constraints of the problem include: The roller coaster has a distinct number of sections that Bessie rides in order. Bessie’s 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 total 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. * Bessie’s 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 below: N (1 ≠¤ N ≠¤ 1000), the number of sections in a particular roller coaster. K (1 ≠¤ K ≠¤ 500), the amount that Bessie’s 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 Bessie’s 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 fixed command line for stopping the test cases. 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 items 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 solution: The item in this problem consists of Bessie’s 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 remain 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 many 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 stored in tables and can be used 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 force algorithm. Mathematical Modeling Input: The number of sections in a particular roller coaster. The amount that Bessie’s 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 Bessie’s 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. Output: 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 Bessie’s 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 Bessie’s 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, and the 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 Bessie’s eyes’ condition (either open or close), it will affect each of the total fun and total dizziness. Hence, FOpen = F + F[fun at nth section], DOpen = D + D[dizzy at nth section], FClose = F[fun at nth section], DClose = D[dizzy at nth section] K, where FOpen, DOpen, FClose, DClose N. Thus a solution for the problem is to find the minimum dizziness Bessie could have with the maximum fun [4]. DP[N][F] is the minimum dizziness Bessie can have, with fun = F. DP[N][F] = max(DP[N 1][F (fun at the nth section)] + (dizziness at the nth section), DP[N 1][F] K). First table is to store the section’s 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 Fun[N]]. 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 to get the new result for the new section. Test Case 1 (Sample input and output from the problem) Sample input Sample output 3 1 2 2 1 3 1 5 2 7 Table 1 Sample input and output of test case 1 Table 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 Bessie’s 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. Eyes’ Condition Level of Fun Dizziness Initial 0 0 Open Section 1 2 1 0 + 2 = 2 0 + 1 = 1 Close Section 2 3 1 2 1 – 1 = 0 Open Section 3 5 2 5 + 2 = 7 0 + 2 = 2 Table 2Optimal solution for test case 1 from sample input Roller Coaster problem Test Case 2 (New input and output) Input Output 12 3 8 5 4 3 2 8 2 6 1 12 5 18 2 12 3 10 4 15 2 16 5 10 3 6 1 80 Table 3 input and output from test case 2 This roller coaster track has a total of 12 sections, the amount that Bessie’s 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’ Condition Level of Fun Dizziness Initial 0 0 Open Section 1 5 4 0 + 5 = 5 0 + 4 = 4 Close Section 2 3 2 5 4 3 = 1 Open Section 3 8 2 5 + 8 = 13 1 + 2 = 3 Open Section 4 6 1 13 + 6 = 19 3 + 1 = 4 Close Section 5 12 5 19 4 – 3 = 1 Open Section 6 18 2 19 + 18 = 37 1 + 2 = 3 Open Section 7 12 3 37 + 12 = 49 3 + 3 = 6 Close Section 8 10 4 49 6 – 3 = 3 Open Section 9 15 2 49 + 15 = 64 3 + 2 = 5 Close Section 10 16 5 64 5 – 3 = 2 Open Section 11 10 3 64 + 10 = 74 2 + 3 = 5 Open Section 12 6 1 74 + 6 = 80 5 + 1 = 6 Table 4: An example of input for Roller Coaster problem Possible Algorithm Design Technique Roller 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 produce 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 Force Brute force technique is not recommended to solve this problem because it will result in an exponential solution [3] as we have to modify the condition (either Bessie’s 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. Let’s take sample test case 1 as an example shown in Table 1. 3 1 2 2 1 3 1 5 2 3 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 problem Brute force algorithm will test all the possibilities of Bessie’s eyes condition, either she had her eyes opened or closed. Eyes’ Condition Level of Fun Dizziness Initial 0 0 Open Section 1 2 1 0 + 2 = 2 0 + 1 = 1 Open Section 2 3 1 2 + 3 = 5 1 + 2 = 3 Open Section 3 5 2 5 + 5 = 10 3 + 2 = 5 Table 6: First condition The first condition fails because Bessie’s dizziness level exceeds her limit even though she got so much fun. Eyes’ Condition Level of Fun Dizziness Initial 0 0 Close Section 1 2 1 0 0 Open Section 2 3 1 0 + 3 = 3 0 + 1 = 1 Open Section 3 5 2 3 + 5 = 8 1 + 2 = 3 Table 7: Second condition The second condition also fails because her dizziness level exceeds her limit. Eyes’ Condition Level of Fun Dizziness Initial 0 0 Open Section 1 2 1 0 + 2 = 2 0 + 1 = 1 Close Section 2 3 1 2 1 – 1 = 0 Open Section 3 5 2 5 + 2 = 7 0 + 2 = 2 Table 8: Third condition The third condition is a success because of her dizziness level does not exceed her limit and she got so much fun. Eyes’ Condition Level of Fun Dizziness Initial 0 0 Open Section 1 2 1 0 + 2 = 2 0 + 1 = 1 Open Section 2 3 1 2 + 3 = 5 1 + 1 = 2 Close Section 3 5 2 5 2 – 1 = 1 Table 9: Fourth condition Even though this condition can be considered as a success because of Bessie’s dizziness level does not exceed her limit but the fun she got is not much. Eyes’ Condition Level of Fun Dizziness Initial 0 0 Close Section 1 2 1 0 0 Close Section 2 3 1 0 0 Open Section 3 5 2 0 + 5 = 5 0 + 2 = 2 Table 10: Fifth condition Even though this condition can be considered as a success because of Bessie’s dizziness level does not exceed her limit but she does not have much fun. Eyes’ Condition Level of Fun Dizziness Initial 0 0 Open Section 1 2 1 0 + 2 = 2 0 + 1 = 1 Close Section 2 3 1 2 1 – 1 = 0 Close Section 3 5 2 2 0 Table 11: Sixth condition Even though this condition can be considered as a success because of Bessie’s dizziness level does not exceed her limit but she does not have much fun. Eyes’ Condition Level of Fun Dizziness Initial 0 0 Close Section 1 2 1 0 0 Open Section 2 3 1 0 + 3 = 3 0 + 1 = 1 Close Section 3 5 2 3 1 – 1 = 0 Table 12: Seventh condition Even though this condition can be considered as a success because Bessie’s dizziness level does not exceed her limit but she does not have much fun. Eyes’ Condition Level of Fun Dizziness Initial 0 0 Close Section 1 2 1 0 0 Close Section 2 3 1 0 0 Close Section 3 5 2 0 0 Table 13: Eighth condition This condition fails because Bessie’s 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 Programming 0-1 Knapsacks The 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. References [1] Knapsack Problem, http://en.m.wikipedia.org/wiki/Knapsack_problem [2] Slide #4 in Dynamic Programming 1, CSC752 Advanced Algorithms Analysis, Syed Ahmad Aljunid. [3] Brute Force Search, en.wikipedia.org/wiki/Brute-force_search [4] Southeast Regionals 2010 – Solutions, https://sites.google.com/site/ubcprogrammingteam/news