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
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
00663 Fetching from uHunt 4.6e, 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.6e, Bipartite Graph MCBM 0.0
00753 Fetching from uHunt 4.6e, 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.6e, Bipartite Graph MCBM; also available at Kattis - gopher2 0.0
11138 Fetching from uHunt 4.6e, Bipartite Graph a pure MCBM problem 0.0
12644 Fetching from uHunt 4.6e, Bipartite Graph classic MCBM problem wrapped inside a creative problem statement 0.0
12668 Fetching from uHunt 4.6e, Bipartite Graph LA 6525 - LatinAmerica13; split rows/columns due to the presence of pawns; then run MCBM 0.0
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
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
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-2024 Steven Halim

Share this page in Facebook