orz's blog

Codeforces Round 907 (Div. 2) Screencast & Editorial
By orz, history, 13 months ago, In English

I participated in Codeforces Round 907 (Div. 2). I believe it could be the first time I was late for a Codeforces Round but still participated in it; however, I solved all problems. The round featured a lot of ideas, which were pretty standard, but it still was kinda nice to discover them here.

Problem Screencast Editorial
1891A - Sorting with Twos https://youtu.be/R2KQsS90MbQ?t=8 https://youtu.be/YOBGKbGMqvY
1891B - Deja Vu https://youtu.be/R2KQsS90MbQ?t=504 https://youtu.be/sXYMZWtb02U
1891C - Smilo and Monsters https://youtu.be/R2KQsS90MbQ?t=1053 https://youtu.be/oaTpslv72zs
1891D - Suspicious logarithms https://youtu.be/R2KQsS90MbQ?t=1817 https://youtu.be/6t_J_-CJ9qM
1891E - Brukhovich and Exams https://youtu.be/R2KQsS90MbQ?t=4838 https://youtu.be/rJ102FAqe5E
1891F - A Growing Tree https://youtu.be/R2KQsS90MbQ?t=2675 https://youtu.be/68e4Qt0fF_g
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

approach for f with euler tour and lazy Propagation with seg tree is giving tle on tc 22. here is the code- https://codeforces.net/contest/1891/submission/230589277

→ Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    Fenwick tree is much faster than a regural segment tree, and segment tree without lazy propagation can me much faster than the one with lazy propagation. Also the up-to-bottom implementation of segment tree can be substantially slower than the bottom-to-top one.

    Also note that in your implementation of Euler tour each vertex is put twice in the array. This is not needed, however: one time (either at the beginning or at the end of the dfs procedure) is enough.

    So I definitely feel for you, but I have to admit there is enough room for optimization in your solution. My approach gets OK in 295 ms: 230557194. If I were a problemsetter, I would try to loosen TL as much as possible, and your solution would probably get OK as well.

    P.S. The editorial proposes the same approach I used.

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

      thanks for this knowledge.I don't know how to use fenwick tree,i will try to learn in few days. I know i can optimize my code further and my changing map to unordered_map i got ac.

      → Reply