Notes on problems other than Codeforces - May 2019
Probe Droids - NAIPC 2018 : The differences of the slopes between lattice points (x, y <= 1e6) can be as small as 1e-12. We can descend along Stern-Brocot Tree to find the closest fraction to a floating point number. Euclidean-like method to find the number of lattice points under a certain line. F - Unhappy Hacking - AtCoder ARC 59 Tried to make observation of the DP formula but failed to improve an O(N^3) solution It turns out that the content of the string does not matter. Then we can just calculate the number ways to get a string length of m after n operations and divide it by 2^n since the diferent strings are essentially the same. Zillionim - Google Codejam 2019 Round 3 Since the opponent is random, we should consider under which scenario human is better than random. The answer is when there are an interval of 2e10, human can either cut it into nothing or 1e10 while the AI will most likely cut it int...
