Trees are a subset of graph theory problems that use the features of a tree:

• Acyclic
• Exactly 1 path between every pair of nodes.

Important algorithms (hopefull) exhaustive list:

• Preorder + Data strcutures
• Dynamic Programming on tree
• $$$2^K$$$ Decomposition of tree (and Lowest Common Ancestor)
• Kruskal Reconstruction Tree (KRT) (IOI Werewolf trick)
• Set Merging (with linear height merging)
• $$$O(N^2)$$$ Distribution DP
• "Re-rooting" tree DP (where you DP twice, once going down and once propagating from top)
• Centroid Decomposition
• Heavy-Light Decomposition
• UFDS on tree (See: CEOI 2017 Streets)
• (Edit: Thanks errorgorn ) Greedy for furthest node (See: RU Code Funny Salesman)

Would be interested to see if anyone has any suggestions what I missed out on!

Picture this: Your algorithm is the correct complexity, but the verdict is TLE. You make some constant time optimizations and AC, or worse, only get an AC after contest. I think the issue of constant time TLE is something many people have faced.

Where does this stem from? The main issue surrounding this is scam solutions. Problemsetters hope that only intended, or similar to intended solutions get an AC verdict. Sometimes, it can be difficult to differentiate between highly-optimized slow code (say NlogN) and unoptimised fast code (say O(N)).

I've personally faced this issue in a big way 3 times. Twice as a problemsetter, once as a contestant. I thought I should share about some of my experiences:

Contestant: IOI 2020, biscuits, 77 points subtask My situation: I had managed to optimize from O(200,000Qlog(10^18)) to O(200,000Q), I was highly expecting to get the points. TLE. I reasoned that recursion is slow, and recoded it iteratively. Still TLE. Finally, I gave up and coded STL queue with 2 pointers on an array. Finally an AC, which ended up deciding my medal colour. Why is such a high-stakes contest down to who listened during a lecture about C++ STL being slow?

Problemsetter: Codeforces Raif Round 1, problem E Fruit Sequences

Our situation: Intended solution is O(N), but fast O(NlogN) implementations with array-based segment trees still got AC. In the end, we allowed the segment trees to AC.

Problemsetter: Problem called collaboration for school contest

Problem: Find the number of pairs of nodes in a tree distance K apart in O(N)

Solution: O(NlogN) centroid decomposition, O(N) set merging

What we did: We set N=3,000,000 and TL as 6s. This only worked because the contest only had C++ submissions, and centroid decomposition could not pass the limit.

Ending thoughts: Is there any way we could help mitigate this issue? As someone who almost had an IOI silver changed into a bronze because of this, I can't help but feel that someone somewhere should try to find a solution.

Personally, I feel that Atcoder's idea of template libraries may make sense. Another thought is banning GCC pragmas and similar optimisations to make it harder to optimise slow code? Honestly, I have no clue. Willing to hear anyone's thoughts and experiences on this.

WARNING: DISGUSTING PROBLEM ALERT

At the start of the year, I wrote a very painful implementation problem. My official solution was over 200 lines long and I was wondering if anyone could come up with a more elegant solution.

The problem is as follows:

Given some subtasks, the highest score was 72 by A_Wallaby. Majority of participants scored 27 points, where $$$B_i = 0$$$ for all $$$i$$$.

This problem is by no measure an elegant problem. It took me close to 4h to implement. I was wondering if anyone could find a more elegant solution? If anyone is interested, here is the problem statement and the solution code.

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!