The_mysterio's blog

By The_mysterio, history, 2 months ago, In English,

Kindly help me with the solution of this problem https://codeforces.com/contest/1362/problem/D My solution https://codeforces.com/contest/1362/submission/82683708 Please help me to find out my error.It seems to me ,the statement *s.rbegin()!=s.size() is causing the problem but not finding any test case to understand why it should be wrong.. My algorithm is as follows... 1)check whether any two neighbouring vertices have same topic--->statement arr[i]==arr[u] does that where u is neighbour of i. 2)if not same,then I map the topic values given, to values starting from 1.So if the topic values avaialable are 2,4,5 then I map 2->1,4->2,5->3. The reason is I will be checking the condition as to whether there exists a topic number smaller than the topic number of current vertex being processed such that the current vertex has no edge to any other vertex having that smaller topic number. So,this mapping is stored in the mapping array. then I process each vertex and its adjacent vertices.The topics of the current vertex as well as the adjacent vertices are pushed into set s.Now if the above stated condition in the previous paragraph holds,then the last element of this set will obviously be not equal to size of the set.So we will be printing -1. Is there some misundrstanding here? Thanks in advance to anyone who will help this novice coder...

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

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

Hey, I have got a testcase where your code fails.

4 3
1 2
2 3
3 4
1 3 2 1

Your solution prints -1, but solution to this exists. 1 4 3 2 is one of the possible solutions. About the logic you trying to implement, your last element of set equals to size isn't correct. We don't need to make sure that, nodes connected to a given node are having continuous numbers, all we need to make sure is, we have all colors less than the current node we are checking.

Hope this makes sense !

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your reply. I actually thought that nodes should always be colored starting from 1. Kind of MEX function like stuff if you have done it. Coincidentally , I just solved this problem today....

    I would like you to advise me one thing. My intution is just not improving for CP problems. Unfortunately, I have been doing cp since 2017 but still no luck...

    I am practising everyday since April this year , almost 16 hrs.....only 4 to 5 problems because only that much i am able to code up in this time...