Date: Oct/28/2024 Rank: 1727 Solved: 3 Rating change: -80 New rating: 1970
- Problem E: The project selection problem.
Date: Sep/20/2024 Rank: 936 Solved: 4 Rating change: -49 New rating: 2009
- Problem E: Greedy. Choose the smallest element. Proof: a b c 1 d e --> 1 a b c d e. Sister problem: 1614 D2.
Date: Sep/14/2024 Rank: 245 Solved: 5 Rating change: +43 New rating: 2058
- Problem E: Good DP problem. Maintain the smallest array index that can win the game.
- Problem E: Use bitset to speed up.
Date: Aug/15/2024 Rank: 5441 Solved: 3 Rating change: -127 New rating: 1832
- Problem E: Use the SG theorem.
- Problem F: Key technique: find a suffix and a prefix that are equal.
- Problem G: Use segtree (may exceeds the time limit), two-stack technique, prefix/suffix sum.
Date: Aug/11/2024 Rank: 1500 Solved: 4 Rating change: 0 New rating: 1934
- Problem D: For a valid DFS order, the parent of
p[i+1]must be an ancestor ofp[i]. - Problem E: Consider an incremental solution. Only keep useful information with a stack.
- Problem F: The prime gap is small: O(log n). Do a bfs search in a small corner (p,n) to (q,m).
Date: Aug/10/2024 Rank: 1319 Solved: 3 Rating change: -38 New rating: 1934
- Problem E: Build a Cartesian tree and do dp on it.
Date: Aug/04/2024 Rank: 722 Solved: 3 Rating change: -6 New rating: 1972
- Problem D: Key observation:
i%kis the number of picked elements. - Problem E: For a fix row, the number of possible values is n+1. Use dp to select a path.
- Problem F: Walking in a map with size of
[w*2, h*2]. Use math to calculate how many times it visits (0,0). A similar problem 982E.
Date: Jul/30/2024 Rank: 2351 Solved: 4 Rating change: -90 New rating: 1978
- Problem E: For each monster, use binary search to find out what is the minimum k that the user will have to fight this monster.
- Problem F: Knapsack counting.
Date: Jul/23/2024 Rank: 69 Solved: 5 Rating change: +114 New rating: 2067
- Problem E: Enumerate the min value and the max value. Use segment tree to fast check if the state is valid.
Date: Jul/20/2024 Rank: 359 Solved: 4 Rating change: +49 New rating: 1953
- Problem E: Each query removes sqrt N nodes. Then use sqrt N queries to move the Mole to the root.
- Problem F: Key observation: number of possible ends is log N. Use segment tree.
Date: Jul/15/2014 Rank: 2194 Solved: 3 Rating change: -81 New rating: 1903
Unsolved problems:
- Problem D: The maximum number of round is limited to log2n.
- [Problem E]: Use Cartesian tree to calculate the answer. What happens if one of the tree node gets removed?
- Problem E: Count the contribution of each number to the final answer. A trick to find the second maximum next value.
- Problem F: For each n, calculate sum i sum p sum q F(i, p) times G(n-i, q). Reduce the time from O(n4) to O(n3).
Date: Jul/07/2024 Rank: 131 Solved: 5 Rating change: +114 New rating: 1984
Unsolved problems:
- Problem F: Binary search on the answer and check for each new right end if it can lead to a smaller xor value.
- Problem G: Calculate each bit independently. Use the patterns (e.g. 00110011) to precompute the sum to the tree root.
Date: Jun/16/2024 Rank: 340 Solved: 5 Rating change: +63 New rating: 1870
Unsolved problems:
- Problem F: Use DSU to merge the nodes with the same factor.
Date: Jun/09/2024 Rank: 2154 Solved: 4 Rating change: -31 New rating: 1807
Unsolved problems: