[Tutorial] Kinetic Tournament (Used in FBHC Round 2) Background ------------------ During Facebook Hacker Cup Round 2 today, Problem D caught my attention. It reminded me of a particular data structure called a **kinetic tournament**, which is not very well known in this community. However, it offers an extremely clean and slick solution to the problem, in my opinion. I first learned about this data structure from [user:dragonslayerintraining,2020-08-30], who described a variant of it in this [Codeforces blog comment](https://codeforces.com/blog/entry/68534#comment-530381). Since the data structure is so interesting, I feel like it deserves a longer explanation, some template code, and more examples. That's why I am writing this blog post. Kinetic Tournaments ------------------ Briefly, the functionality of the data structure is a mix between a line container, i.e., "convex hull trick", and a segment tree. Suppose that you have an array containing pairs of nonnegative integers, $A[i]$ and $B[i]$. You also have a global...

Full text and comments »

I compiled a list of almost all useful blogs ever published on Codeforces [update: till 09.06.2021] <h3 style="color:red">If there are any blogs that I have missed, please tell in the comment section. Thank you.</h3> # Mathematics Stuff - [Number Theory in Competitive Programming [Tutorial]](https://codeforces.com/blog/entry/46620) - [Number of points on Convex hull with lattice points](https://codeforces.com/blog/entry/62183) - [FFT, big modulos, precision errors.](https://codeforces.com/blog/entry/48465) - [Number of ways between two vertices](https://codeforces.com/blog/entry/19078) - [Mathematics For Competitive Programming](https://codeforces.com/blog/entry/76938) - [FFT and NTT](https://codeforces.com/blog/entry/19862) - [Burnside Lemma](https://codeforces.com/blog/entry/51272) - [Number of positive integral solutions of equation 1/x+1/y=1/n!](https://codeforces.com/blog/entry/76836) - [On burnside (again)](https://codeforces.com/blog/entry/64860) - [Simple but often unknown theorems/lemmas/formula? Do you know?](https://codeforces.com/blog/entry/55912) - [Probabili...

Full text and comments »

Editorial of Codeforces Round #778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round) [problem:1654A] Author: [user:TheScrasse,2022-02-24]<br> Preparation: [user:TheScrasse,2022-02-19] <spoiler summary="Hint 1"> Suppose you want to choose pieces of cake $i$, $j$. Can you make them adjacent in $1$ move? </spoiler> <spoiler summary="Solution"> The answer is the sum of the $2$ maximum weights. You can always pick the $2$ maximum weights: if they are $a_i$ and $a_j$ ($i < j$), you can flip the subsegment $[i, j-1]$ to make them adjacent. The result can't be larger, because the sum of the weights of any $2$ pieces of cake is never greater than the sum of the $2$ maximum weights. Iterating over all pairs of pieces of cake is enough to get AC, but you can solve the problem in $O(n \log n)$ by sorting the weights and printing the sum of the last $2$ values, or even in $O(n)$ if you calculate the maximum and the second maximum in linear time. Complexity: $O(t \cdot n^2)$, $O(t \cdot n \log n)$ or $O(t \cdot n)$ </spoiler> Official solution: [submissi...

Full text and comments »

(Plenty of) useful blogs in CodeForces Here are some useful blogs I found in CodeForces. Note that: - This list can be treated as an extension of [catalog](https://codeforces.com/catalog), since much of these tutorials are included in catalog but the others are collected by myself. - The same blog may be included in this post twice or more. - Blogs to ask questions are **NOT** included in this blog, since they seemed not quite useful to CP. - If there are any blogs that I have missed, please tell me in the comment section. Thank you very much. Hint: you can use Ctrl+F to search for information here. # General Advices ## Micellaneous - [How to use Codeforces [GUIDE]](https://codeforces.com/blog/entry/99660) - [[Tutorial] The command line: how to read input from file without #ifdef and much more](https://codeforces.com/blog/entry/102287) - [After a Round FAQ](https://codeforces.com/blog/entry/103654) - [[Tutorial] How to read editorials](https://codeforces.com/blog/entry/123882) - [Pro Tips — get them whi...

Full text and comments »