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]\).



The most important observation to make here is that if we take \(T = 1, 1+p, 1+2p, 1+3p, \ldots\) (i.e each subsequent Ts differ by p\), we will have all the segments divided into disjoint sets. That means we can employ a divide and conquer strategy! How? For each such T, suppose the items that appears at time T is in [i..j]. We run a knapsack algorithm for all possible budgets twice on these items, first in i to j direction, and another one is from j to i direction. Store them in two tables S[b][k] and R[b][k] respectively, where b represents the budget, while k tells us how much of the items are being considered (that means items [i..i+k-1] for S and items [j-k+1..j] for R).

Since each items belong to only one value of T, in total we need \(O(nB)\) time to compute R and S.

Finally, to compute the desired maximum happiness in each query (\(a_i\),\(b_i\)), we iterate through all possible distribution of budget b into the relevant S and R and take the maximum.

Since each query is answered in \(O(B)\) time, in total we need \(O(qB)\) to serve the queries. Such a nice technique.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
#include <cstring>
using namespace std;

int N,P;
int val[4003], cost[4003];
int h[4003], c[4003], t[4003];
int len[20003];         // height of the segment stack
int f[20003];           // index of upmost segment
int up[4003][4003];
int down[4003][4003];
vector<pair<int,int> > st;

int main(){
    int u,v,w;
    scanf("%d%d", &N, &P);
    for(int i=0;i<N;++i){
        scanf("%d%d%d", &u,&v,&w);
        cost[i] = u;
        val[i] = v;
        st.push_back(make_pair(w,i));
    }
    sort(st.begin(),st.end());
    memset(f, -1, sizeof f);
    for(int i=0;i<N;++i){
        len[st[i].first]++;
        len[st[i].first+P]--;
        h[i] = val[st[i].second];
        c[i] = cost[st[i].second];
        t[i] = st[i].first;
        f[st[i].first] = i;
    }
    for(int i=0;i<N;++i){
    }
    for(int i=1;i<=20000;++i) {
        len[i] += len[i-1];
        f[i] = (f[i] == -1 && len[i]!=0 ? f[i-1] : f[i]);
    }
    for(int T=1;T<=20000;T+=P){
        if(f[T]==-1)continue;
        for(int b=0;b<=4000;++b){
            for(int i=f[T];i>f[T]-len[T];--i){
                if(b-c[i]>=0){
                    if(i==f[T])up[b][i] = max(up[b][i], h[i]);
                    else up[b][i] = max(up[b][i], up[b-c[i]][i+1]+h[i]);
                }
                if(i<f[T]) up[b][i] = max(up[b][i], up[b][i+1]);
            }
            for(int i=f[T]-len[T]+1;i<=f[T];++i){
                if(b-c[i]>=0){
                    if(i==f[T]-len[T]+1)down[b][i] = max(down[b][i], h[i]);
                    else down[b][i] = max(down[b][i], down[b-c[i]][i-1]+h[i]);
                }
                if(i>f[T]-len[T]+1)down[b][i] = max(down[b][i],down[b][i-1]);
            }
        }
    }
    int Q;
    scanf("%d", &Q);
    for(int qq=0;qq<Q;++qq){
        scanf("%d%d", &u,&v);
        int prev = ((u-1)/P)*P+1;
        int ans = 0;
        if(len[u]>0){
            for(int b=0;b<=v;++b){
                int tmp = 0;
                if(f[prev]>=f[u]-len[u]+1)tmp+=up[b][f[u]-len[u]+1];
                if(f[prev]<f[u])tmp+=down[v-b][f[u]];
                ans = max(ans,tmp);
                
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}