Skip to main content

Posts

Featured

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…

Latest Posts

Codeforces Problem Notes: Starting from 2019.4.26

A2OJ Ladder Climbing Note (1900 <= Codeforces Rating <= 1999)

Personal Thoughts after Codeforces Round #477 (rated, Div. 2, based on VK Cup 2018 Round 3)

Divide by Zero 2018 and Codeforces Round #474

Thoughts on Hello 2018. For myself.

Use of Linked List and Priority Queue in CF Round 452, Problem E

"Meet-in-the-middle technique" on Educational Codeforces Round 32, Problem E

''Euler tour technique' and 'Lazy Segment Tree' based on CF 877E