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

------------------------------------------------------------------------------------------------
The ladder in A2OJ sort of fits the idea of upsolving in competitive programming, which encourages me to solve the problem in it. I wrote this blog to record some neat idea of the problems and things I learn.
------------------------------------------------------------------------------------------------


Problem 41: Sliding window technique. Just need to remember using S.erase(S.find(num[i])) in multi-set instead of S.erase(num[i]) because the latter will delete all value that equal to num[i] in S.

Problem 49: A map version of the algorithm of finding longest sub-sequence can lead to a O(n*n*logn) solution. However, the tutorial had a O(n*n) solution, which requires more consideration.

Problem 51: The way to represent a permutation as a graph of loop is interesting and useful for solving the problem.

Problem 54: Tried hard to find a solution of dp in a combinatoric way, while the solution is simply doing dp in a linear time.


Problem 56: A problem that doesn't accept O(m*n*logn) but O(m * n). The sliding window technique using deque is a salient one, which allows to find the minimum in a sliding window in amortized O(n) time. Sliding Window Minimum Implementations


Problem 64: Convex Hull Trick is something that I've never heard about. But this interesting algorithm is crucial for solving this problem. Convex Hull trick


Problem 80: The dp solution is really neat, but I encountered a problem when I was implementing the solution: I frequently used division, which I later found is unacceptable when there is a module. Instead, suffix and prefix product can help do the job.

Comments

Popular Posts