Competitive Programming

Methods to Solve (2000-present)

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).

Column Point is only used in Kattis (and simulated in LeetCode) online judge.

All OJ Problem Title CP4+5 Hint DACU Point
00111 Fetching from uHunt 3.5c, LIS be careful of the ranking system 0.0
00231 Fetching from uHunt 3.5c, LIS straightforward 0.0
00437 Fetching from uHunt 3.5c, LIS can be modeled as LIS 0.0
00481 Fetching from uHunt 3.5c, LIS O(n log k) LIS+solution 0.0
00497 Fetching from uHunt 3.5c, LIS solution must be printed 0.0
01196 Fetching from uHunt 3.5c, LIS LA 2815 - Kaohsiung03; sort all the blocks in increasing L[i]; then we get the classical LIS problem 0.0
10131 Fetching from uHunt 3.5c, LIS sort elephants based on decreasing IQ; LIS on increasing weight 0.0
10154 Fetching from uHunt 3.5c, LIS LIS variant 0.0
10534 Fetching from uHunt 3.5c, LIS must use O(n log k) LIS twice 0.0
11368 Fetching from uHunt 3.5c, LIS sort in one dimension; Dilworth's theorem; LIS in the other; also available at Kattis - nesteddolls 0.0
11456 Fetching from uHunt 3.5c, LIS max(LIS(i)+LDS(i)-1), ∀i ∈ [0...n-1]; also available at Kattis - trainsorting 0.0
11790 Fetching from uHunt 3.5c, LIS combination of LIS LDS; weighted 0.0
alphabet alphabet 3.5c, LIS find LIS of a short string; the answer is 26-LIS_length 666 3.2
increasingsubsequence increasingsubsequence 3.5c, LIS LIS; n ≤ 200$; print lexicographically smallest solution, 99% similar to 'longincsubseq' 352 4.1
lc0300 to replace with LeetCode link soon... 3.5c, LIS classic LIS problem; top-100-liked; top-interview-150 0 4.0
lc0334 to replace with LeetCode link soon... 3.5c, LIS LIS problem with a very small tweak; leetcode-75 0 4.0
lc0646 to replace with LeetCode link soon... 3.5c, LIS LIS problem; this time comparing pairs 0 4.0
lc0673 to replace with LeetCode link soon... 3.5c, LIS counting version of LIS 0 4.0
longincsubseq longincsubseq 3.5c, LIS standard O(n log k) LIS; print any solution 579 5.7
manhattanmornings manhattanmornings 3.5c, LIS utilize symmetries to simplify the problem; then run LIS variant in O(N log K) 154 4.7
nesteddolls nesteddolls 3.5c, LIS sort in one dimension; Dilworth's theorem; LIS in the other; also available at UVa 11368 - Nested Dolls 115 7.1
studentsko studentsko 3.5c, LIS sort skills of N players; map them to K teams; find LNDS in O(N log K); answer is N-LNDS 124 3.9
trainsorting trainsorting 3.5c, LIS max(LIS(i)+LDS(i)-1), ∀i ∈ [0...n-1]; also available at UVa 11456 522 5.4
00431 Fetching from uHunt 3.5d, 0-1 KNAPSACK/SS classic 0-1 Knapsack Problem; output any optimal solution as there is a special checker for this problem 0.0
00562 Fetching from uHunt 3.5d, 0-1 KNAPSACK/SS use a one dimensional table 0.0
00990 Fetching from uHunt 3.5d, 0-1 KNAPSACK/SS print the solution 0.0
01213 Fetching from uHunt 3.5d, 0-1 KNAPSACK/SS LA 3619 - Yokohama06; extension of 0-1 KNAPSACK; s: (id, remN, remK) instead of s: (id, remN) 0.0
10130 Fetching from uHunt 3.5d, 0-1 KNAPSACK/SS basic 0-1 Knapsack problem 0.0
10261 Fetching from uHunt 3.5d, 0-1 KNAPSACK/SS s: (current_car; left; right) 0.0
10616 Fetching from uHunt 3.5d, 0-1 KNAPSACK/SS input can be -ve; use long long 0.0
10664 Fetching from uHunt 3.5d, 0-1 KNAPSACK/SS Subset Sum 0.0
10690 Fetching from uHunt 3.5d, 0-1 KNAPSACK/SS DP Subset Sum with negative offset technique; with addition of simple math 0.0
10819 Fetching from uHunt 3.5d, 0-1 KNAPSACK/SS 0-1 knapsack with 'credit card' twist 0.0
11003 Fetching from uHunt 3.5d, 0-1 KNAPSACK/SS try all max weight from 0 to max(weight[i] capacity[i]); forall i in [0..n-1]; if a max weight is known; how many boxes ... 0.0
11341 Fetching from uHunt 3.5d, 0-1 KNAPSACK/SS s: (id; h_learned; h_left); t: learn module 'id' by 1 hour or skip it 0.0
11566 Fetching from uHunt 3.5d, 0-1 KNAPSACK/SS KNAPSACK variant: double each dim sum; add one parameter to see if we have bought too many dishes 0.0
11658 Fetching from uHunt 3.5d, 0-1 KNAPSACK/SS s: (id; share); t: form/ignore coalition with id 0.0
11832 Fetching from uHunt 3.5d, 0-1 KNAPSACK/SS interesting DP; s: (id; val); use offset to handle negative numbers; t: plus or minus; print solution 0.0
12621 Fetching from uHunt 3.5d, 0-1 KNAPSACK/SS DP Subset Sum; simplify the multiple of 10 0.0
knapsack knapsack 3.5d, 0-1 KNAPSACK/SS basic DP KNAPSACK; print the solution 687 4.8
lc0377 to replace with LeetCode link soon... 3.5d, 0-1 KNAPSACK/SS counting version of SUBSET-SUM 0 4.0
lc0416 to replace with LeetCode link soon... 3.5d, 0-1 KNAPSACK/SS classic Subset-Sum; top-100-liked 0 4.0
lc0474 to replace with LeetCode link soon... 3.5d, 0-1 KNAPSACK/SS Knapsack; skip or take a string 0 4.0
lc2291 to replace with LeetCode link soon... 3.5d, 0-1 KNAPSACK/SS PREMIUM - hint hidden 0 4.0
muzicari muzicari 3.5d, 0-1 KNAPSACK/SS 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.5d, 0-1 KNAPSACK/SS brute force all possible sums; use DP SUBSET-SUM on each hotdog and bun packs; clever problem 499 4.4
orders orders 3.5d, 0-1 KNAPSACK/SS interesting KNAPSACK variant; print the solution 713 4.5
presidentialelections presidentialelections 3.5d, 0-1 KNAPSACK/SS pre-process the input to discard non winnable states; be careful of negative total voters; then standard DP KNAPSACK 116 5.7
00147 Fetching from uHunt 3.5e, COIN-CHANGE similar to UVa 357 and 674 0.0
00166 Fetching from uHunt 3.5e, COIN-CHANGE two coin change variants in one problem 0.0
00242 Fetching from uHunt 3.5e, COIN-CHANGE LA 5181 - WorldFinals Nashville95; Complete Search + DP Coin-Change 0.0
00357 Fetching from uHunt 3.5e, COIN-CHANGE similar to UVa 147 and 674 0.0
00674 Fetching from uHunt 3.5e, COIN-CHANGE basic coin change problem 0.0
10313 Fetching from uHunt 3.5e, COIN-CHANGE modified coin change and DP 1D range sum 0.0
10448 Fetching from uHunt 3.5e, COIN-CHANGE after dealing with traversal on tree; you can reduce the original problem into coin change; not trivial 0.0
11137 Fetching from uHunt 3.5e, COIN-CHANGE use long long 0.0
11259 Fetching from uHunt 3.5e, COIN-CHANGE part of the problem is DP COIN-CHANGE with restricted number of coins per type; inclusion-exclusion 0.0
11517 Fetching from uHunt 3.5e, COIN-CHANGE a variation to the coin change problem; also available at Kattis - exactchange2 0.0
bagoftiles bagoftiles 3.5e, 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.5e, COIN-CHANGE complete search possible range of counter examples; do both greedy COIN-CHANGE and DP COIN-CHANGE 502 5.7
exactchange2 exactchange2 3.5e, COIN-CHANGE a variation to the Coin-Change problem; also available at UVa 11517 - Exact Change 708 5.4
lc0322 to replace with LeetCode link soon... 3.5e, COIN-CHANGE COIN-CHANGE; top-100-liked; top-interview-150 0 4.0
lc0518 to replace with LeetCode link soon... 3.5e, COIN-CHANGE Coin-Change; the counting variant 0 4.0
00216 Fetching from uHunt 3.5f, TSP LA 5155 - WorldFinals KansasCity92; DP TSP problem; but still solvable with backtracking 0.0
01281 Fetching from uHunt 3.5f, TSP LA 6028 - WorldFinals Warsaw12; DP TSP variant; also available at Kattis - bustour 0.0
10496 Fetching from uHunt 3.5f, TSP DP or recursive backtracking with sufficient pruning; also available at Kattis - beepers 0.0
11795 Fetching from uHunt 3.5f, TSP DP TSP variant; counting paths on DAG; DP+bitmask; let Mega Buster owned by a dummy 'Robot 0' 0.0
12841 Fetching from uHunt 3.5f, TSP simply find and print the lexicographically smallest Hamiltonian path; use DP-TSP technique 0.0
beepers beepers 3.5f, TSP DP or recursive backtracking with sufficient pruning; also available at UVa 10496 - Collecting Beepers 196 4.6
bustour bustour 3.5f, TSP LA 6028 - WorldFinals Warsaw12; DP TSP variant; also available at UVa 01281 - Bus Tour 124 6.1
cycleseasy cycleseasy 3.5f, TSP Count number of HAMILTONIAN-TOURs 108 4.1
errands errands 3.5f, TSP map location names to integer indices; DP TSP 51 7.0
maximizingyourpay maximizingyourpay 3.5f, TSP Max-Traveling-Salesman-Problem; can go back to vertex 0 early; use DP bitmask 60 6.4
pokemongogo pokemongogo 3.5f, TSP DP TSP variant; there can be more than one Pokemon in the same location 154 5.0
race race 3.5f, 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
00103 Fetching from uHunt 4.7a, S/Longest Paths on DAG longest paths on DAG; backtracking OK 0.0
00452 Fetching from uHunt 4.7a, S/Longest Paths on DAG LONGEST-PATH on DAG 0.0
10000 Fetching from uHunt 4.7a, S/Longest Paths on DAG longest paths on DAG; backtracking OK 0.0
10051 Fetching from uHunt 4.7a, S/Longest Paths on DAG longest paths on DAG; DP 0.0
10259 Fetching from uHunt 4.7a, S/Longest Paths on DAG longest paths on implicit DAG; DP 0.0
10285 Fetching from uHunt 4.7a, S/Longest Paths on DAG longest paths on implicit DAG; however; the graph is small enough for recursive backtracking solution 0.0
10350 Fetching from uHunt 4.7a, S/Longest Paths on DAG shortest paths; implicit DAG; DP 0.0
baas baas 4.7a, S/Longest Paths on DAG try all possible vertex to be 'optimized'; LONGEST-PATH on DAG 55 4.5
delftdistance delftdistance 4.7a, S/Longest Paths on DAG SSSP on DAG (4 N/E/S/W vertices on each square/round buildings); t: two straights, two 90 degrees straight turns, two ro... 161 3.8
excavatorexpedition excavatorexpedition 4.7a, S/Longest Paths on DAG s: (pos); t: try all directed edge; +1/-1 weight; LONGEST-PATH on DAG problem; be careful of negative final answer 70 5.4
fibtour fibtour 4.7a, 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
lc0064 to replace with LeetCode link soon... 4.7a, S/Longest Paths on DAG basic SSSP on DAG; top-100-liked; top-interview-150 0 4.0
lc0120 to replace with LeetCode link soon... 4.7a, S/Longest Paths on DAG SSSP on DAG; top-interview-150 0 4.0
lc0329 to replace with LeetCode link soon... 4.7a, S/Longest Paths on DAG find LONGEST-PATH in an implicit DAG; DP 0 6.0
lc0931 to replace with LeetCode link soon... 4.7a, S/Longest Paths on DAG SSSP on implicit DAG; can only go down 0 4.0
lc2684 to replace with LeetCode link soon... 4.7a, S/Longest Paths on DAG find LONGEST-PATH in implicit DAG 0 4.0
monopoly monopoly 4.7a, S/Longest Paths on DAG K, b, r are all irrelevant; vertex value is either +ve (salary) or -ve (tax); LONGEST-PATH on DAG (u < v); exclude so... 69 3.0
mravi mravi 4.7a, 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.7a, 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
savinguniverse savinguniverse 4.7a, S/Longest Paths on DAG s: (cur_SE; Q_pos); t: stay in this search engine or switch to one other; unweighted SSSP on DAG 122 4.7
00825 Fetching from uHunt 4.7b, Counting Paths, Easier counting paths in grid (implicit DAG); DP; similar to UVa 00926 and 11067 0.0
00926 Fetching from uHunt 4.7b, Counting Paths, Easier counting paths in grid (implicit DAG); DP; similar to UVa 825 and 11067 0.0
00986 Fetching from uHunt 4.7b, Counting Paths, Easier counting paths in DAG; DP; s: (x; y; lastmove; peaksfound); t: try NE/SE 0.0
00988 Fetching from uHunt 4.7b, Counting Paths, Easier counting paths in DAG; DP 0.0
10401 Fetching from uHunt 4.7b, Counting Paths, Easier counting paths in implicit DAG; DP; s: (col; row); t: next col; avoid 2 or 3 adjacent rows 0.0
10544 Fetching from uHunt 4.7b, Counting Paths, Easier counting paths in implicit DAG 0.0
10564 Fetching from uHunt 4.7b, Counting Paths, Easier counting paths in implicit DAG (top-down); print one solution 0.0
10926 Fetching from uHunt 4.7b, Counting Paths, Easier counting paths in DAG; DP 0.0
11067 Fetching from uHunt 4.7b, Counting Paths, Easier counting paths in grid (implicit DAG); DP; similar to UVa 825 and 926 0.0
11569 Fetching from uHunt 4.7b, Counting Paths, Easier determine the length of one of the longest paths and then count the number of such longest paths in DAG 0.0
11655 Fetching from uHunt 4.7b, Counting Paths, Easier counting paths in DAG and one more similar task: counting the number of vertices involved in the paths 0.0
11957 Fetching from uHunt 4.7b, Counting Paths, Easier counting paths in implicit DAG; DP 0.0
compositions compositions 4.7b, Counting Paths, Easier LA 7365 - Greater NY15; s: (N_left); t: try all values, skip some numbers 160 2.3
gourmeten gourmeten 4.7b, Counting Paths, Easier s: (M_left); t: eat any of the N dishes one more time 378 1.8
helpfulcurrents helpfulcurrents 4.7b, Counting Paths, Easier problem description ensures a DAG; counting path modulo 1000003; output "begin repairs" if Lysias's castle is unreachabl... 51 5.3
lc0062 to replace with LeetCode link soon... 4.7b, Counting Paths, Easier counting paths; DAG; leetcode-75; top-100-liked 0 4.0
lc0063 to replace with LeetCode link soon... 4.7b, Counting Paths, Easier counting paths in DAG with some obstacles; top-interview-150 0 4.0
lc0091 to replace with LeetCode link soon... 4.7b, Counting Paths, Easier counting paths on implicit DAG; single digit that is not 0 or [10..19] or [20..26] 0 4.0
lc1641 to replace with LeetCode link soon... 4.7b, Counting Paths, Easier s: (i, last); counting paths on implicit DAG 0 4.0
marypartitions marypartitions 4.7b, Counting Paths, Easier 3 ≤ m, so we will only use a few power values; counting paths on DAG 245 3.5
rampantgrowth rampantgrowth 4.7b, Counting Paths, Easier can be modeled as counting paths in DAG problem 333 1.8
robotsonagrid robotsonagrid 4.7b, Counting Paths, Easier counting paths in implicit DAG 147 4.3
runningsteps runningsteps 4.7b, 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.7b, 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
00590 Fetching from uHunt 4.7c, Conversion to DAG s: (pos; day_left) 0.0
00607 Fetching from uHunt 4.7c, Conversion to DAG returns pair of information 0.0
00757 Fetching from uHunt 4.7c, Conversion to DAG s: (lake_id, time_left); this time_left is best left as multiple of 5 minutes; output the optimal solution too 0.0
00907 Fetching from uHunt 4.7c, Conversion to DAG s: (pos; night_left) 0.0
00910 Fetching from uHunt 4.7c, Conversion to DAG s: (pos; move_left) 0.0
01025 Fetching from uHunt 4.7c, Conversion to DAG s: (station, cur_t); t: stay until meeting time (if at station N), or either go to right or go to left using any of the ... 0.0
10201 Fetching from uHunt 4.7c, Conversion to DAG s: (pos, fuel_left); also available at Kattis - adventuremoving4 0.0
10271 Fetching from uHunt 4.7c, Conversion to DAG Observation: The 3rd chopstick can be any chopstick; s: (pos, K_left); t: ignore this chopstick, or take this chopstick ... 0.0
10543 Fetching from uHunt 4.7c, Conversion to DAG s: (pos; speech_given) 0.0
10681 Fetching from uHunt 4.7c, Conversion to DAG s: (pos; day_left) 0.0
10702 Fetching from uHunt 4.7c, Conversion to DAG s: (pos; T_left); similar to UVa 12875 0.0
10874 Fetching from uHunt 4.7c, Conversion to DAG s: (row; left/right); t: go left/right 0.0
10913 Fetching from uHunt 4.7c, Conversion to DAG s: (r; c; neg_left; stat); t: down/(left/right) 0.0
11307 Fetching from uHunt 4.7c, Conversion to DAG Min Chromatic Sum; max 6 colors 0.0
11487 Fetching from uHunt 4.7c, Conversion to DAG s: (r; c; cur_food; len); t: 4 dirs 0.0
11545 Fetching from uHunt 4.7c, Conversion to DAG s: (cPos; cTime; cWTime); t: move forward/rest 0.0
11782 Fetching from uHunt 4.7c, Conversion to DAG s: (id; rem_K); t: take root/try left-right subtree 0.0
12875 Fetching from uHunt 4.7c, Conversion to DAG LA 6853 - Bangkok14; similar to UVa 10702; s: (cur_store; cur_concert); t: pick any next store for next concert 0.0
13122 Fetching from uHunt 4.7c, Conversion to DAG s: (pos, K_left); knapsack style DP; jump 1, 2, ..., K_left points; connect with the two points with a line with cost eq... 0.0
adventuremoving4 adventuremoving4 4.7c, Conversion to DAG s: (pos, fuel_left); also available at UVa 10201 - Adventures in Moving - Part IV 315 5.4
cardmagic cardmagic 4.7c, Conversion to DAG s: (deck, tgt_left); t: val 1 to K ≤ tgt_left 133 3.9
drinkresponsibly drinkresponsibly 4.7c, Conversion to DAG s: (cur_drink, money_left, u_left); be careful with precision errors; print solution 98 4.2
maximizingwinnings maximizingwinnings 4.7c, Conversion to DAG separate the maximizing and minimizing problem; s: (cur_room, turns_left); t: go to other room or stay 193 3.9
quantumsuperposition quantumsuperposition 4.7c, Conversion to DAG s: (id, u, step); id is either DAG 1 or DAG 2, u is current vertex, step is the number of step used; t: try all neighbor... 172 6.0
shortestpath4 shortestpath4 4.7c, Conversion to DAG s: (u, vtx_left); t: neighbors of u 76 3.0
00112 Fetching from uHunt 4.7d, Tree backtracking 0.0
00115 Fetching from uHunt 4.7d, Tree tree traversal to determine relationships between vertices 0.0
00122 Fetching from uHunt 4.7d, Tree tree traversal 0.0
00536 Fetching from uHunt 4.7d, Tree reconstructing binary tree from preorder and inorder binary tree traversal 0.0
00548 Fetching from uHunt 4.7d, Tree reconstructing tree from in postorder 0.0
00615 Fetching from uHunt 4.7d, Tree graph property check 0.0
00699 Fetching from uHunt 4.7d, Tree preorder traversal 0.0
00712 Fetching from uHunt 4.7d, Tree simple binary tree traversal variant 0.0
00839 Fetching from uHunt 4.7d, Tree can be viewed as a recursive problem on tree 0.0
10308 Fetching from uHunt 4.7d, Tree diameter of tree 0.0
10459 Fetching from uHunt 4.7d, Tree diameter of tree 0.0
10701 Fetching from uHunt 4.7d, Tree reconstructing tree from pre inorder 0.0
10805 Fetching from uHunt 4.7d, Tree involving diameter of tree 0.0
11131 Fetching from uHunt 4.7d, Tree read tree; produce two postorder traversals 0.0
11234 Fetching from uHunt 4.7d, Tree converting post-order to level-order; binary tree 0.0
11615 Fetching from uHunt 4.7d, Tree counting size of subtrees 0.0
11695 Fetching from uHunt 4.7d, Tree cut the worst edge along the tree diameter; link two centers; also available at Kattis - flight 0.0
12186 Fetching from uHunt 4.7d, Tree the input graph is a tree 0.0
12347 Fetching from uHunt 4.7d, Tree given pre-order traversal of a BST; use BST property to get the BST; output the post-order traversal that BST 0.0
12379 Fetching from uHunt 4.7d, Tree find the diameter of tree first; we only traverse the diameter once and we traverse the other edges twice 0.0
adjoin adjoin 4.7d, Tree the key parts are finding tree diameter and its center (along that diameter); also see UVa 11695 373 5.3
appealtotheaudience appealtotheaudience 4.7d, Tree LONGEST-PATH on tree + greedy matching (strongest player plays the most and so on) 31 3.1
decisions decisions 4.7d, Tree collapse a sub-tree into a super vertex if all f values on its leaves are equal; count size of min BDD tree recursively 151 3.1
flight flight 4.7d, Tree cut the worst edge along the tree diameter; link two centers; also available at UVa 11695 - Flight Planning 46 6.3
frozenrose frozenrose 4.7d, Tree tree traversal; is it better to close the valve that goes in to a vertex u or close subset of valve(s) in subtree of u 56 3.5
kitten kitten 4.7d, Tree simple rooted tree traversal; from a vertex back to root 1278 1.7
lc0690 to replace with LeetCode link soon... 4.7d, Tree custom traversal of a tree from a given source 0 4.0
lc1466 to replace with LeetCode link soon... 4.7d, Tree create undirected tree; traverse from the root 0 to identify the answers; leetcode-75 0 4.0
lc2204 to replace with LeetCode link soon... 4.7d, Tree PREMIUM - hint hidden 0 6.0
mazemakers mazemakers 4.7d, Tree long problem statement to describe a custom 2D grid graph; just a graph traversal: check if all cells are visited and th... 171 2.8
tourists tourists 4.7d, Tree APSP on Tree (special requirements); LCA 431 3.8
whostheboss whostheboss 4.7d, Tree sort; create the tree graph; DFS from root; parent array and size of subtree (a bit of DP) 29 6.1
00663 Fetching from uHunt 4.7e, Bipartite Graph try disallowing an edge to see if MCBM changes; which implies that the edge has to be used 0.0
00670 Fetching from uHunt 4.7e, Bipartite Graph MCBM 0.0
00753 Fetching from uHunt 4.7e, Bipartite Graph initially a non standard matching problem but this problem can be reduced to a simple MCBM problem 0.0
10080 Fetching from uHunt 4.7e, Bipartite Graph MCBM; also available at Kattis - gopher2 0.0
11138 Fetching from uHunt 4.7e, Bipartite Graph a pure MCBM problem 0.0
12644 Fetching from uHunt 4.7e, Bipartite Graph classic MCBM problem wrapped inside a creative problem statement 0.0
12668 Fetching from uHunt 4.7e, Bipartite Graph LA 6525 - LatinAmerica13; split rows/columns due to the presence of pawns; then run MCBM 0.0
absurdistan3 absurdistan3 4.7e, Bipartite Graph can be modeled as MCBM; or greedy graph construction with PQ 312 5.6
bookclub bookclub 4.7e, Bipartite Graph check if perfect MCBM is possible 307 4.5
elementarymath elementarymath 4.7e, Bipartite Graph left set: (a, b); right set: possible scores; possible if MCBM = n; use long long 365 5.1
escapeplan escapeplan 4.7e, Bipartite Graph left set: robots; right set: holes; 3 version of similar bipartite graphs; MCBM 98 5.7
flippingcards flippingcards 4.7e, 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.7e, Bipartite Graph MCBM; also available at UVa 10080 - Gopher II 337 4.3
paintball paintball 4.7e, Bipartite Graph very similar with bookclub 335 4.3
pianolessons pianolessons 4.7e, Bipartite Graph straightforward MCBM 151 4.5
00117 Fetching from uHunt 4.7f, Eulerian Graph Euler tour; get cost of tour 0.0
00291 Fetching from uHunt 4.7f, Eulerian Graph Euler tour on a small graph; backtracking is sufficient 0.0
00302 Fetching from uHunt 4.7f, Eulerian Graph Euler tour; print the tour 0.0
10054 Fetching from uHunt 4.7f, Eulerian Graph printing the Euler tour 0.0
10129 Fetching from uHunt 4.7f, Eulerian Graph Euler Graph property check 0.0
10203 Fetching from uHunt 4.7f, Eulerian Graph the underlying graph is Euler graph 0.0
10596 Fetching from uHunt 4.7f, Eulerian Graph Euler Graph property check 0.0
catenyms catenyms 4.7f, Eulerian Graph Euler graph property check; 26 vertices; directed non simple graph; printing the Euler tour in lexicographic order 67 7.1
eulerian eulerian 4.7f, Eulerian Graph basic Eulerian graph property checks 58 2.9
eulerianpath eulerianpath 4.7f, Eulerian Graph Euler graph property check; directed graph; printing the Euler tour 219 5.6
grandopening grandopening 4.7f, Eulerian Graph false alarm case is trivial; model the movement as a directed graph; check if Eulerian path exists 89 5.9
railroad2 railroad2 4.7f, 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
00259 Fetching from uHunt 8.4a, Network Flow, Standard assignment problem; matching with capacity; similar to UVa 10092; 11045; and 12873; but actually the input constraint is... 0.0
00820 Fetching from uHunt 8.4a, Network Flow, Standard LA 5220 - WorldFinals Orlando00; very basic max flow problem 0.0
10092 Fetching from uHunt 8.4a, Network Flow, Standard assignment problem; matching with capacity; similar to UVa 259; 11045; and 12873 0.0
10511 Fetching from uHunt 8.4a, Network Flow, Standard matching; max flow; print the assignment; also available at Kattis - councilling 0.0
10779 Fetching from uHunt 8.4a, Network Flow, Standard build a flow graph s.t. each augmenting path corresponds to a series of exchange of duplicate stickers; repeat until thi... 0.0
11045 Fetching from uHunt 8.4a, Network Flow, Standard assignment problem; matching with capacity; similar to UVa 259; 10092; and 12873; but actually the input constraint is a... 0.0
11082 Fetching from uHunt 8.4a, Network Flow, Standard very similar to Kattis - tomography 0.0
11167 Fetching from uHunt 8.4a, Network Flow, Standard many edges in the flow graph; compress the capacity-1 edges when possible; use Dinic's 0.0
11418 Fetching from uHunt 8.4a, Network Flow, Standard two layers of graph matching (not really bipartite matching); use max flow solution 0.0
12873 Fetching from uHunt 8.4a, Network Flow, Standard LA 6851 - Bangkok14; assignment problem; similar to UVa 00259, 11045, and 10092; use Dinic's 0.0
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
00563 Fetching from uHunt 8.4b, Network Flow, Variants check whether the maximum number of independent paths on the flow graph equals to b banks 0.0
01242 Fetching from uHunt 8.4b, Network Flow, Variants LA 4271 - Hefei08; to have a necklace; we need to be able to two edge-disjoint s-t flows 0.0
10330 Fetching from uHunt 8.4b, Network Flow, Variants max flow; vertex capacities 0.0
10480 Fetching from uHunt 8.4b, Network Flow, Variants straightforward min cut problem 0.0
11380 Fetching from uHunt 8.4b, Network Flow, Variants max flow modeling with vertex capacities; similar to UVa 12125 0.0
11506 Fetching from uHunt 8.4b, Network Flow, Variants min cut with vertex capacities 0.0
11757 Fetching from uHunt 8.4b, Network Flow, Variants creative problem about min cut; build the flow graph with a bit of simple geometry involving circle; then find the min c... 0.0
11765 Fetching from uHunt 8.4b, Network Flow, Variants interesting min cut variant 0.0
12125 Fetching from uHunt 8.4b, Network Flow, Variants max flow modeling with vertex capacities; similar to UVa 11380; also available at Kattis - marchofpenguins 0.0
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
00193 Fetching from uHunt 8.6a, NP-hard/C, small, E optimization version of Max Independent Set problem on general graph which is NP-Hard with small input 0.0
00539 Fetching from uHunt 8.6a, NP-hard/C, small, E LONGEST-PATH problem; small input/general graph 0.0
00574 Fetching from uHunt 8.6a, NP-hard/C, small, E print all solutions with backtracking 0.0
00624 Fetching from uHunt 8.6a, NP-hard/C, small, E input size is small; backtracking is enough 0.0
00775 Fetching from uHunt 8.6a, NP-hard/C, small, E backtracking suffices as the search space is small; it is more likely to have a HAMILTONIAN-TOUR in a dense graph, so we... 0.0
00989 Fetching from uHunt 8.6a, NP-hard/C, small, E classic SUDOKU puzzle; the small 9x9 instance is solvable with backtracking with pruning; use bitmask to speed up 0.0
10957 Fetching from uHunt 8.6a, NP-hard/C, small, E very similar with UVa 989; if you can solve that one; you can modify your code a bit to solve this one 0.0
11088 Fetching from uHunt 8.6a, NP-hard/C, small, E similar to UVa 10911 but partitioning of three persons to one team; PARTITION-INTO-TRIANGLES 0.0
12455 Fetching from uHunt 8.6a, NP-hard/C, small, E SUBSET-SUM; try all; see the harder UVa 12911 that requires meet in the middle 0.0
balanceddiet balanceddiet 8.6a, NP-hard/C, small, E PARTITION; n ≤ 20; use DP SUBSET-SUM style 316 4.0
countingchocolate countingchocolate 8.6a, NP-hard/C, small, E PARTITION; small instance; DP SUBSET-SUM style 158 4.2
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
01098 Fetching from uHunt 8.6b, NP-hard/C, small, H LA 4793 - WorldFinals Harbin10; HAMILTONIAN-TOUR; backtracking+pruning; meet in the middle 0.0
01217 Fetching from uHunt 8.6b, NP-hard/C, small, H LA 3681 - Kaohsiung06; TSP-like optimization problem; which is NP-Hard; solvable with A*/IDA* 0.0
10032 Fetching from uHunt 8.6b, NP-hard/C, small, H PARTITION; DP Knapsack with optimization to avoid TLE; also available at Kattis - tugofwar 0.0
10125 Fetching from uHunt 8.6b, NP-hard/C, small, H SUBSET-SUM; 4-SUM variant; use unordered_map to map sum of a and b in S and their two indices; also available at Kattis ... 0.0
10160 Fetching from uHunt 8.6b, NP-hard/C, small, H optimization version of Min Vertex Cover on general graph; Dominating Set; which is NP-Hard; strategies: backtracking; s... 0.0
10571 Fetching from uHunt 8.6b, NP-hard/C, small, H hard backtracking problem; it has similar flavor as Su Doku puzzle 0.0
11065 Fetching from uHunt 8.6b, NP-hard/C, small, H optimization version of MAX-INDEPENDENT-SET problem on general graph; also report the number of Independent Sets; bitmas... 0.0
11095 Fetching from uHunt 8.6b, NP-hard/C, small, H optimization version of Min Vertex Cover on general graph which is NP-Hard 0.0
12911 Fetching from uHunt 8.6b, NP-hard/C, small, H SUBSET-SUM; we cannot use DP as 1 ≤ N ≤ 40 and -10^9 ≤ T ≤ 10^9; use meet in the middle 0.0
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
lc0015 to replace with LeetCode link soon... 8.6b, NP-hard/C, small, H one possible way is to hash all numbers and try all-pairs; avoid duplicates; top-100-liked; top-interview-150 0 4.0
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
01194 Fetching from uHunt 8.6c, NP-hard/C, special, E LA 2523 - Beijing02; Min Vertex Cover/MVC 0.0
01347 Fetching from uHunt 8.6c, NP-hard/C, special, E LA 3305 - SoutheasternEurope05; this is the pure version of Bitonic TSP problem; you may want to start from here 0.0
10243 Fetching from uHunt 8.6c, NP-hard/C, special, E this problem can be reduced to the Min Vertex Cover problem on Tree; there is a polynomial DP solution for this variant 0.0
10349 Fetching from uHunt 8.6c, NP-hard/C, special, E MIS: V-MCBM; also available at Kattis - antennaplacement 0.0
10859 Fetching from uHunt 8.6c, NP-hard/C, special, E Min-Vertex-Cover; on several trees; maximize number of edges with its two endpoints covered 0.0
11159 Fetching from uHunt 8.6c, NP-hard/C, special, E MAX-INDEPENDENT-SET; on Bipartite Graph; ans equals to its MCBM 0.0
11357 Fetching from uHunt 8.6c, NP-hard/C, special, E not a pure CNF SAT(isfiability) problem; it is a special case as only one clause needs to be satisfied 0.0
11419 Fetching from uHunt 8.6c, NP-hard/C, special, E MVC; Konig theorem 0.0
12083 Fetching from uHunt 8.6c, NP-hard/C, special, E LA 3415 - NorthwesternEurope05; MIS; also available at Kattis - guardianofdecency 0.0
12168 Fetching from uHunt 8.6c, NP-hard/C, special, E LA 4288 - NorthwesternEurope08; MIS; also available at Kattis - catvsdog 0.0
13115 Fetching from uHunt 8.6c, NP-hard/C, special, E just a SUDOKU solution verifier; an NP-problem 0.0
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
lc0198 to replace with LeetCode link soon... 8.6c, NP-hard/C, special, E MWIS; on line graph; simple DP; leetcode-75; top-100-liked; top-interview-150 0 4.0
lc0213 to replace with LeetCode link soon... 8.6c, NP-hard/C, special, E MWIS; on circular line graph; DP variant 0 4.0
lc0256 to replace with LeetCode link soon... 8.6c, NP-hard/C, special, E PREMIUM - hint hidden 0 4.0
lc0265 to replace with LeetCode link soon... 8.6c, NP-hard/C, special, E PREMIUM - hint hidden 0 6.0
lc0337 to replace with LeetCode link soon... 8.6c, NP-hard/C, special, E MWIS; on tree; DP 0 4.0
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
01086 Fetching from uHunt 8.6d, NP-hard/C, special, H LA 4452 - WorldFinals Stockholm09; can be modeled as a 2-SAT problem 0.0
01096 Fetching from uHunt 8.6d, NP-hard/C, special, H LA 4791 - WorldFinals Harbin10; Bitonic TSP variant; print the actual path 0.0
01184 Fetching from uHunt 8.6d, NP-hard/C, special, H LA 2696 - Dhaka02; MPC on DAG ~ MCBM 0.0
01201 Fetching from uHunt 8.6d, NP-hard/C, special, H LA 3126 - NorthwesternEurope04; MPC on DAG; also available at Kattis - taxicab 0.0
01212 Fetching from uHunt 8.6d, NP-hard/C, special, H LA 3483 - Hangzhou05; MWIS on Bipartite Graph 0.0
01220 Fetching from uHunt 8.6d, NP-hard/C, special, H LA 3794 - Tehran06; Maximum Independent Set (MIS) problem on tree; DP; also check if the MIS is unique 0.0
10319 Fetching from uHunt 8.6d, NP-hard/C, special, H can be modeled as a 2-SAT problem 0.0
11294 Fetching from uHunt 8.6d, NP-hard/C, special, H can be modeled as a 2-SAT problem; also available at Kattis - wedding 0.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
01045 Fetching from uHunt 9.kuhn, Kuhn-Munkres LA 3276 - WorldFinals Shanghai05; try all configurations; weighted matching; pick the best; Kuhn-Munkres 0.0
10746 Fetching from uHunt 9.kuhn, Kuhn-Munkres min weighted bipartite matching 0.0
10888 Fetching from uHunt 9.kuhn, Kuhn-Munkres BFS/SSSP; min weighted bipartite matching 0.0
11553 Fetching from uHunt 9.kuhn, Kuhn-Munkres brute force; DP bitmask; or Hungarian 0.0
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

© 2000-2026 Steven Halim

Share this page in Facebook