CLANDLBL - Editorial

clandlbl
editorial
feb18
isomorphism
medium-hard
number-theory

#1

PROBLEM LINK:

Practice
Contest

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) e l(v) for u e 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 ext{ 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*[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*[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*[j]
        consistent = false
    if consistent then dfs(i+1)

ALTERNATIVE SOLUTION:

Please feel free to share your approaches :slight_smile:

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.


#2

I followed the tester approach during contest, though my solution is not correct. I am missing the n! prunning part. Here is my solution . Can you suggest how can I improve this solution??


#3

i also followed the tester’s approach during the contest but my solution failed 3 and 4th test cases i dnt know why , plz help my solution is https://www.codechef.com/viewsolution/17285624 ??


#4

Firstly the common divisor count cannot exceed 24. Now , all the elements of the rows from 1 to N can be computed (i.e all the values for 1 can be computed by calculating its common divisor count with 2,3,4,…N. Similarly for 2 to N also). Let us store these in vector v[1005]. Now see the first row of the input. Any of the values from the vector set which after sorting matches with the first row can be set as a label to 1st node(It can be proved). Now scan the next row, if suppose it matches with another label from the vector v , Now just check if after setting this label the given values of the matrix match with the values we have set till now. This does the task in O(NNlogN).


#5

what i did was for every node, i created a multiset which contain values of edges connected to it. And stored the multiset in map<multiset,set> which contain set of nodes having same edge values. And then assign values to nodes according to previously assigned nodes values and remove them from map.
here is my solution https://www.codechef.com/viewsolution/17344622
But i think is more than O(n^2) in worst case, so maybe problem had weak test cases.
@r_64 any idea how it passed the time limit?.


#6

My method was greedy.

I created the matrix cosidering the permutation 1,2,3,…n. Then sorted each row and created a frequency map of these sorted arrays(n of them)(also stored the indices(1,3,4)).Now lets say they gave me the matrix og,i copy it into matrix temp.Now for each row of temp,i sort it .Now after sorting ,if its frequency in frequency map is 1 then we can be sure what this row should be. The problem comes when the frequency is greater than 1.So for this u could start from the array in increasing order of its occurrence,and accordingly assign.

Note:One important thing is that u can interchange the rows which have all 1’s(not considering a[x][x]),and that for n=1000 number of rows that have a frequency of 1 is around 535,so since half of the permutation is known,there’s no way that now two repeating rows can have same values at this permutation(Though cant prove it,would be glad if someone could prove me wrong(as i too am a bit unsure))

My solution:
https://www.codechef.com/viewsolution/17393465


#7

What do you mean by after sorting?Is it after sorting v vector or sorting the individual row of each entry in vector?Can you please elaborate it and please give the code.


#8

The answer wasn’t fitting in one comment so I broke it down into two parts.
Part 1
By sorting I meant individual rows of the vector. Let me explain by an example.Suppose N= 4 and consider the sample case.
0 1 1 1
1 0 1 1
1 1 0 2
1 1 2 0
Since N=4 we store in v[1] - common divisors of 1 with 1,2,3,4 , v[2] will store common divisors of 2 with 1,2,3,4. Now one by one we have to assign labels to v[1],v[2],…v[N]. So start with v[1]. See the input row with which it matches and assign that row number to node 1.


#9

Next when we assign value to node 2 i.e when we see v[2] we match the row with the input row,see if this shouldn’t be any previously used row.We will also have to check one additional thing…whether the label that we assign to the current node is consistent with the previously assigned labels. For ex if we are assigning node number 3 the label X and suppose we have assigned node 1 the label 7 and node 2 the label 47…so here we will have to check whether number of common factors of(7,X)=a[1][3] and similarly for node 2 and 3.If this condition fails then dont pick X, just continue the loop.


#10

link to my code - https://www.codechef.com/viewsolution/17395170


#11

my solution is the same.I also felt that it was kinda N^3 but a lot of break statements allowed it to pass.Also the complexity could have been reduced to 24NN by instead of matching every element in the subset match the fequencies of each element from 0 to 24…essentialy multiset is doing the same thing but in O(N) time.