Блог пользователя abdallahmontaser

Автор abdallahmontaser, история, 3 года назад, По-английски

https://mirror.codeforces.com/edu/course/2/lesson/7/1/practice/contest/289390/problem/C

in this problem if i used path compression get wrong answer and accept without path compression can any one explain why

this code that get wrong answer https://mirror.codeforces.com/edu/course/2/lesson/7/1/practice/contest/289390/submission/132622662

this code that get accept https://mirror.codeforces.com/edu/course/2/lesson/7/1/practice/contest/289390/submission/132624996

If you could give an test , that would be great

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

The whole idea of this problem is that normal path compression doesnt work and union by size does (or maybe using nothing works as well because of weak test cases).

Path compression doesnt just magically make the complexity better. Suppose we have something like this:

When we call merge on 3 and 4 without path compression, we get this:

Then if we call "get" on 3, we would get the right answer, 10 — 20 + 40 = 30.

However, this is what happens when we find the leader for 3 and merge later:

All the relations between the nodes are lost, and now the 10 points from 2 aren't count for the answer, giving 20 instead of 30. This gets very wrong very quickly.

If you really want a solution with path compression, here is mine. Im basically updating the information of the nodes while doing the path compression to prevent this from happening