Editorial for Wesley's Anger Contest 2 Problem 5 - Oober Treats
Submitting an official solution before solving the problem yourself is a bannable offence.
First, consider the problem without any updates to the list. While there are many ways to interpret this problem, one way is to recognize that it is a variation of the bounded knapsack problem, which itself can be transformed into the 0-1 knapsack problem. Here, the weight of an item is the fuel for the route, and the value of an item is the cash earned for each repeated completion. Each item is duplicated times, such that each of the duplicated items represents the original item repeated times where is a distinct power of , such that the sum of for all of the duplicated items is equal to (there may need to be one item where is not a power of ). The standard 0-1 knapsack algorithm can then be performed. In order to deal with the different cash value earned for the first completion, we can solve the bounded knapsack problem for items, and perform 0-1 knapsack on a single item. The maximum value for a weight for the first routes can be updated as usual, with the exception that the dynamic programming now becomes where is the maximum cash earned for the first routes using at most fuel, and is the maximum cash earned for the first items and completing route up to times, each earning cash.
Side Note: Bounded knapsack can be performed in time. There is a method that can solve this in time, however it is unnecessary for this problem.
To solve the problem with updates, we can see that the versions of the app form a rooted directed tree, where the vertices are the versions of the app, and the edges are from the old version to the new version of the app. If we treat each update as a removal of an item, followed by an addition of an item to the knapsack, we can flatten the tree into an Euler Tour, to have a linear progression of changes.
Observe that we can undo the addition of the most recent item to the knapsack easily by removing the last row of the dynamic programming. Thus, if there is some reorganization of the ordering of the removals and additions, then the problem can be solved more easily. We can use a divide and conquer approach to reorder the addition of items. We can treat an item as being active for a certain interval of time. For a time interval of with , we can first add to the knapsack all items which have one endpoint of its interval in the range . Since we know these items will not be modified in the range , we can recursively solve the problem in the range . Afterwards, we can undo the additions of those items, and repeat the same process for the range . The base case is when , where we can simply retrieve the answer for whatever items are currently in the knapsack (we can treat the queries as a separate event).
Instead of using divide and conquer, we can group the events from the Euler Tour together in groups of size . We will answer the queries in each group together. first add items to the knapsack that are not modified in the group. For each query, the items that are modified can then be added to the knapsack one by one, and then removed after each query. This method takes slightly longer than the divide and conquer method and may require optimizations to fit within the time limit.