## Sunday, November 23, 2014

### Codeforces Round 278 (Div.1) Problem B. Strip

Problem Statement:
478B - Strip

Solution:
This is a very interesting problem, and the official editorial for the round is already very well written :D So I'll just provide an implementation of the solution using monotonic queue (cool stuff). The DP idea is pretty simple: If f[i] is the minimum number of pieces needed to divide elements in [1..i], and g[i] is the left-most index such that [g[i]..i] is a valid piece, then f[i] is the minimum of f[j] + 1 for all $$j \in$$ [g[i] .. (i-L)]. Well implementing this alone will leave us with an at least $$O(N^2)$$ solution to compute each f[i], and that is already TLE. So the smart thing to do is to keep track of the maximum and minimum element between two index j and i while updating g[i] and f[i]. This can be done efficiently using monotonic queue / sliding window minimum data structure with $$O(N)$$ running time, or can be achieved by simply using a multiset which will give us an $$O(N\lg{N})$$ solution in the end. Here I used monotonic queue to solve the problem.

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

deque<pair<long long, int> > dmin, dmax;
long long f[100004];
int a[100004], g[100004];
int N, S, L;
int main(){
scanf("%d %d %d", &N, &S, &L);
for(int i=0;i<N;++i){
scanf("%d", &a[i]);
}
int tail = 0;
dmin.push_back(make_pair(a[0],0));
dmax.push_back(make_pair(a[0],0));
g[0] = 0;
for(int i=1;i<N;++i){
while (!dmin.empty() && dmin.back().first >= a[i]) {
dmin.pop_back();
}
dmin.push_back(make_pair(a[i],i));
while(!dmax.empty() && dmax.back().first <= a[i]) {
dmax.pop_back();
}
dmax.push_back(make_pair(a[i],i));
while(!dmax.empty() && !dmin.empty() && (long long)(dmax.front().first - dmin.front().first) > (long long)S) {
++tail;
if(dmax.front().second < tail) dmax.pop_front();
if(dmin.front().second < tail) dmin.pop_front();
}
g[i] = tail;
}
dmin = deque<pair<long long,int> > ();
for(int i=0;i<L;++i){
f[i] = 12345678;
}
if(L - g[L-1] >= L) f[L-1] = 1;
else {
printf("-1\n");
return 0;
}
dmin.push_back(make_pair(0,-1));
for(int i=L;i<N;++i){
f[i] = 12345678;
while(!dmin.empty() && dmin.back().first >= f[i-L]){
dmin.pop_back();
}
dmin.push_back(make_pair(f[i-L],i-L));
while(!dmin.empty() && dmin.front().second < g[i]-1){
dmin.pop_front();
}
if(!dmin.empty()) f[i] = dmin.front().first + 1;
}
if(f[N-1] < (long long)12345678) cout << f[N-1] << endl;
else printf("-1\n");
return 0;
}