Competitive Programming
Use these filters to narrow down your next problem to solve:
OJ: , Topic: , Quality: , Difficulty:
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 when we first entered the hint (thus an outdated 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; but Kattis changes its UI again by end 2023 so this feature is now broken again)
(Almost) all of the easiest 1097 problems (range: [1.1..3.3] points, average at 2.2 points) have hints and solving them all gives you 1097*~2.2 ≥ 2413.4 total Kattis points — The Lower Bound of Programming Contests in the 2020s year 2024.
Tips: You may want to occasionally 'Remove 'Kattis Hint Giver' from Chrome' and re-'Add it back to Chrome' to manually sync this Methods to Solve content with the local cache.
| Kattis | Problem Title | CP4+5 | Hint | DACU | Point |
|---|---|---|---|---|---|
| reachableroads |
 reachableroads |
4.2a, Finding CCs | report number of CC-1 | 892 | 2.1 |
| securitybadge |
securitybadge |
4.2a, Finding CCs | reachability test; clever idea to compress ids | 129 | 7.6 |
| terraces |
terraces |
4.2a, Finding CCs | group cells with similar height together; if it cannot flow to any other component with lower height, add the size of th... | 339 | 3.6 |
| wheresmyinternet |
wheresmyinternet |
4.2a, Finding CCs | check connectivity to vertex 1 | 1716 | 3.7 |
| amoebas |
amoebas |
4.2b, Flood Fill, Easier | easy floodfill | 1079 | 1.8 |
| countingstars |
countingstars |
4.2b, Flood Fill, Easier | basic flood fill problem; count CCs | 1494 | 2.7 |
| fontan |
fontan |
4.2b, Flood Fill, Easier | modified multi-sources BFS/floodfill | 866 | 2.0 |
| gold |
gold |
4.2b, Flood Fill, Easier | flood fill with extra blocking constraint; also available at UVa 11561 - Getting Gold | 735 | 2.2 |
| 10kindsofpeople |
10kindsofpeople |
4.2c, Flood Fill, Harder | intelligent flood fill; just run once to avoid TLE as there are many queries | 2380 | 3.9 |
| coast |
coast |
4.2c, Flood Fill, Harder | intelligent flood fill; just run once to avoid TLE as there are many queries | 1339 | 3.2 |
| islands3 |
islands3 |
4.2c, Flood Fill, Harder | optimistic flood fill; assume all Cs are Ls | 936 | 2.1 |
| brexit |
brexit |
4.2d, Topological Sort | toposort; chain reaction; modified Kahn's algorithm | 826 | 3.6 |
| builddeps |
builddeps |
4.2d, Topological Sort | the graph is acyclic; toposort with DFS from the changed file | 626 | 4.7 |
| conservation |
conservation |
4.2d, Topological Sort | modified Kahn's algorithm; greedily process all steps in a certain lab before alternating to the other lab | 133 | 4.2 |
| pickupsticks |
pickupsticks |
4.2d, Topological Sort | cycle check + toposort if DAG; also available at item UVa 11686 - Pick up sticks | 373 | 4.7 |
| hoppers |
hoppers |
4.2e, Graph Properties Check | the answer is number of CC-1 if there is at least one non-bipartite component in the graph; or number of CC otherwise | 234 | 3.9 |
| molekule |
molekule |
4.2e, Graph Properties Check | undirected tree is also Bipartite/bi-colorable; bi-color it with 0 and 1; direct all edges from 0 to 1 (or vice versa) | 175 | 3.5 |
| runningmom |
runningmom |
4.2e, Graph Properties Check | find a cycle in a directed graph | 591 | 3.8 |
| torn2pieces |
torn2pieces |
4.2e, Graph Properties Check | construct graph from strings; traversal from source to target; reachability check; print path | 1115 | 3.6 |
| birthday |
birthday |
4.2f, Cut Vertices/Bridges | check if the input graph contains any bridge; N is small though so weaker solution can still be accepted | 323 | 4.3 |
| caveexploration |
caveexploration |
4.2f, Cut Vertices/Bridges | find size of bi-connected components that contains vertex 0; identify the bridges | 848 | 3.3 |
| gymleadersterritory |
gymleadersterritory |
4.2f, Cut Vertices/Bridges | if all edges connected to vertex k are bridges, then `YES`; otherwise `NO` | 165 | 3.5 |
| intercept |
intercept |
4.2f, Cut Vertices/Bridges | Articulation Points in SSSP Spanning DAG; clever modification of Dijkstra's | 112 | 6.6 |
| cantinaofbabel |
cantinaofbabel |
4.2g, Finding SCCs | build directed graph 'can_speak'; compute the largest SCC of 'can_speak'; keep this largest SCC | 1294 | 3.2 |
| dominos |
dominos |
4.2g, Finding SCCs | count the number of SCCs without incoming edge from a vertex outside that SCC; also available at UVa 11504 - Dominos | 248 | 6.2 |
| equivalences |
equivalences |
4.2g, Finding SCCs | contract input directed graph into SCCs; count SCCs that have in-/out-degrees = 0; report the max | 281 | 5.4 |
| reversingroads |
reversingroads |
4.2g, Finding SCCs | if #SCC = 1, print 'valid'; or try reversing one of the m directed edges until we either have #SCC = 1, or print 'invali... | 640 | 3.7 |
| dominoes2 |
dominoes2 |
4.2h, Really Ad Hoc | unlike UVa 11504, we treat SCCs as CCs; also available at UVa 11518 - Dominos 2 | 599 | 3.3 |
| faultyrobot |
faultyrobot |
4.2h, Really Ad Hoc | interesting graph traversal variant; add one more state to each vertex: bug_used | 556 | 3.6 |
| promotions |
promotions |
4.2h, Really Ad Hoc | modified DFS; special graph; DAG; also available at UVa 13015 - Promotions | 129 | 5.5 |
| succession |
succession |
4.2h, Really Ad Hoc | (upwards) traversal of family DAG; use unordered_maps; make the founder has very large starting blood to avoid fraction | 165 | 3.1 |
| cats |
cats |
4.3a, MST, Standard | standard MST | 456 | 4.1 |
| islandhopping |
islandhopping |
4.3a, MST, Standard | MST on small complete graph | 440 | 3.0 |
| lostmap |
lostmap |
4.3a, MST, Standard | actually just a standard MST problem | 782 | 2.1 |
| minspantree |
minspantree |
4.3a, MST, Standard | very standard MST problem; check if a spanning tree is formed; also output the edges in any spanning tree in lexicograph... | 862 | 4.0 |
| millionairemadness |
millionairemadness |
4.3b, MST, Variants | MiniMax path problem | 649 | 2.4 |
| muddyhike |
muddyhike |
4.3b, MST, Variants | MiniMax path problem | 209 | 3.9 |
| naturereserve |
naturereserve |
4.3b, MST, Variants | Prim's algorithm from multiple sources | 180 | 4.6 |
| buttonbashing |
buttonbashing |
4.4a, SSSP, BFS, Easier | very similar to UVa 12160 | 728 | 3.4 |
| horror |
horror |
4.4a, SSSP, BFS, Easier | SSSP from all sources = horror movies; report lowest ID with the highest unweighted SSSP distance | 500 | 3.3 |
| fire2 |
fire2 |
4.4b, SSSP, BFS, Medium | very similar to UVa 11624 | 395 | 4.2 |
| lost |
lost |
4.4b, SSSP, BFS, Medium | interesting twist of BFS/SSSP spanning tree | 269 | 4.7 |
| mallmania |
mallmania |
4.4b, SSSP, BFS, Medium | multi-sources BFS from m1; get minimum at border of m2; also available at UVa 11101 - Mall Mania | 48 | 4.9 |
| oceancurrents |
oceancurrents |
4.4b, SSSP, BFS, Medium | 0/1-weighted SSSP; BFS+deque; also available at UVa 11573 - Ocean Currents | 118 | 5.4 |
| grasshopper |
grasshopper |
4.4c, Knight Moves, BFS | BFS on implicit Knight jump graph | 136 | 4.0 |
| hidingplaces |
hidingplaces |
4.4c, Knight Moves, BFS | SSSP from (r, c); find cells with max distance; print | 607 | 1.9 |
| flowerytrails |
flowerytrails |
4.4e, SSSP, Dijkstra, Easier | Dijkstra's; record predecessor graph as there can be multiple shortest paths; also available at UVa 12878 - Flowery Trai... | 305 | 3.9 |
| shortestpath1 |
shortestpath1 |
4.4e, SSSP, Dijkstra, Easier | very standard Dijkstra's problem | 1470 | 3.5 |
| shortestpath2 |
shortestpath2 |
4.4e, SSSP, Dijkstra, Easier | Dijkstra's with modification; edges only available periodically; be careful with P = 0 case | 423 | 3.9 |
| texassummers |
texassummers |
4.4e, SSSP, Dijkstra, Easier | Dijkstra's; complete weighted graph; print path | 97 | 4.0 |
| blockcrusher |
blockcrusher |
4.4g, SSSP, Dijkstra, Harder | Dijkstra's from top row to bottom row (or vice versa); print path | 257 | 5.1 |
| emptyingbaltic |
emptyingbaltic |
4.4g, SSSP, Dijkstra, Harder | Dijkstra's variant; grow spanning tree from drain/source | 287 | 5.4 |
| invasion |
invasion |
4.4g, SSSP, Dijkstra, Harder | SSSP with multiple and successive sources; multiple calls of Dijkstra's (gets lighter each time if pruned properly) | 46 | 4.3 |
| visualgo |
visualgo |
4.4g, SSSP, Dijkstra, Harder | Dijkstra's produces SSSP spanning DAG if there are multiple shortest paths from s to t; counting paths on DAG | 496 | 3.4 |
| hauntedgraveyard |
hauntedgraveyard |
4.4h, SSSP, Bellman-Ford | Bellman-Ford; negative cycle check needed | 95 | 8.2 |
| shortestpath3 |
shortestpath3 |
4.4h, SSSP, Bellman-Ford | Bellman-Ford; do DFS/BFS from vertices that are part of any negative cycle | 524 | 5.1 |
| xyzzy |
xyzzy |
4.4h, SSSP, Bellman-Ford | check 'positive' cycle; check connectedness; also available at UVa 10557 | 152 | 6.7 |
| allpairspath |
allpairspath |
4.5a, APSP, Standard | basic Floyd-Warshall; tricky negative cycle checks | 772 | 5.5 |
| importspaghetti |
importspaghetti |
4.5a, APSP, Standard | smallest cycle; print path by breaking the self-loop into i - other vertex j - i | 292 | 5.1 |
| transportationplanning |
transportationplanning |
4.5a, APSP, Standard | APSP; FW; for each unused edge, use it and see how much distance is reduced; get minimum; O(n^4) | 65 | 3.9 |
| arbitrage |
arbitrage |
4.5b, APSP, Variants | arbitrage problem; similar to UVa 00104 and 00436 | 324 | 3.3 |
| kastenlauf |
kastenlauf |
4.5b, APSP, Variants | n ≤ 100; Warshall's transitive closure problem | 713 | 3.8 |
| secretchamber |
secretchamber |
4.5b, APSP, Variants | LA 8047 - WorldFinals RapidCity17; Warshall's transitive closure; also available at UVa 01757 - Secret Chamber ... | 1187 | 2.2 |
| fibtour |
fibtour |
4.6a, S/Longest Paths on DAG | only ~90 Fibonacci numbers not more than 10^18; LONGEST-PATH on DAG problem; special case for first two Fibonacci number... | 105 | 6.4 |
| mravi |
mravi |
4.6a, S/Longest Paths on DAG | reverse edge directions to change the input tree into a DAG; find longest path from leaf that contains ant to root | 197 | 2.7 |
| safepassage |
safepassage |
4.6a, S/Longest Paths on DAG | SSSP; implicit DAG; s: (cloak_pos, bitmask); try all ways to go back and forth between gate and dorm; report minimum | 387 | 4.9 |
| compositions |
compositions |
4.6b, Counting Paths, Easier | LA 7365 - Greater NY15; s: (N_left); t: try all values, skip some numbers | 160 | 2.3 |
| robotsonagrid |
robotsonagrid |
4.6b, Counting Paths, Easier | counting paths in implicit DAG | 147 | 4.3 |
| runningsteps |
runningsteps |
4.6b, Counting Paths, Easier | LA 7360 - Greater NY15; s: (leg, l2, r2, l1, r1); t: left/right leg 1/2 steps; use unordered_map as memo table; use prun... | 168 | 2.6 |
| scenes |
scenes |
4.6b, Counting Paths, Easier | s: (pos, ribbon_left); t: try all possible heights; ignore the flat scenes first and subtract those cases at the end | 407 | 3.6 |
| cardmagic |
cardmagic |
4.6c, Conversion to DAG | s: (deck, tgt_left); t: val 1 to K ≤ tgt_left | 133 | 3.9 |
| drinkresponsibly |
drinkresponsibly |
4.6c, Conversion to DAG | s: (cur_drink, money_left, u_left); be careful with precision errors; print solution | 98 | 4.2 |
| maximizingwinnings |
maximizingwinnings |
4.6c, Conversion to DAG | separate the maximizing and minimizing problem; s: (cur_room, turns_left); t: go to other room or stay | 193 | 3.9 |
| adjoin |
adjoin |
4.6d, Tree | the key parts are finding tree diameter and its center (along that diameter); also see UVa 11695 | 373 | 5.3 |
| flight |
flight |
4.6d, Tree | cut the worst edge along the tree diameter; link two centers; also available at UVa 11695 - Flight Planning | 46 | 6.3 |
| tourists |
tourists |
4.6d, Tree | APSP on Tree (special requirements); LCA | 431 | 3.8 |
| bookclub |
bookclub |
4.6e, Bipartite Graph | check if perfect MCBM is possible | 307 | 4.5 |
| 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 |
| catenyms |
catenyms |
4.6f, Eulerian Graph | Euler graph property check; 26 vertices; directed non simple graph; printing the Euler tour in lexicographic order | 67 | 7.1 |
| eulerianpath |
eulerianpath |
4.6f, Eulerian Graph | Euler graph property check; directed graph; printing the Euler tour | 219 | 5.6 |
| railroad2 |
railroad2 |
4.6f, Eulerian Graph | x-shaped level junctions have even degrees - ignore X; y-shaped switches have degree 3 - Y has to be even | 2188 | 1.4 |
