errorgorn's blog

By errorgorn, 22 months ago, In English

Selamat pagi Codeforces!

We are excited to invite you to TLX Regular Open Contest #30!

Key details:

Many thanks to:

Please register for the contest or else rama_pang will drink all your milk 😋🥛.

UPD: the contest is over!

Congratulations to the top 5:

  1. Benq (perfect score)
  2. maroonrk
  3. hos.lyric
  4. hitonanode
  5. nuip

Congratulations to our first solvers:

Also, congratulations to Phantom_Performer for getting the 400000-th submission!

You can upsolve the problem here. Editorial is available in the upsolve link!

Thank you for participating and see you on the next contest!

  • Vote: I like it
  • +200
  • Vote: I do not like it

»
22 months ago, # |
  Vote: I like it +18 Vote: I do not like it

How to register

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    You should go to the contest link in TLX and register there. You need to login to register. If you have not made a TLX account before, you can easily make one there.

»
22 months ago, # |
  Vote: I like it +48 Vote: I do not like it

TLX Regular Open Contest

Is the TOKI Regular Open Contest being renamed TLX Regular Open Contest?

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Yes! It has been renamed since TROC 29.

»
22 months ago, # |
  Vote: I like it +39 Vote: I do not like it

What's the contest difficulty when compared to a cf round? Div2 ? Div3? Div1?Div1+Div2?Div4?

  • »
    »
    22 months ago, # ^ |
    Rev. 2   Vote: I like it +32 Vote: I do not like it

    It is like an easier version of a Div. 1 + Div. 2 Codeforces round.

»
22 months ago, # |
  Vote: I like it +28 Vote: I do not like it

Friendly reminder that the contest will start in less than 90 minutes!

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Don't forget to drink milk for good luck 😋🥛!

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

Just curious, is there no tester for TROC or are they hidden?

»
22 months ago, # |
  Vote: I like it +8 Vote: I do not like it

E: dynamic connectivity is dead

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

How to solve E without LCA and segment trees?

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

    I used Zobrist Hashing code

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    It is possible solve it deterministically only using DSU.

    For the second part of the problem where we need to mark roads on a path from $$$A_i$$$ to $$$B_i$$$, we will merge vertices $$$u$$$ and $$$v$$$ if edge $$$(u,v)$$$ is marked on the DSU. When we add a new father from $$$A_i$$$ to $$$B_i$$$, we need to mark all unmarked paths from $$$A_i$$$ to $$$B_i$$$. This can be done quickly using DSU if in each DSU component, we store the highest vertex. This way we can quickly to the highest unmarked edge.

    code: https://tlx.toki.id/problems/troc-30/E/submissions/1289709

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

      I wrote MST for the initial graph, and then deleted edges that were not necessary. I ran dfs on MST, lets say I am at a node ND and K is a son of ND, then look at a subtree starting with K, if in this subtree there is no node that needs to pass ND on it's way to it's "interesting" node then you can delete ND-K edge.

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

Lucky me :)