CSC 454/654 - Spring 2021 - Programming Challenge 2

These programming challenge problems are part of Assignment 3 (see Canvas for written problems). Note that while a Java solution to both problems can run in a fraction of a second, it was hard to get a Python solution to run in a reasonable amount of time on some test cases. Therefore, the time limit on these challenges has been increased from 5 seconds to 15 seconds.

Problem 1 - RockBags (10 points)

A shopkeeper in ArachnidMan’s city has learned of your awesome algorithm design and programming skills, and has hired you to help decide how to package his shiny rocks for sale. While all the shiny rocks are identical, how they are grouped and packaged makes a huge difference. A bag with 8 rocks may be worth less than two bags of 4 rocks, since one bag with 8 rocks has the disadvantage of being very heavy. On the other hand, it might be worth more than two bags of 4 rocks, if people want 8 rocks but don’t want to mess with two different bags. This is all very unpredictable, so the “Shiny Rock Consortium” standardizes prices and publishes a list of the value of different size bags. This is provided in a text file, where the first line gives a value \(n\) with the maximum number of rocks that can be put in a bag, followed by \(n\) lines that give the value of a size 1 bag, size 2 bag, etc.

For example, if bags can hold up to 5 rocks, and a 1 rock bag is worth 5 dollars, a 2 rock bag is worth 10 dollars, a 3 rock bag is worth 15 dollars, a 4 rock bag is worth 16 dollars, and a 5 rock bag is worth 22 dollars, the input would look like this:

   5
   4
   10
   15
   16
   22

Your shopkeeper has exactly \(n\) shiny rocks, and wants to know how to divide them into bags to maximize his value. With the data above, he could put all 5 rocks in one bag (value 22 dollars), or could make two bags with two rocks and one bag with one rock (value 10+10+4=24 dollars). His best option, however, is one bag with two rocks and one bag with three rocks (value 10+15=25 dollars).

Your task is to write a program that reads this data (from standard input, as always), and prints out the maximum possible total value. So with he input given above, your program would print out “25”. Your program must be able to process inputs with up to 10,000 values, and run in less than 15 seconds.

Problem 2 - NumFalls (10 points)

ArachnidMan has a new sidekick, BlackFeline, who also has superpowers that charge up by falling, but in a slightly different way. BlackFeline makes a sequence of falling jumps, and gets one unit of “superpower charge” for each jump. It doesn’t matter how far the fall is, there’s one unit of charge for any fall. Every jump does have to go from left to right and it has to be a fall – BlackFeline can never jump to the left or to a position at the same level or higher.

Consider the same skyline as last time:

If BlackFeline starts at position 2 (height 7), jumps to position 3 (height 3), and then to position 5 (height 1), she gets 2 units of superpower charge. However, that’s not the best choice! She can start at position 2, jump to position 9, then to position 11, and finally to position 12. She doesn’t fall as far as the first scenario, but since there are 3 falls instead of 2, she gets 3 units of superpower charge from this possibility.

Your challenge is to write a program that reads a skyline input as described in the previous programming challenge, and calculate the largest possible superpower charge that BlackFeline can gain. The skyline can have up to 10,000 entries, and your solution must run in under 15 seconds. Output should consist of just the maximum charge, an integer on a single line, so with the sample scenario above your program should just print “3”.