Chtholly Tree Complexity Analysis

Revision en1, by nichke, 2022-03-14 20:22:06

Hi CodeForces, yesterday I encountered problem 896C related to Chtholly Tree. My understanding of integrals is limited so the comment in the editorial wasn't of great help and I couldn't find any articles online discussing the complexity. I'd appreciate if someone would clearly derive the complexity of the algorithm provided the queries are uniformly distributed (preferably using elementary maths only). Thanks! Regards!

Tags algorithm complexity, probability

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English nichke 2022-03-14 20:22:06 456 Initial revision (published)