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

can someone help me please

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

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | tourist | 3567 |

3 | Um_nik | 3527 |

4 | ecnerwala | 3458 |

5 | maroonrk | 3409 |

6 | 300iq | 3317 |

7 | Petr | 3272 |

8 | LHiC | 3229 |

9 | Benq | 3226 |

10 | TLE | 3223 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 197 |

2 | antontrygubO_o | 188 |

3 | pikmike | 183 |

4 | Ashishgup | 182 |

5 | vovuh | 179 |

6 | Radewoosh | 167 |

7 | Um_nik | 165 |

8 | tourist | 163 |

9 | McDic | 162 |

10 | Geothermal | 157 |

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

can someone help me please

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/02/2020 08:29:22 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.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`

Suppose say the path from u=1, v=6 the numbers in edges are 0, 4, 1 now the next minimum number on the edge should be 2, so i can fill it in 1-3 as well as 2-4 right??

No. You didn't understand what MEX is.

Yeah i can understand it now thank you

Hi sorry im unable to reply to you.dont know why

That's okay.

Solution

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.

Thank you, i can understand!