PROBLEM LINK:Author: Kamran Maharov DIFFICULTY:MEDIUMHARD 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 SOLUTIONTESTER'S SOLUTIONALTERNATIVE SOLUTION:Please feel free to share your approaches :) AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 27 Jan, 14:08

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:06

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<int> 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
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, 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, 19:55)
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, 20:00)
link to my code  https://www.codechef.com/viewsolution/17395170
(14 Feb, 02:02)

The step 1 and step 2 part can possibly be explained better. It requires a very careful reading (may be twice or more) to understand what each sentence means. I agree that this is a difficult problem and it requires quite an efforts to understand. If we can somehow improve it up, it'll be great. Otherwise, leaving it as it is fine too. answered 07 Feb, 16:23

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<int>,set<int>> 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, 21:45
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, 14:20)

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, 22:14
