You are not logged in. Please login at www.codechef.com to post your questions!

×

CLANDLBL - Editorial

0
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)\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

View Content

TESTER'S SOLUTION

View Content

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.

This question is marked "community wiki".

asked 27 Jan, 14:08

r_64's gravatar image

7★r_64
261822
accept rate: 16%

edited 12 Feb, 15:51

admin's gravatar image

0★admin ♦♦
19.0k348495531


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 ??

link

answered 12 Feb, 18:06

mritunjay07's gravatar image

3★mritunjay07
111
accept rate: 0%

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

link

answered 12 Feb, 18:18

abx_2109's gravatar image

5★abx_2109
275111
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, 15:38) coolrohan1234★

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) abx_21095★

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) abx_21095★
(14 Feb, 02:02) abx_21095★

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.

link

answered 07 Feb, 16:23

admin's gravatar image

0★admin ♦♦
19.0k348495531
accept rate: 37%

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??

link

answered 12 Feb, 15:53

coolrohan123's gravatar image

4★coolrohan123
562
accept rate: 9%

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

link

answered 13 Feb, 21:45

akash_321's gravatar image

4★akash_321
665
accept rate: 0%

edited 13 Feb, 21:47

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) abx_21095★

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

link

answered 14 Feb, 22:14

vivek_1998299's gravatar image

6★vivek_1998299
1.3k29
accept rate: 23%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×14,366
×1,089
×529
×232
×13
×2

question asked: 27 Jan, 14:08

question was seen: 1,475 times

last updated: 14 Feb, 22:14