Hi All,
I will be providing editorial for one of the problem from CF #151 today.
Link of Problem: http://codeforces.com/contest/246/problem/D
Problem Statement: All the nodes are given some color between [1-1e5]. Our task is to find one color having maximum different kind of neighbors. As per my approach, I though of making a map of 100000 size. What we can do is that on getting every edge, if both vertex has different color, we can put this in our map.
Now as we want lexicographical smallest value of vertex having same cardinality, we traverse our map in sorted order of vertexes. We simple pick the one with highest cardinality and lowest vertex number.
Hope code will resolve doubts in case you have.
Implementation:
Feel free to comment in case you are not able to follow up.
I will be providing editorial for one of the problem from CF #151 today.
Link of Problem: http://codeforces.com/contest/246/problem/D
Problem Statement: All the nodes are given some color between [1-1e5]. Our task is to find one color having maximum different kind of neighbors. As per my approach, I though of making a map of 100000 size. What we can do is that on getting every edge, if both vertex has different color, we can put this in our map.
Now as we want lexicographical smallest value of vertex having same cardinality, we traverse our map in sorted order of vertexes. We simple pick the one with highest cardinality and lowest vertex number.
Hope code will resolve doubts in case you have.
Implementation:
Feel free to comment in case you are not able to follow up.
No comments:
Post a Comment