题意:
what is the largest value of k such that there is a k-clustering with spacing at least 3? That is, how many clusters are needed to ensure that no pair of nodes with all but 2 bits in common get split into different clusters?
即, 海明距离小于等于 2 的所有点要被聚集到一个 cluster 中
输入:
[first bit of node 1] … [last bit of node 1]
[first bit of node 2] … [last bit of node 2]
For example, the third line of the file “0 1 1 0 0 1 1 0 0 1 0 1 1 1 1 1 1 0 1 0 1 1 0 1″ denotes the 24 bits associated with node #2.
输出:
what is the largest value of k such that there is a k-clustering with spacing at least 3? That is, how many clusters are needed to ensure that no pair of nodes with all but 2 bits in common get split into different clusters?
思路:
1. 将所有的点放入 hashtable 中
2. 遍历 hash table 中的所有点 p, 分别找出与 p 海明距离为 0, 1, 2 的点, 并将其合并
细节:
1. 实现 hash table 的数据结构式 unordered_multimap
2. 寻找与某点 p 海明距离为 0 的点, 通过hash table 可以在 o(1) 的时间内完成, 这是本题的基础
3. 寻找与某点 p hash 距离为 1 的点, 相当于把 p 的某一位翻转变成 p’, 然后找出与 p’ 海明距离为 1 的点
4. 海明距离为 2 同理
5. 用到带路径压缩的并查集
Submit original work, copying violates the class Honor Code