主要是為了跪拜 solution 3 所以打一下..
Problem: imagine there is an undirected graph
G. Implement an adversary oracle, that opponent queries hasEdge(x, y) and you returns true/false. Goal: opponent cannot figure out whether
G is connected using less than C(|V|, 2) queries. |V| ≤ 2500
Solution 1: idea: return false unless
G will be disconnected eventually (even if all unqueried edge presents). Naive implementation O(n
4). One can view as starting from a complete graph, and support operations:
- addEdge(x, y)
- removeEdge(x, y)
- queryConnect(x, y)
which is the
Dynnamic Connectivity Problem. From
here, it can be done in O(polylog n) which may not fast enough and probably coding-infeasible for IOI.
Solution 2: idea: relax the constraints for returning true. Assume there are several components in the graph currently. For every two components we will have an edge connecting them directly, but only reveal it when opponent queried all pairs of vertices from that two components. Implementation: maintain a counter for every pair of components. Merging components takes O(n) to update the counters, but we only do merge operation n-1 times so in total O(n
2).
Solution 3: for query hasEdge(x, y), wlog x < y, 0-based, increase cnt[y] by 1. Return yes if and only if cnt[y] reaches y.
Intuitive explanation: eventually every vertex (except 0) will has 1 edge to a smaller label vertex, forming a tree. Also for this tree to be formed, C(|V|, 2) queries is required.
References:
live video feed.
