By Lindsey L. (11th Grade)
ICPC 2017 NWERC Problem I Installing Apps
https://qoj.ac/problem/2640 12/23/25
Concepts: greedy, dp
Since n <= 500 and c <= 10^4, we can do an O(nc) solution.
If we sort the values optimally and then do a knapsack dp, we can find the answer.
We can observe that we should sort by s – d in decreasing order, which is the amount of disk space left after choosing an app to download. This is optimal because we want to leave a greater amount of disk space remaining so there are more future apps to choose from.
We can do a dp[first i apps][space left] and initialize everything to -1e9 and dp[0][c] to 0. For each transition, we loop through all c possible values of disk space. We set the dp value to the maximum of taking the current app if possible or not taking it. The final answer will be the maximum of dp[n][i] for all i from 0 to c.
Since the problem also asks us to output the indexes of apps downloaded, we need to store which apps we have chosen at each step using another array. If at dp[i][j], choosing to take the current app is more optimal than not taking it, we can mark that we chose this app. After the dp, we need to reconstruct our answer by starting at the end and going backwards. We loop through the n apps backwards, keeping track of the disk space, and if we see that we have chosen the app, we can add it to our answer and update the disk space. Finally, we have to print out our answer in reverse since we found the indexes in reverse.
