CF527D Clique Problem

The clique problem is one of the most well-known NP-complete problems. Under some simplification it can be formulated as follows. Consider an undirected graph $ G $ . It is required to find a subset of vertices $ C $ of the maximum size such that any two of them are connected by an edge in graph $ G $ . Sounds simple, doesn't it? Nobody yet knows an algorithm that finds a solution to this problem in polynomial time of the size of the graph. However, as with many other NP-complete problems, the clique problem is easier if you consider a specific type of a graph. Consider $ n $ distinct points on a line. Let the $ i $ -th point have the coordinate $ x_{i} $ and weight $ w_{i} $ . Let's form graph $ G $ , whose vertices are these points and edges connect exactly the pairs of points $ (i,j) $ , such that the distance between them is not less than the sum of their weights, or more formally: $ |x_{i}-x_{j}|>=w_{i}+w_{j} $ . Find the size of the maximum clique in such graph.

N/A

N/A

If you happen to know how to solve this problem without using the specific properties of the graph formulated in the problem statement, then you are able to get a prize of one million dollars! The picture for the sample test.