## Thursday, January 1, 2015

### 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;
}