A. Cluster Analysis
Author: Suhendry Effendy.
Prepared by: Suhendry Effendy, Felix Halim.
Problem: A – Cluster Analysis
This is the easiest problem in the contest.
The low constraint (N ≤ 100) allows contestant to solve this problem using less efficient solutions. For example, you can construct a boolean N x N matrix where element (i, j) denotes whether ith and jth elements differ by at most K. Then you can employ disjoint set data structure and join each true element in the matrix to create the clusters. Alternatively, you can employ graph traversal algorithm (e.g., BFS or DFS) to calculate the number of clusters.
All the methods I mentioned previously are overkill (I know several teams using those methods).
There is an easy O(N lg N) solution to the problem:
- Sort all integers in array A, let’s call the sorted A as A’;
- Count how many adjacent elements in array A’ (A’i and A’i+1) s.t. the difference is more than K, let this value be X;
- The output is X + 1.