el-nino's blog

Timus 1003.Чётность. Как применить DSU?
By el-nino, 13 years ago, In Russian
Недавно изучил алгоритм DSU (disjoint set union) и хотел решить некоторые задачи принимая его. Вдруг нашёл задачу из тимуса 1003.Чётность...
Уже недели никак не могу решат его. Сначала в голову пришли куча идеи но они оказались неправду. Я знаю его можно решить с помощью другими методами но хочу решить именно с помощью DSU! Я хочу применить DSU в практике. Помогите мне пожалуйста. Буду очень рад если скажите другие задачи. Всем заранее спасибо...       
  • Vote: I like it
  • +14
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
13 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Let a[k] - (sum of  1) %2 from 1 to k element. (a[k] - 0 or 1)

Then sum is even for subsequence from l to r  means a[l-1]=a[r].
Therefore sum is odd for subsequence from l to r means a[l-1]!=a[r].
It is clear, that a[0] = 0, because it is empty sequence (from 1 to 0 element)
That is the problem - is to find first moment, when wiil be contradiction in these equalities.

So for DSU:
we can take for each a[k] two vertexes - the a[k] and !a[k] (the opposite value of the a[k]). These two vertexes should always be in different sets. Initially all vertexes stands in different sets.

Then when we get request like a[l-1]=a[r], we can combine a[l-1] & a[r] to one set and  !a[l-1] & !a[r] to another, that is will mean that a[l-1] and a[r] have equal values and !a[l-1] & !a[r] have equal values too.

When we get request like a[l-1]!=a[r],  we can combine vertexes !a[l-1] & a[r] which means that a[l-1] & a[r] have different values.

Then the contradiction can happen onle when we have a[l-1] and !a[l-1] in one set or a[r] and !a[r] in one set.

I saw that you from Spain. Hope it will be easier for you to read on english rather than russian . If not - let me know, I'll rewrite it.
→ Reply