PROBLEM LINK:
Author: Kamran Maharov
Tester: Hanlin Ren
Editorialist: Hanlin Ren
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Number Theory, Graph, constructive algorithm, graph isomorphism
PROBLEM:
Given an undirected complete graph G of n vertices where each edge has a weight w(u,v), assign each vertex a label such that for any edge (u,v), w(u,v)=common\_divisor\_count(l(u),l(v)), where l(u),l(v) are labels of u,v, respectively, and common\_divisor\_count(l(u),l(v)) is the number of common divisors of l(u) and l(v). The label should be a permutation of 1\sim n, i.e. 1\le l(u)\le n and l(u)\ne l(v) for u\ne v.
QUICK EXPLANATION:
This editorial contains two solutions:
- Setter’s solution. Firstly we assign prime labels. The neighbor of a prime p has (\lfloor n/p\rfloor-1) 2’s and (n-\lfloor n/p\rfloor) 1’s, and we (roughly) use this information to assign prime labels. Then we assign labels which are prime powers (p^k). For some vertex u, if there’s only one v such that w(u,v) > 1 and v is labeled prime, then u is a prime power. At last, based on prime powers, we can label other numbers.
- Tester’s solution. This problem is a special case for graph isomorphism problem, so we can use heuristic algorithms. For every vertex, compute a hash of its neighboring edges. Then use this information to prune the O(n!) brute-force search.
SETTER’S SOLUTION
Click to view
This algorithm proceeds in three steps. Below we say u,v are connected if w(u,v)\ge 2.
Step 1: primes
In this step, we find all vertices that should be assigned prime labels, i.e. l(v)\in\{2,3,5,7,11,\dots\}.
Define seq(v) be the sorted sequence of incident weights of v. For example, when n=4 and l(v)=2, seq(v)=(0,1,1,2). If l(v)=p is a prime, then seq(v) only contains 0, 1 and 2. Moreover there should be exactly one zero and \lfloor n/p\rfloor-1 twos. The zero comes from M_{vv}, and the twos come from p's multiples.
But, if seq(v) consists of only 0,1 and 2, then is l(v) necessarily a prime? The answer turns out to be no: if l(v) is the product of two (not necessarily distinct) primes q\cdot r which satisfies 2qr>n, seq(v) also contains 0,1,2 only. For example:
- when n=100, seq(5)=seq(91), and both of them contain 19 twos;
- when n=25, seq(5)=seq(25), and both of them contain 4 twos.
In the above two cases, we say 5 has conflict with 91(25 resp.). An important observation is that, if p has conflict with qr, then \min(q,r)>p. Proof: seq(qr) has \lfloor n/q\rfloor+\lfloor n/r\rfloor-2 twos, which means \lfloor n/q\rfloor+\lfloor n/r\rfloor=\lfloor n/p\rfloor+1. If, say, q\ge p, then to make \lfloor n/r\rfloor\le 1, we have r > n/2. But in this case, qr>n, which is impossible. Therefore \min(q,r)>p.
Let’s enumerate the primes from large to small. Consider a prime p, suppose all primes in (p,n] have been assigned. We should find a vertex v whose seq(v)=(0,1,1,\dots,1,\underbrace{2,2,\dots,2}_{\lfloor n/p\rfloor-1\text{ 2's}}). However this doesn’t immediately mean l(v)=p since l(v) could also be a product of two primes QR. So we check if there’s some u connected to v such that l(u) is already marked by larger primes.
- If there is such u, then there should be exactly two such u, and l(v)=l(u_1)l(u_2). However it’s not necessary to assign a label to l(v) now. We look for another v with the desired seq(v).
- Otherwise we can mark l(v) as p.
Step 2: prime powers
Now we know the position of all prime labels. For a vertex v, it’s a prime power(p^k) if and only if it’s only connected with one prime. And if that prime is p, then l(v) must be a power of p. So we can enumerate prime p and find all vertices that should be labeled as a power of p by this method. Say they are v_1,v_2,\dots,v_t(t=\lfloor\log_p n\rfloor). Then which power should we assign to each v_i? We can decide this by considering “sum”: denote sum(v) as the sum of all numbers in seq(v). Then sum(p)\le sum(p^2)\le\dots\le sum(p^t). Moreover, if 2p^t\le n, then sum(p^{t-1}) < sum(p^t). (If 2p^t>n, then p^t and p^{t-1} are indistinguishable in the graph.) Therefore, we compute the $sum$s of v_1,v_2,\dots,v_t. The one with the smallest sum is p^2, the second smallest sum is p^3, and so on.
Step 3: all numbers
When we marked all prime powers, the rest is easy. For a vertex v, suppose u_1,u_2,\dots,u_k are the prime powers v connects to, then the label of v is just \mathrm{lcm}(l(u_1),l(u_2),\dots,l(u_k)).
Time complexity
This solution runs in O(n^2) time.
TESTER’S SOLUTION
Click to view
We first compute a matrix a[i][j]=common\_divisor\_count(i,j), and denote the input matrix by A. The rest to do is to find an isomorphism between a and A. An isomorphism, in this case, is defined as a permutation l of \{1,2,\dots,n\} such that a[l(i)][l(j)]=A[i][j] for all i,j. (Note: this l is equivalent to the l in Setter’s Solution)
There are many heuristics for graph isomorphism problems, and this problem can be solved by a simple one. For a matrix A and a number i, we compute a hash of A_i(the i-th row of A, sorted in ascending order), and denote this by h(A,i). We then use brute force to search a valid l, with some pruning based on the hash. For a valid l, h(a,l(i))=h(A,i) for any i. (Note that there’ll be some identical rows after sorting, so we can’t determine l only by h(a,l(i))=h(A,i), but need a brute-force search. One of such case is: when n=100, the rows corresponding to 5 and 91 are identical.) We use a map <hash_value, set <rows> > to store the set of rows in a that has a certain hash value. Then we use this to prune the brute-force:
dfs(i)
//we've determined l(1..i-1), and we're considering l(i)
for li in map(h(A,i)) //this means h(a,li)=h(A,i)
l(i) <- li
consistent = true
for j <- 1 to i-1
if a[l(i)][l(j)] != A[i][j]
consistent = false
if consistent then dfs(i+1)
ALTERNATIVE SOLUTION:
Please feel free to share your approaches 
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.