### 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.