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 into nothing. Thus we can create as much 2e10 intervals as we can, and try to keep the SG value to be 0.

Pancake Pyramid - Google Codejam 2019 Round 3 

We can solve this problem by trying each peaking points. Then the way to solve it turns out to be a neat manipulation of the stack data structure (or something similar). If we consider a peaking point, note that we can express the result using two left (same for right) pyramidifications, one on the left of the peak and one on the right.

More problems to add....