Codeforces Good Bye 2014 Problem F - New Year Shopping

Problem Statement
500F - New Year Shopping

Solution:
A pretty tough problem which solution employs a very clever divide and conquer strategy. Learnt cool stuff :D.

Let's suppose that all the items are already sorted by \(t_i\) in increasing order. We know that item i will be available in the time segment \([t_i,t_i+p-1]\). Suppose that for each time \(T\), we know which are the segments that contain \(T\), i.e. the set of i such that \(T \in [t_i,t_i+p-1]\).

a bit of dp: Notes on 0-1 Knapsack

DP Table = array[i][W]
Value Table = p[i]
Weight Table = w[i]
Total element = max_i
Restriction on Knapsack = max_w

Recursive Relationship (Sequential passing of element i):
\(S(i, W) = max \{S(i-1, W), p[i] + S(i-1, W-w[i]) \} \) (Starting at S(max_i, max_w) ) or
\(S(i, W) = max \{S(i+1, W), p[i] + S(i+1, W+w[i] \} \) (Starting at S(0,0) and limited by max_i & max_w)

Bottom-up (Incremental addition of element i):
Firstly, \(S(i,0) = 0\) and \(S(0,W)=0\) for all \(i,W\).
For i = 1 to max_i,
    For W = 1 to max_w,
        S(i,W) = max( S(i-1, W), S(i-1, W - w[i]) + p[i] ) (Direct translation of recursion!)

a bit of codechef: (June Cook-Off 2014) Knapsack Problem

Problem Statement:
(June Cook-Off 2014) Knapsack Problem

Summary:
Given \(3\leq N \geq 100000\) items with weights \(1\leq w_i \leq 2\) and costs \(1\leq c_i \leq 10^9\), output maximum costs of each \(M\) from 1 to total sum of all weights.

Solution:
At first it seems like the problem can be solved by normal Knapsack DP problems, with the recursion \(S(w) = \max_{w_i \in W} \{S(w-w_i) + c_i\} \), but \(N\) and hence \(M\) is too big for this to finish quickly enough. There are also only 2 value for weights. This suggests a more specialized algorithm to output all costs in the most efficient manner.

For me this is a very interesting problem, and the following observation is the key to solving it:
1. Given \(M\), we can try all \(m\) and \(n\) such that \(2m+n \leq M\). Furthermore, given \(m\) and \(n\),  the maximum cost would be to choose \(m\) items of biggest cost with weight equals to 2, and \(n\) items of biggest cost with weight 1. Now we only need a way to choose combination of \(m\) and \(n\) effectively, and therefore the second observation:
2. Given \(m,n\) which optimizes the cost when the total weight is \(M\), we can find \(m',n'\) of \(M+1\) by taking the maximum of either \(m+1,n\) or \(m,n+1\) (we also have to ensure that the resulting \(m'\) and \(n'\) does not exceed the total 2s and 1s, or else maximum cost of \(M+1\) is equal to \(M\)

The two observations above are enough for us to develop a bottom-up DP by storing the combination of \(m,n\) for each \(M\).