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