×

# CLANDLBL - Editorial

Author: Kamran Maharov
Tester: Hanlin Ren
Editorialist: Hanlin Ren

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.

View Content

View Content

# AUTHOR'S AND TESTER'S SOLUTIONS:

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

This question is marked "community wiki".

7★r_64
261924
accept rate: 16%

19.7k350498541

 1 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 ?? answered 12 Feb '18, 18:06 11●1 accept rate: 0%
 1 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). answered 12 Feb '18, 18:18 4★abx_2109 275●1●11 accept rate: 0% 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. (13 Feb '18, 15:38) 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. (13 Feb '18, 19:55) abx_21094★ 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. (13 Feb '18, 20:00) abx_21094★ link to my code - https://www.codechef.com/viewsolution/17395170 (14 Feb '18, 02:02) abx_21094★
 0 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?? answered 12 Feb '18, 15:53 56●2 accept rate: 9%
 0 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,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?. answered 13 Feb '18, 21:45 76●5 accept rate: 0% 1 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. (14 Feb '18, 14:20) abx_21094★
 0 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 answered 14 Feb '18, 22:14 1.6k●2●9 accept rate: 23%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,498
×1,237
×626
×233
×13
×2

question asked: 27 Jan '18, 14:08

question was seen: 1,651 times

last updated: 14 Feb '18, 22:14