Competitive Programming
Use these filters to narrow down your next problem to solve:
OJ: , Topic: , Quality:
You can now sort these problems based on Distinct ACcepted Users (DACU) column.
Generally, problems with high DACU are the easier problems.
Note that we only update DACU column manually (not a live data).
As Kattis users, you can also sort these problems based Kattis points (usually correlated with DACU but not always).
Generally, problems with low Kattis points are the easier problems.
Note that we only update Point column manually (not a live data).
For Kattis and Google Chrome users, install Kattis Hint Giver created by one of my student Lin Si Jie that integrates this page directly with Kattis problems pages (Kattis has major UI/UX upgrade on early Jun 2022, Si Jie has updated this tool and added 'spoiler blur' so users can decide when to be spoiled)
(Almost) all of the easiest 796 problems (range: [1.2..3.3] points, average at 2.25 points) have hints and solving them all gives you 796*~2.25 ≥ 1700 total Kattis points — The Lower Bound of Programming Contests in the 2020s.
Tips: You may want to occasionally 'Remove from Chrome' and re-'Add to Chrome' to manually sync this Methods to Solve content with the local cache.
| Kattis | Problem Title | CP4 | Hint | DACU | Point |
|---|---|---|---|---|---|
| knapsack |  knapsack |
3.5c, 0-1 KNAPSACK | basic DP KNAPSACK; print the solution | 687 | 4.8 |
| muzicari | muzicari |
3.5c, 0-1 KNAPSACK | set Knapsack of size = T, each break length as item weight, and value = 1/2 (put that break at 'virtual knapsack 1/2', r... | 343 | 4.9 |
| ninepacks | ninepacks |
3.5c, 0-1 KNAPSACK | brute force all possible sums; use DP SUBSET-SUM on each hotdog and bun packs; clever problem | 499 | 4.4 |
| orders | orders |
3.5c, 0-1 KNAPSACK | interesting KNAPSACK variant; print the solution | 713 | 4.5 |
| presidentialelections | presidentialelections |
3.5c, 0-1 KNAPSACK | pre-process the input to discard non winnable states; be careful of negative total voters; then standard DP KNAPSACK | 116 | 5.7 |
| bagoftiles | bagoftiles |
3.5d, COIN-CHANGE | count number of ways to do COIN-CHANGE; meet in the middle; DP combinatorics (n choose k) to find the answer for a+b | 102 | 6.5 |
| canonical | canonical |
3.5d, COIN-CHANGE | complete search possible range of counter examples; do both greedy COIN-CHANGE and DP COIN-CHANGE | 502 | 5.7 |
| exactchange2 | exactchange2 |
3.5d, COIN-CHANGE | a variation to the Coin-Change problem; also available at UVa 11517 - Exact Change | 708 | 5.4 |
| beepers | beepers |
3.5e, TSP | DP or recursive backtracking with sufficient pruning; also available at UVa 10496 - Collecting Beepers | 196 | 4.6 |
| bustour | bustour |
3.5e, TSP | LA 6028 - WorldFinals Warsaw12; DP TSP variant; also available at UVa 01281 - Bus Tour | 124 | 6.1 |
| cycleseasy | cycleseasy |
3.5e, TSP | Count number of HAMILTONIAN-TOURs | 108 | 4.1 |
| errands | errands |
3.5e, TSP | map location names to integer indices; DP TSP | 51 | 7.0 |
| maximizingyourpay | maximizingyourpay |
3.5e, TSP | Max-Traveling-Salesman-Problem; can go back to vertex 0 early; use DP bitmask | 60 | 6.4 |
| pokemongogo | pokemongogo |
3.5e, TSP | DP TSP variant; there can be more than one Pokemon in the same location | 154 | 5.0 |
| race | race |
3.5e, TSP | try all possible subset of locations; run DP TSP variant from start to ending to see if the plan is doable; keep the bes... | 65 | 7.5 |
| absurdistan3 | absurdistan3 |
4.6e, Bipartite Graph | can be modeled as MCBM; or greedy graph construction with PQ | 312 | 5.6 |
| bookclub | bookclub |
4.6e, Bipartite Graph | check if perfect MCBM is possible | 307 | 4.5 |
| elementarymath | elementarymath |
4.6e, Bipartite Graph | left set: (a, b); right set: possible scores; possible if MCBM = n; use long long | 365 | 5.1 |
| escapeplan | escapeplan |
4.6e, Bipartite Graph | left set: robots; right set: holes; 3 version of similar bipartite graphs; MCBM | 98 | 5.7 |
| flippingcards | flippingcards |
4.6e, Bipartite Graph | left set: n card numbers; right set: 2*n picture numbers; possible if MCBM = n; need fast algorithm | 169 | 7.0 |
| gopher2 | gopher2 |
4.6e, Bipartite Graph | MCBM; also available at UVa 10080 - Gopher II | 337 | 4.3 |
| paintball | paintball |
4.6e, Bipartite Graph | very similar with bookclub | 335 | 4.3 |
| pianolessons | pianolessons |
4.6e, Bipartite Graph | straightforward MCBM | 151 | 4.5 |
| councilling | councilling |
8.4a, Network Flow, Standard | matching; max flow; print the assignment; also available at UVa 10511 - Councilling | 89 | 7.1 |
| dutyscheduler | dutyscheduler |
8.4a, Network Flow, Standard | try all possible (small range of answers); assignment problem; matching with capacity; max flow | 94 | 3.8 |
| jupiter | jupiter |
8.4a, Network Flow, Standard | good modeling problem; a good exercise for those who wants to master max flow modeling | 150 | 5.8 |
| maxflow | maxflow |
8.4a, Network Flow, Standard | standard max flow problem for practice; print edges used in the max flow | 531 | 6.3 |
| mazemovement | mazemovement |
8.4a, Network Flow, Standard | use gcd for all pairs of vertices to construct the flow graph; then it is just a standard max flow problem | 135 | 4.4 |
| mincut | mincut |
8.4a, Network Flow, Standard | standard min cut problem for practice; print vertices reachable from source s after max flow | 293 | 4.1 |
| piano | piano |
8.4a, Network Flow, Standard | good modeling problem; afterwards it is just a standard max flow problem | 230 | 4.1 |
| tomography | tomography |
8.4a, Network Flow, Standard | max flow; somewhat assignment problem; matching with capacity; bipartite graph: left-set: rows/right-set: col; can also ... | 239 | 3.8 |
| waif | waif |
8.4a, Network Flow, Standard | two layers of graph matching; with capacity; use max flow solution | 159 | 2.7 |
| water | water |
8.4a, Network Flow, Standard | max flow on undirected flow graph; add edges; rerun max flow K times (short) | 49 | 4.5 |
| avoidingtheapocalypse | avoidingtheapocalypse |
8.4b, Network Flow, Variants | interesting max flow modeling; blow the vertices based on time | 191 | 4.4 |
| budget | budget |
8.4b, Network Flow, Variants | max flow with lower bound | 66 | 6.8 |
| chesscompetition | chesscompetition |
8.4b, Network Flow, Variants | baseball elimination problem; similar to Kattis - unfairplay | 87 | 4.9 |
| congest | congest |
8.4b, Network Flow, Variants | LA 6395 - World Finals StPetersburg13; compute SSSP from downtown to other vertices; repeated edge-disjoint path computa... | 256 | 3.7 |
| conveyorbelts | conveyorbelts |
8.4b, Network Flow, Variants | max flow; blow up the vertices K times; reroute edges | 89 | 3.7 |
| copsandrobbers | copsandrobbers |
8.4b, Network Flow, Variants | min cut; similar to Kattis - thekingofthenorth | 125 | 3.7 |
| darkness | darkness |
8.4b, Network Flow, Variants | interesting min cut problem; each light source affects all other cells at x and y units away (the z is always H); cost i... | 28 | 6.5 |
| floodingfields | floodingfields |
8.4b, Network Flow, Variants | similar with UVa 11380; must be very careful | 48 | 5.5 |
| landscaping | landscaping |
8.4b, Network Flow, Variants | min cut; hard to spot the required modeling | 70 | 6.0 |
| marchofpenguins | marchofpenguins |
8.4b, Network Flow, Variants | max flow modeling; vertex capacities; also see UVa 11380; also available at UVa 12125 - March of the Penguins | 68 | 3.8 |
| neutralground | neutralground |
8.4b, Network Flow, Variants | min cut; similar to Kattis - thekingofthenorth | 28 | 6.0 |
| thekingofthenorth | thekingofthenorth |
8.4b, Network Flow, Variants | interesting min cut problem | 193 | 5.0 |
| transportation | transportation |
8.4b, Network Flow, Variants | max flow with vertex capacities | 165 | 5.6 |
| unfairplay | unfairplay |
8.4b, Network Flow, Variants | baseball elimination problem; similar to Kattis - chesscompetition; need to print solution too | 89 | 4.7 |
| balanceddiet | balanceddiet |
8.6a, NP-hard/C, small, E | PARTITION; n ≤ 20; use DP SUBSET-SUM style | 316 | 4.0 |
| equalsumseasy | equalsumseasy |
8.6a, NP-hard/C, small, E | PARTITION; generate all possible subsets with bitmask; use set to record which sums have been computed | 474 | 2.3 |
| flowfree | flowfree |
8.6a, NP-hard/C, small, E | brute force combination 3^10 or 4^8; then LONGEST-PATH problem on non DAG between two end points of the same color | 109 | 4.4 |
| font | font |
8.6a, NP-hard/C, small, E | count number of possible SET-COVERs; use 2^N backtracking; but use bitmask to represent small set of covered letters | 199 | 4.2 |
| satisfiability | satisfiability |
8.6a, NP-hard/C, small, E | SAT(isfiability); n ≤ 20; try all possible subsets | 244 | 3.8 |
| socialadvertising | socialadvertising |
8.6a, NP-hard/C, small, E | MIN-DOMINATING-SET/MIN-SET-COVER; n ≤ 20; use compact Adjacency Matrix technique | 59 | 5.1 |
| tightfitsudoku | tightfitsudoku |
8.6a, NP-hard/C, small, E | SUDOKU variant; backtracking + pruning | 87 | 4.2 |
| vivoparc | vivoparc |
8.6a, NP-hard/C, small, E | GRAPH-COLORING on medium-sized graph; only 4 colors are used in this problem; backtracking | 151 | 5.1 |
| beanbag | beanbag |
8.6b, NP-hard/C, small, H | SET-COVER problem; T farmers can collude to give Jack the hardest possible subset of beans to be given freely to Jack | 119 | 4.9 |
| busplanning | busplanning |
8.6b, NP-hard/C, small, H | MIN-CLIQUE-COVER; DP bitmask over sets | 91 | 5.4 |
| coloring | coloring |
8.6b, NP-hard/C, small, H | GRAPH-COLORING; n ≤ 11; greedily set vertex 0 to have color 0 to reduce max N to 10; backtracking | 313 | 4.8 |
| mapcolouring | mapcolouring |
8.6b, NP-hard/C, small, H | GRAPH-COLORING; n ≤ 16; DP over sets; O(3^n); Subset of vertices that are Independent can be 1-colored | 200 | 5.2 |
| perfectskyline | perfectskyline |
8.6b, NP-hard/C, small, H | N, S ≤ 15; SUBSET-SUM backtracking with bitmasks | 39 | 4.1 |
| programmingteamselection | programmingteamselection |
8.6b, NP-hard/C, small, H | PARTITION-INTO-TRIANGLES; prune if #students % 3 != 0; generate up to m/3 teams; backtracking with memo | 64 | 7.2 |
| tugofwar | tugofwar |
8.6b, NP-hard/C, small, H | PARTITION; DP Knapsack with optimization to avoid TLE; also available at UVa 10032 - Tug of War | 117 | 7.4 |
| antennaplacement | antennaplacement |
8.6c, NP-hard/C, special, E | MIS: V-MCBM; also available at UVa 10349 - Antenna Placement | 36 | 5.2 |
| bilateral | bilateral |
8.6c, NP-hard/C, special, E | MIN-VERTEX-COVER on Bipartite Graph; MCBM; Konig's theorem that can handle the 1009 case correctly | 43 | 6.5 |
| bookcircle | bookcircle |
8.6c, NP-hard/C, special, E | left set: boys; right set: girls; add edge (i, j) if boy i reads same book as girl j; MIN-VERTEX-COVER on Bipartite Grap... | 137 | 4.4 |
| catvsdog | catvsdog |
8.6c, NP-hard/C, special, E | LA 4288 - NorthwesternEurope08; MIS; also available at UVa 12168 - Cat vs. Dog | 199 | 5.5 |
| citrusintern | citrusintern |
8.6c, NP-hard/C, special, E | modified MIN-DOMINATING-SET on tree where two adjacent vertices cannot be both inside the Dominating Set | 169 | 3.6 |
| countingclauses | countingclauses |
8.6c, NP-hard/C, special, E | special case of 3-SAT; a bluffing task | 480 | 1.7 |
| cross | cross |
8.6c, NP-hard/C, special, E | run special heuristics of the SUDOKU puzzle | 273 | 3.9 |
| europeantrip | europeantrip |
8.6c, NP-hard/C, special, E | STEINER-TREE with 3 terminal vertices and up to 1 Steiner point; we can use two ternary searches | 297 | 3.3 |
| guardianofdecency | guardianofdecency |
8.6c, NP-hard/C, special, E | LA 3415 - NorthwesternEurope05; MIS; also available at UVa 12083 - Guardian of Decency | 45 | 6.3 |
| reactivity | reactivity |
8.6c, NP-hard/C, special, E | verify if a HAMILTONIAN-PATH exists in the DAG; find one topological sort of the DAG; verify if it is the only one in li... | 280 | 4.0 |
| airports | airports |
8.6d, NP-hard/C, special, H | MIN-PATH-COVER; on DAG; MCBM | 92 | 6.4 |
| eastereggs | eastereggs |
8.6d, NP-hard/C, special, H | BSTA; MAX-INDEPENDENT-SET on Bipartite Graph; V-MCBM | 82 | 5.2 |
| ironcoal | ironcoal |
8.6d, NP-hard/C, special, H | STEINER-TREE with 3 terminal vertices and up to 1 Steiner point; SSSP on unweighted graph; BFS; similar to Kattis - jail... | 216 | 5.0 |
| itcanbearranged | itcanbearranged |
8.6d, NP-hard/C, special, H | MIN-PATH-COVER; on DAG; weighted; Max Flow | 50 | 5.1 |
| jailbreak | jailbreak |
8.6d, NP-hard/C, special, H | STEINER-TREE; grid; BFS from 3 vertices: 'outside' and 2 prisoners (open doors independently or meet a Steiner point fir... | 130 | 4.8 |
| joggers | joggers |
8.6d, NP-hard/C, special, H | MIN-VERTEX-COVER on Tree; root tree at vertex 0; limit tree up to depth S/2 | 46 | 6.1 |
| mafija | mafija |
8.6d, NP-hard/C, special, H | MAX-INDEPENDENT-SET; Special case: on Pseudoforest; use Greedy MIS; handle unvisited cycle separately | 100 | 3.7 |
| ridofcoins | ridofcoins |
8.6d, NP-hard/C, special, H | not the minimizing COIN-CHANGE problem; but the maximizing one; greedy pruning; complete search on much smaller instance | 94 | 7.9 |
| taxicab | taxicab |
8.6d, NP-hard/C, special, H | LA 3126 - NorthwesternEurope04; MPC on DAG; also available at UVa 01201 - Taxi Cab Scheme | 38 | 5.5 |
| wedding | wedding |
8.6d, NP-hard/C, special, H | can be modeled as a 2-SAT problem; also available at UVa 11294 - Wedding | 36 | 6.7 |
| aqueducts | aqueducts |
9.kuhn, Kuhn-Munkres | build bipartite graph; weighted MCBM; Hungarian | 51 | 6.0 |
| cheatingatwar | cheatingatwar |
9.kuhn, Kuhn-Munkres | build weighted bipartite graph K26,26; L: Yraglac's card; R: Opponent's card; assign value: 2/1/0; weighted M... | 97 | 3.1 |
| engaging | engaging |
9.kuhn, Kuhn-Munkres | LA 8437 - HoChiMinhCity17; Hungarian; print solution | 135 | 5.8 |
| cheeseifyouplease | cheeseifyouplease |
9.line, Linear Programming | simple Linear Programming problem; use Simplex | 51 | 3.3 |
| maximumrent | maximumrent |
9.line, Linear Programming | basic Linear Programming problem with integer output; we can use simplex algorithm or another simpler solution | 241 | 3.1 |
