Edward's Problem List 19JAN23.txt

Good Learning Problems

https://codeforces.com/contest/1534/problem/F1 (kosaraju’s algorithm / scc)
https://codeforces.com/contest/1486/problem/D (O(n) sieve of Eratosthenes)

Intro problems (Kattis):
https://open.kattis.com/problems/echoechoecho Easy to read, beginner IO
https://open.kattis.com/problems/aprizenoonecanwin (Time complexity, O(n^2) TLE vs O(n) AC)


EASY 800-1500
Heap/Priority Queue:
https://codeforces.com/contest/1722/problem/D 

Dict
https://codeforces.com/contest/1511/problem/C 

Matrix
https://codeforces.com/problemset/problem/1438/C (matrix input, not an easy problem idea)

Prefix Sums:
https://codeforces.com/problemset/problem/961/B
https://codeforces.com/contest/433/problem/B
https://atcoder.jp/contests/abc278/tasks/abc278_e (2d prefix sums)

Binary Search:
https://codeforces.com/contest/1486/problem/C1
https://codeforces.com/contest/1676/problem/E (binary search + prefix sums or Using set lower_bound)
https://open.kattis.com/contests/jfvd4z/standings lots of somewhat standard problems (E requires graphs and D is harder)

DP:
https://codeforces.com/problemset/problem/1418/C 
https://codeforces.com/problemset/problem/1420/C1 
https://codeforces.com/problemset/problem/1469/C
https://codeforces.com/problemset/problem/1526/C1 
https://codeforces.com/contest/1741/problem/E (really good, two transitions)
https://codeforces.com/contest/1743/problem/C (2xn dp also has greedy)

Graphs:
https://codeforces.com/problemset/problem/1662/O (basic maze solving)
https://codeforces.com/contest/1676/problem/G (basic tree dp)
https://codeforces.com/contest/1675/problem/D (tree dp)
https://codeforces.com/problemset/problem/1661/B (non-graph bfs)
https://codeforces.com/problemset/problem/893/C (check connectivity)

greedy:
https://codeforces.com/contest/1591/problem/C
https://codeforces.com/problemset/problem/1694/B
https://codeforces.com/contest/1704/problem/B (maintain range of values and gassing bunnies)
	Sorting:
		https://codeforces.com/contest/1704/problem/C (sort difference array)
https://codeforces.com/problemset/problem/1084/C 
https://codeforces.com/contest/1742/problem/D (keep best index)
https://codeforces.com/contest/1692/problem/F (do problem mod 10)
https://codeforces.com/contest/1749/problem/B (easy)

two pointers:
https://codeforces.com/contest/1690/problem/D

calculate new information at each index:
https://codeforces.com/contest/1365/problem/C 

work backwards:
https://codeforces.com/contest/1650/problem/D 

brute force:
https://codeforces.com/problemset/problem/1450/B 

Mid 1500-2000
DP:
https://codeforces.com/contest/1613/problem/D
https://codeforces.com/contest/1132/problem/F (string dp)
https://codeforces.com/contest/1391/problem/D (clever insight + bitmask dp)
https://codeforces.com/contest/296/problem/B (technically 2000 rated but very basic dp)
https://open.kattis.com/problems/researchproductivityindex (EV dp)
https://codeforces.com/contest/1728/problem/D (substring dp + game theory)

Greedy:
https://codeforces.com/contest/1661/problem/D (work back from end)

Graphs:
https://open.kattis.com/problems/slowleak (floyd-warshall)

Trees:
https://codeforces.com/contest/739/problem/B (tree dp + events on tree)
https://codeforces.com/contest/1746/problem/D (tree dp)

Binary search:
https://codeforces.com/contest/1619/problem/D
https://codeforces.com/contest/1497/problem/E1
https://codeforces.com/contest/1547/problem/F (binary search + rmq)
https://codeforces.com/contest/1623/problem/C (simple binary search over sol. space)
https://codeforces.com/contest/1632/problem/D (non obvious binary search + req)
https://codeforces.com/contest/1624/problem/E (easier, build answer from smaller answers)
https://codeforces.com/contest/1661/problem/C (Don’t create a “greedy” formula, just binary search)

two pointers:
https://codeforces.com/contest/1631/problem/D

Data structures:
https://codeforces.com/contest/1619/problem/E (multiset or can be simplified to stack with intuition)
https://codeforces.com/problemset/problem/1624/G Basic DSU ideas
https://codeforces.com/problemset/problem/1609/D DSU + some intuition
https://codeforces.com/contest/1213/problem/G DSU+maintain set sizes+sort queries
https://codeforces.com/contest/1234/problem/D Sets of indexes or SegTree

Counting:
https://codeforces.com/contest/1622/problem/D 

Misc:
https://codeforces.com/contest/1633/problem/D (bfs+knapsack+additional insight)
https://codeforces.com/contest/1657/problem/D (precompute with harmonic series time complexity + binary search)
https://codeforces.com/contest/1715/problem/C Considering sum by counting weight at each index
https://codeforces.com/contest/1704/problem/D (find the invariant)

Hard 2000-2500


Strings:
https://codeforces.com/contest/1537/problem/E2 (z-function)
https://nac22.kattis.com/problems/cram (suffix array)
http://web.stanford.edu/class/cs97si/suffix-array.pdf (suffix arrays + packet)

Recursion/divide and conquer:
https://codeforces.com/contest/1748/problem/E

Bitset:
https://codeforces.com/contest/993/problem/C (iterate with map/two pointers + bitset)

tree:
https://codeforces.com/contest/1646/problem/D
https://codeforces.com/contest/1671/problem/E (Tree DP + combo)
https://codeforces.com/contest/280/problem/C (linearity of expectation, looks like tree DP, but isn’t)
https://leetcode.com/problems/create-components-with-same-value/  (tree dp + iterate over factors)
https://codeforces.com/contest/1278/problem/E (good dfs ideas, construct traversal order to achiever property)

Binary Lifting:
https://codeforces.com/contest/1535/problem/E

sqrt:
https://codeforces.com/contest/1619/problem/H (sort decomposition: store pointers for jumps of sqrt size)
https://codeforces.com/contest/1207/problem/F (heavy light)

graphs:
https://codeforces.com/contest/1741/problem/G (brute force graph (maybe TSP) + bitmasks dp)

data structures:
https://codeforces.com/contest/1616/problem/E ST or BIT
https://atcoder.jp/contests/abc254/tasks/abc254_f Range gcd query + math
https://codeforces.com/contest/1288/problem/E ST/BIT over value
https://codeforces.com/problemset/problem/1659/E DSU + bitwise intuition

Randomization:
https://codeforces.com/problemset/problem/1514/D (Can also use optimized Mo’s or ST)

hashing:
https://codeforces.com/contest/1056/problem/E (substring hashes)

dp:
https://open.kattis.com/problems/runningroutes
https://open.kattis.com/problems/badpacking
https://codeforces.com/contest/508/problem/E (substring dp, also has greedy solution)
https://codeforces.com/contest/1743/problem/E (Find point to dp over (both lasers fire))
https://codeforces.com/contest/1263/problem/F (also used binary lifting)
https://codeforces.com/contest/1077/problem/F2 Easy dp with interesting pq optimization
https://codeforces.com/contest/1670/problem/F (realizations -> dp over amount remaining by bit)

Trie
https://codeforces.com/contest/1720/problem/D2 (bit trie)

max flow:
https://codeforces.com/contest/852/problem/D (also requires APSP)
https://open.kattis.com/problems/copsandrobbers (flow in alternative graph)

event processing:
https://codeforces.com/contest/1743/problem/F (also contribution to sum, could also iterate from n to 1 using set lower bound) Editorial overcomplicates problem

Misc:
https://codeforces.com/contest/920/problem/E (skip bad edges)
https://codeforces.com/contest/1658/problem/E (manhattan->x,y transformation + pq/maintain max+min)

Mickey:
https://codeforces.com/contest/522/problem/C (mickey case)

FFT:
https://codeforces.com/contest/993/problem/E (basic FFT/NTT) 

Very Hard 2500+
https://codeforces.com/contest/1617/problem/E (Not too complicated, but difficult intuitions about graph/tree)

https://codeforces.com/contest/1632/problem/E2 (maintaining diameter of tree)

Interactive:
https://codeforces.com/contest/1746/problem/E1 or E2 (parallel queries)