The_mysterio's blog

Help on problem Johny and Contribution
By The_mysterio, history, 4 years ago, In English

Kindly help me with the solution of this problem https://mirror.codeforces.com/contest/1362/problem/D My solution https://mirror.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

Comments Comments (1)
| Write comment?
»
4 years 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 !

→ Reply