sauravUppoor's blog

By sauravUppoor, 4 years ago, In English

Hello!

Here is my approach for CF Round 647 Div2 D:

Traverse the blogs from 1 to n. Check the neighbours of current blog for:

  1. If topic of the neighbour and the topic of the current blog isn't same.

  2. Topic of the current blog is the smallest possible missing topic in the set of topics of neighbours.

Then if I pass both the condition for all the blogs, I go on to print the blog number in sorted order of topics.

My submission: https://codeforces.com/contest/1362/submission/82608827

Most probably I have missed a case where the answer doesn't exist. However, I am unable to find where I am going wrong.

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Your output for this test:

3 1

1 2

1 2 3

is:

1 2 3

which is wrong, because you cannot assign the topic $$$3$$$ to the blog $$$3$$$, because blog $$$3$$$ is alone, so the topic $$$1$$$ should be assigned to it.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thanks a lot for going through the solution and suggesting the case! I missed checking the condition for isolated vertices.