## Thursday, March 19, 2015

### Codeforces Round 296 Div. 1 B / Div. 2 D - Clique Problem

Problem Statement:
528B - Clique Problem

Solution:
This problem is brilliantly crafted. I really enjoy solving this problem, as the ideas are really natural.

Firstly, we notice that we can sort the vertices by its x coordinates, and we hope that some nice property can be established. Indeed,  suppose v[i] = (x[i], w[i]) is an array of vertices in sorted order with respect to x, then let C[i] be the maximum size of a clique that can be formed by choosing amongst v[1], v[2], to v[i], with the added constraint that v[i] must be included in C[i]. Then we claim that:
C[i] = max (C[j] + 1) where j is less than i.
Why is this true? Consider a clique C[j] for which we have:
|x[i] - x[j]| = x[i] - x[j] $$\geq$$ w[i] + w[j].

Then for all v[k] in C[j], we know that:
|x[k] - x[j]| = x[j] - x[k] $$\geq$$ w[k] + w[j] is also true.

Combining them, we have :
x[i] -  x[k]  $$\geq$$ w[i] + w[k] + 2*w[j]
and hence we have |x[i] - x[k]| $$\geq$$ w[i] + w[k] for all k! This establishes our claim that if we can find C[j] such that v[j] and v[i] is connected by an edge, then for any v[k] in C[j], v[k] and v[i] is also connected by an edge.

Based on this relationship, we can already come up with an $$O(N^2)$$ dynamic programming approach. However, this will not pass the time limit and hence we must do better. In fact, we can use segment tree to push the time limit to $$O(N \lg{N} )$$!

The approach is as follows: Since there are N vertices, there will be also at most N different values for x[i] + w[i], call this V. If we define a compartment identified by its V values, then each vertices can be distributed into one compartment each, and there will be at most N compartments. We sort these compartments with respect to their V values. Lets call each compartment K[j], where K[j].V is its value, and K[j].val is the maximum C[i] for all v[i] that belongs to K[j]. At first, all K[j].val is equal to 0. Then do the following:
1. From i = 1 to N, we want to find maximum C[j] such that x[i] - x[j] $$\geq$$ w[i] + w[j].
2. Let d = x[i] - w[i], and V = x[j] + w[j]. We can rewrite the inequality as d $$\geq$$ V. Hence finding maximum C[j] is equivalent to finding the maximum K[j].val amongst all j such that d $$\geq$$ K[j].V
3. Use binary search to find the upper bound for j, call this U. Then we can use segment tree to find the maximum K[j].val in the range [1, U]. This will correspond the maximum C[j].
4. We know that v[i] resides in compartment K[x[i]+w[i]]. Hence, finally update K[x[i]+w[i]].val accordingly using maximum C[j] we computed earlier.

Implementation:

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

vector<pair<int,int> > point;
vector<pair<long long, int> > valstack;
int N;
long long val[200005];
int segtree[1000000];

int rmq(int p, int S, int T, int L, int R) {
if(S>T)return 0;
if(T<L || R<S)return -1;
if(S<=L && R<=T) return segtree[p];
int M = (L+R)/2;
int left = rmq(2*p, S, T, L, M);
int right = rmq(2*p+1, S, T, M+1, R);
return max(left, right);
}

void update(int p, int S, int L, int R, int val) {
if(S < L || R < S) return;
if(L == R && R == S) {
segtree[p] = max(segtree[p],val);
return;
}
int M = (L+R)/2;
update(2*p, S, L, M, val);
update(2*p+1, S, M+1, R, val);
segtree[p] = max(segtree[2*p], segtree[2*p+1]);
return;
}

//upperbound
int getIndex(long long V) {
int lo = 0, hi = N-1, mid;
while(lo <= hi) {
mid = (lo+hi)/2;
if(val[mid] <= V) {
lo = mid+1;
} else {
hi = mid-1;
}
}
if(lo == N || val[lo] > V) lo--;
return lo;
}

void solve() {
sort(point.begin(), point.end());

for(int i=0;i<N;++i){
val[i] = point[i].first+point[i].second;
valstack.push_back(make_pair(val[i], i));
}
sort(valstack.begin(), valstack.end());
for(int i=0;i<N;++i){
val[i] = valstack[i].first;
}
for(int i=0;i<1000000;++i){
segtree[i] = 0;
}
int ans = 0;
for(int i=0;i<N;++i){
long long d = point[i].first - point[i].second;
long long v = point[i].first + point[i].second;
int left = getIndex(d);
int idx = getIndex(v);
int prev = rmq(1, 0, left, 0, N-1);
update(1, idx, 0, N-1, prev+1);
ans = max(prev+1, ans);
}
printf("%d\n",ans);
}

int main(){
scanf("%d",&N);
int x, w;
for(int i=0;i<N;++i){
scanf("%d%d",&x,&w);
point.push_back(make_pair(x,w));
}
solve();
return 0;
}