ACM ICPC Regional Problem

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, 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 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_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]

Link:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=410&page=show_problem&problem=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:

1. The roller coaster has a distinct number of sections that Bessie rides in order.
2. Bessie’s fun and dizziness levels are both at 0 at the beginning of the ride.
3. 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.
4. 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. *
5. 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. *
6. Bessie’s dizziness can never go below 0.
7. Bessie will get sick if her dizziness is above a given limit. *

* – Tricky constraint.

The parameters for this problem are listed as below:

1. N (1 ≤ N ≤ 1000), the number of sections in a particular roller coaster.
2. 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.
3. L (1 ≤ L ≤ 300,000), limit of dizziness that Bessie can stand.
4. F (1 ≤ F ≤ 20), the increases to Bessie’s total fun if she keeps her eyes open on that section.
5. D (1 ≤ D ≤ 500), the increases to her dizziness level if she keeps her eyes open on that section.
6. 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:

1. The item in this problem consists of Bessie’s dizziness level (weight) and fun level (value).
2. Her dizziness is how much she can carries in her sack (total weight of the items she carries in the sack).
3. Her fun is what she would like to maximize (total value of the items she carries).
4. 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:

1. The number of sections in a particular roller coaster.
2. The amount that Bessie’s dizziness level will be subtracted if she keeps her eyes closed on any section of the ride.
3. The limit of dizziness that Bessie can stand.
4. The increases to Bessie’s total fun if she keeps her eyes open on that section.
5. The increases to her dizziness level if she keeps her eyes open on that section.
6. 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,

1. the number of sections in a particular roller coaster = N, where N ≥ 1 and N ≤ 1000,
2. 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,
3. the limit of dizziness that Bessie can stand = L, where L ≥ 1 and L ≤ 300000,
4. the increases to Bessie’s total fun if she keeps her eyes open on that section = F, where F ≥ 1 and F ≤ 20,
5. the increases to her dizziness level if she keeps her eyes open on that section = D, where D ≥ 1 and D ≤ 500, and
6. 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 [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)

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.

Table 2Optimal solution for test case 1 from sample input Roller Coaster problem

Test Case 2 (New input and output)

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.

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.

Get Help With Your Essay

If you need assistance with writing your essay, our professional essay writing service is here to help!

Essay Writing Service

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.

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.

Table 6: First condition

The first condition fails because Bessie’s dizziness level exceeds her limit even though she got so much fun.

Table 7: Second condition

The second condition also fails because her dizziness level exceeds her limit.

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.

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.

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.

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.

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.

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