Competitive Programming

Methods to Solve (2000-present)

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

Buy Now!

Partner Links