2020 plan and summary
Hello 2020. Bye 2020
Update at the end of 2020: this was originally a plan. In 2020, I hoped to persist with 500 difficult problems and write regular summaries.
As you can see, it died somewhere around problem 64. Looking back, 64/500 is rather miserable. I certainly solved more than 64 problems, but the write-ups did not keep up.
The reasons are complicated, but fundamentally I did not stay committed to what I truly wanted. I got surrounded by trivial things and lost my direction along the way.
| Problem | Difficulty | Type | Comment | No. |
|---|---|---|---|---|
| CF_1264D1 | D | DP | Parentheses with ?; use DP to calculate each parenthesis’s contribution. |
1 |
| CF_1265E | E | DP | Expected-value DP and recurrence. | 2 |
| CF_1265D | D | Ad hoc | When the optimal approach is unclear, brute force it. | 3 |
| CF_1263E | E | Segment tree | Parentheses; update intervals and find their maximum and minimum. | 4 |
| CF_1263F | F | DP | Two trees, delete edges, minimize the cost. | 5 |
| CF_1260E | E | Ad hoc | Run a contest and bribe the judges. | 6 |
| CF_600F | F | Hungarian algorithm | The idea behind the Hungarian algorithm. | 7 |
| CF_1253D | D | N/A | N/A | 8(self) |
| CF_1253E | E | DP | Calculate each point’s range, then use DP. | 9 |
| CF_600D | D | Computational geometry | Template geometry; area of intersecting circles. | 10 |
| CF_598F | F | Computational geometry | Length of a line’s intersection with shapes; cross products. | 11 |
| CF_1245F | F | Digit DP | Similar to a HihoCoder digit-DP problem; brute force. | 12 |
| CF_1133E | E | DP | Fairly standard DP, not greedy. | 13 |
| CF_600E | E | Ad hoc | Merging trees in $O(n\log n)$. | 14 |
| CF_1227F1 | F | DP | DP to count permutations. | 15 |
| CF_1163D | D | DP | Compute the next array; string DP considering all cases. |
16 |
| CF_1245E | E | 17 | ||
| CF_1257E | E | DP | DP and permutations. | 18 |
| CF_1272E | E | Graph theory | Graph theory; shortest paths. | 19 |
| CF_1271E | E | Binary search | Identify the pattern, then binary-search twice (problem-setting). | 20 |
| CF_1278D | D | Binary search, trees | Given segments, intersections represent connections; determine if they form a tree. | 21 |
| CF_1269D | D | Ad hoc | A neat trick: turn dominoes into a chessboard problem. | 22 |
| CF_652D | D | Fenwick tree | A basic Fenwick-tree problem—why did it take so long? | 23 |
| CF_468B | D | dsu, 2-sat | dsu | 24 |
| CF_744B | D | Interactive | A classic interactive problem: split by each bit and calculate. | 25 |
| CF_744C | E | Bitmask DP | ||
| CF_1266D | D | Ad hoc | Assume a cycle and simplify debt repayment. | 27 |
| CF_1282D | D | Interactive | Interactive edit-distance problem. | 28 |
| CF_1278E | E | Ad hoc | Given a tree, construct intersecting segments. | 29 |
| AGC_41B | D | Binary search | Choose $p$ of $N$ problems after $M$ votes. | 30 |
| LC_1307 | C | Ad hoc | Arithmetic expressions: simplify first, then DFS. | 31 |
| LC_P3 | D | Ad hoc | Robot adventure. | 32 |
| CF_1270D | D | Interactive | Ad hoc; the rank of the returned result is unknown. | 33 |
| CF_228E | E | 2-SAT | A 2-SAT template problem. | 34 |
| CF_27E | E | Mathematics | Given a number of divisors, find the smallest number with that count. | 35 |
| LCP4. Coverage | D | Hungarian algorithm | Bipartite maximum matching; cover with 1x2 dominoes. Bitmask DP also works. A classic older problem. | 36 |
| CF_1284C | C | Counting | Count valid intervals across all permutations; count fixed intervals. | 37 |
| CF_1173C | C | Ad hoc | Two decks of cards; tricky, with implementation details to watch. | 38 |
| CF_1173D | D | Counting, tree DP | A tree; count permutations while preventing edge crossings. | 39 |
| CF_1286B | D | DFS | Given how many nodes in a subtree are smaller, find every final node value. | 40 |
| CF_1180D | D | Ad hoc | Turn one dimension into two; reason around the center. | 41 |
| CF_1185D | D | Ad hoc | Easy problem. | 42 (self) |
| CF_1307C | C | Ad hoc | The string length can only be one or two. | 43 |
| CF_1313C2 | D | Stack | A classic stack problem—good review. | 44 |
| CF_1307D | D | BFS, sort | BFS plus sorting; revisit the sorting part. | 45 |
| CF_1311F | D | Fenwick tree, merge sort | The idea behind merge sort. | 46 |
| CF_1311D | C | Easy problem | Easy problem. | 47 (self) |
| At_PPC_E | D | Thinking | Not greedy; closer to DP. Combine three strings to minimize the final length. | 48 |
| At_PPC_F | D | Thinking | A large graph with a blocked middle; find the distance between two points. | 49 |
| At_160_F | E | Tree | Topological ordering of a tree, then convert to DP. | 50 |
| At_164_E | E | Shortest path | Shortest path. | 51 |
| At_163_E | E | DP | Sort, then greedy + DP. | 52 |
| CF_1290B | D | Trick | Observe the pattern. | 53 |
| LCP 14 | D | DP | Split the array where gcd != 1. |
54 |
| LC 5403 | D | Trick | Just maintain $k$ of them. | 55 |
| LC 5387 | D | Bitmask DP | Hats and people are treated the same way. | 56 |
| LCP 05 | D | Segment tree | DFS serialization + segment tree. | 57 |
| CF768E | E | Game theory | A game-theory problem: find the SG value. | 58 |
| CF1355E | E | Ternary search | A standard ternary-search problem. | 59 |
| CF1343E | E | Graph theory | A tricky solution using sorting. | 60 |
| CF1355D | D | Trick | Trick. | 61 |
| CF1354D | D | Fenwick tree + binary search | 62 | |
| CF1354E | E | dp | 63 | |
| CF1342D | D | Binary search | Got caught by vector. |
64 |