Shayan's blog

Codeforces Round 981 (Div. 3) — Video Tutorial
By Shayan, 4 weeks ago, In English

Note: The text editorials will be provided by the authors of the round. This video tutorial acts as an additional resource for those who prefer video over text, not as a substitute for the text editorial.

2033A — Sakurako and Kosuke

Video

2033B — Sakurako and Water

Video

2033C — Sakurako's Field Trip

Video

2033D — Kousuke's Assignment

Video

2033E — Sakurako, Kosuke, and the Permutation

Video

2033F — Kosuke's Sloth

Video
  • Vote: I like it
  • +17
  • Vote: I do not like it

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

No G?

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

Where is G?

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

plz tell me when Tutorial (en) will appear,thx

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

How this got hacked on tle https://codeforces.net/contest/2033/submission/287798279 ? Pretty sure this is O(N) only.

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

Hi,in problem F I dont get the part why the length of the period is O(k) can someone elaborate on that?

→ Reply
»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

downvotes is crazy

→ Reply
»
4 weeks ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Most of them in top 10 of the official standings have cheated. No doubt about it. I feel useless doing contests now...

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

G can be solved with binary uplifting. For each v,k there are 2 way: travel from v to the lowest leaf in the subtree at v; or move up k0 <= k ancestors and travel down.
Use binary uplifting for when moving up.

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

    Can you explain more?

    With binary lifting I understood that I need to reach the _k_th ancestor of vi in logn. Then need to find the deepest node from that _k_th ancestor excluding vi.

    How to do this excluding?

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

      First, for each node, we calculate the deepest child, the parent, the longest path if moving up the parent and down another subtree. So we have all calculated k=1 for all nodes. For each node i, if kth ancestor is j, we have: 2*k th ancestor of i = kth ancestor of i; max_path_from_i_up_to_2*k = max(path_from_i_up_to_k, k + path_from_j_up_to_k).

      For binary lifting we travel up the ancestors and update the longest path.

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

c is much harder than d e f...

→ Reply