Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

vinupreethi93's blog

By vinupreethi93, history, 5 weeks ago, In English,

i cant understand the problem. https://codeforces.com/problemset/problem/1325/C

can someone help me please

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You have to mark the edges with some numbers from 0 - (N-2) in such a way that, if you go from any vertex (u) to any other vertex (v) the element that doesn't exist in a simple path from u to v is minimum.

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

    Consider TestCase-2, If you have to go from vertex 1 to 6 you have to go like this:

    1 - 2 -> edge value — 0

    2 - 5 -> edge value — 4

    5 - 6 -> edge value — 1

    So, the minimum value that doesn't exist in this path is value 2

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution

  • You have a tree with n vertices, so n-1 edges.
  • Mark all the edges with numbers from 0 to n-2.
  • Take any pair of vertices and write down the numbers on the edges in the shortest path between them.
  • Find the MEX of this array.

If you understand how MEX works, the problem is simple. The MEX of any path that doesn't contain the edge labeled 0 is 0. Find a vertex which has more than 3 edges, and mark them 0, 1, 2. Mark the remaining edges randomly. This ensures that the maximum MEX is 2.