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

DSU roll back offline deletion
Автор sitingfake, история, 5 недель назад, По-английски

can anyone help me explain this technique, is this technique used frequently in famous contests such as icpc,ioi...? sorry for my poor english

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

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

Just take the advice from Um_nik: "Stop learning useless algorithms, go and solve some problems, learn how to use binary search".

→ Ответить
  • »
    »
    5 недель назад, # ^ |
      Проголосовать: нравится -13 Проголосовать: не нравится

    There's no need to take some algos down. DSU roll back offline deletion is also a common and useful algo with widely use. It's easy, too. Just use a stack to record the operations and pop while you need to roll back, which is much shorter than sustainable DSU.
    I think Um_nik's words are not right at all. On one hand, for example, in China, it's necessary to use some "useless algorithms" like Li-Chao Segment Tree, Segment Tree Beats and $$$k$$$-th shortest path expertly for the OIers who's just a junior high school with about 14 years old. MST in $$$O(E\log V)$$$ is one of the key tools for 12 year-old kids to get more points in the CSP Coding ability recognization. On the other hand, Codeforces is not the only OJ all around the world, although it has the most valuable problems. Many CPers spend their time on other OJ, maybe AtCoder for Japanese, Luogu for Chinese, or others. The color of the name on CF is not the only evidence to judge a CPer's ability.
    Uselessness is not the excuse of laziness. Keeping learning is the most fun thing in the life.

    → Ответить
    • »
      »
      »
      5 недель назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      My answer was mostly to this part of the question: "is this technique used frequently in famous contests such as icpc,ioi."

      I believe there's very limited usefulness to learn advanced algorithms while more simple algorithms are not mastered.

      "The color of the name on CF is not the only evidence to judge a CPer's ability." — I strongly disagree with this claim. It might be true if the user has too few contests but if one participated in, let's say, 10 contests — then we can reliably judge his/her ability.

      → Ответить
»
5 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

to enable rollbacks in any data structure, we can simply save every change invector<pair<int&, int>>, where first element in pair is link to changed memory, and second — value before change.When we need to undo last change, just changes.back().first = changes.back().second;changes.pop_back(); remember, that in dsu you change multiply values in one query, so we need to undo a couple of changes to make rollback.

→ Ответить