dvdg6566's blog

APIO 2020 Unofficial Editorial
By dvdg6566, history, 4 years ago, In English

Hello codeforces!

With the conclusion of APIO 2020, we have compiled an unofficial editorial for all 3 problems.

Credits to bensonlzl oolimry for helping with the compilation. The editorial can be found at the following link:

https://drive.google.com/file/d/1ZZIUOhvEl-sldF9eY8HSjTMnusHsbGsM/view?usp=drivesdk

Special thanks to APIO committee for an interesting problemset this year!

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

»
4 years ago, # |
  Vote: I like it +34 Vote: I do not like it

Does anyone have a solution that is lesser than O(n sqrt(400000)) for A? or is official solution also that .-.

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

Oops, I wasn't able to pass this approach for C ... I think this should work (for $$$N\le 500$$$) but I'm not sure why this takes care of the "edge" cases.

EDIT: Nvm, I see why it works.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +18 Vote: I do not like it

    WA

    It doesn't work :(

    Edit: I didn't read the code — this approach does work (it just uses too many queries in this instance)

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +28 Vote: I do not like it

    For the edge case, here's what I did.

    Terminology: Let the centroid be R, the subtrees be X,Y,Z. wlog let X be the biggest subtree.

    This edge case occurs is at the point where SZ(X) = SZ(Y) + SZ(Z) + 1, we are currently in subtree Y, where ht(X) < ht(Y) < ht(Z). In this case, we will jump from Y, then to X, then to Z.

    However, we cannot do this as ht(Z) + ht(X) > ht(Y) + ht(X). To resolve this, we make an additional jump from Y to Z.

    This is my implementaton: 

    if(t.s!=MAJ && t.f!=-1 && SZ(res) && pd[res.back()] < t.f){
  	res.pb(t.s);
  	V[belg[t.s]].pop_back();
  	blk=-1;
}

    Edit: tidied up my code a little bit, https://pastebin.com/Fq3hDrGB

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

Does anyone know when are they releasing the results?

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

    Friday, 21 August 2020 19:00 (UTC+7) is the closing ceremony

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

Is B solvable with MST?

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

    Yes, but it is a bit simpler.

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

    I think there is a solution that uses kruskal reconstruction tree to solve the problem

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

Is there any place to submit solutions yet?

→ Reply