FerjaniSassi's blog

POLL
By FerjaniSassi, 4 weeks ago, In English

Which name is better and WHY

DSU ON TREES

SACK

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

»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

3rd one the worst contributor from the last. Sorry..

→ Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

They are different things though?

AFAIK DSU on trees is just the small-to-large trick applied to trees (you have an instance of a data structure on each node), and sack is more like HLD applied to MO's algorithm (you have a single global data structure and you insert into/erase from it)

I prefer the name sack though

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have a question. Does contribution gets reset after a certain period? Or it stays as it is?

    → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't know, but with positive contribution, if you are inactive for a long time, it resets to 0.

      → Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    How do you know so many algorithms ?

    → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I've been doing competitive programming for 7 years. I know a lot of useless stuff.

      → Reply