ACM ICPC Regional Problem
4887 words (20 pages) Essay in Computer Science
22/06/18 Computer Science Reference this
Disclaimer: This work has been submitted by a student. This is not an example of the work produced by our Essay Writing Service. You can view samples of our professional work here.
Any opinions, findings, conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of UK Essays.


Table of Contents (Jump to)
Test Case 1 (Sample input and output from the problem)
Test Case 2 (New input and output)
Possible Algorithm Design Technique
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, Bessie’s 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, Bessie’s 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 ACMICPC 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_onlinejudge&Itemid=8&category=410&page=show_problem&problem=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]
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 01 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 01 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 subproblems [2], hence the Knapsack solution to this problem does not have to perform backtracking or recursion. This is because the previously solved subproblems are stored in tables and can be used again instead of recomputing 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 (D_{Total}) can never go below zero and must not exceed the given limit. Hence, D_{Total} ≥ 0 and D_{Total} ≤ L.
Moreover, depending on Bessie’s eyes’ condition (either open or close), it will affect each of the total fun and total dizziness. Hence,
F_{Open} = F + F[fun at nth section],
D_{Open} = D + D[dizzy at nth section],
F_{Close} = F[fun at nth section],
D_{Close} = D[dizzy at nth section] – K,
where F_{Open}, D_{Open}, F_{Close}, D_{Close} 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 [N1] [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 subproblem. 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 

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
01 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/Bruteforce_search
[4] Southeast Regionals 2010 – Solutions, https://sites.google.com/site/ubcprogrammingteam/news
If you need assistance with writing your essay, our professional essay writing service is here to help!
Find out moreCite This Work
To export a reference to this article please select a referencing style below:
Related Services
View allDMCA / Removal Request
If you are the original writer of this essay and no longer wish to have the essay published on the UK Essays website then please: