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.
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
Post a Comment