Competitive Programming
Use these filters to narrow down your next problem to solve:
OJ: , Topic: , Quality:
You can now sort these problems based on Distinct ACcepted Users (DACU) column.
Generally, problems with high DACU are the easier problems.
Note that we only update DACU column manually when we first entered the hint (thus an outdated data).
Note: Column Point is only relevant for Kattis online judge.
| Both OJ | Problem Title | CP4 | Hint | DACU | Point |
|---|---|---|---|---|---|
| 00431 | Fetching from uHunt | 3.5c, 0-1 KNAPSACK | 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.5c, 0-1 KNAPSACK | use a one dimensional table | 0.0 | |
| 00990 | Fetching from uHunt | 3.5c, 0-1 KNAPSACK | print the solution | 0.0 | |
| 01213 | Fetching from uHunt | 3.5c, 0-1 KNAPSACK | LA 3619 - Yokohama06; extension of 0-1 KNAPSACK; s: (id, remN, remK) instead of s: (id, remN) | 0.0 | |
| 10130 | Fetching from uHunt | 3.5c, 0-1 KNAPSACK | very basic 0-1 KNAPSACK problem | 0.0 | |
| 10261 | Fetching from uHunt | 3.5c, 0-1 KNAPSACK | s: (current_car; left; right) | 0.0 | |
| 10616 | Fetching from uHunt | 3.5c, 0-1 KNAPSACK | input can be -ve; use long long | 0.0 | |
| 10664 | Fetching from uHunt | 3.5c, 0-1 KNAPSACK | Subset Sum | 0.0 | |
| 10690 | Fetching from uHunt | 3.5c, 0-1 KNAPSACK | DP Subset Sum with negative offset technique; with addition of simple math | 0.0 | |
| 10819 | Fetching from uHunt | 3.5c, 0-1 KNAPSACK | 0-1 knapsack with 'credit card' twist | 0.0 | |
| 11003 | Fetching from uHunt | 3.5c, 0-1 KNAPSACK | 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.5c, 0-1 KNAPSACK | s: (id; h_learned; h_left); t: learn module 'id' by 1 hour or skip it | 0.0 | |
| 11566 | Fetching from uHunt | 3.5c, 0-1 KNAPSACK | 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.5c, 0-1 KNAPSACK | s: (id; share); t: form/ignore coalition with id | 0.0 | |
| 11832 | Fetching from uHunt | 3.5c, 0-1 KNAPSACK | interesting DP; s: (id; val); use offset to handle negative numbers; t: plus or minus; print solution | 0.0 | |
| 12621 | Fetching from uHunt | 3.5c, 0-1 KNAPSACK | DP Subset Sum; simplify the multiple of 10 | 0.0 | |
| 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 |
| 00147 | Fetching from uHunt | 3.5d, COIN-CHANGE | similar to UVa 357 and 674 | 0.0 | |
| 00166 | Fetching from uHunt | 3.5d, COIN-CHANGE | two coin change variants in one problem | 0.0 | |
| 00242 | Fetching from uHunt | 3.5d, COIN-CHANGE | LA 5181 - WorldFinals Nashville95; Complete Search + DP Coin-Change | 0.0 | |
| 00357 | Fetching from uHunt | 3.5d, COIN-CHANGE | similar to UVa 147 and 674 | 0.0 | |
| 00674 | Fetching from uHunt | 3.5d, COIN-CHANGE | basic coin change problem | 0.0 | |
| 10313 | Fetching from uHunt | 3.5d, COIN-CHANGE | modified coin change and DP 1D range sum | 0.0 | |
| 10448 | Fetching from uHunt | 3.5d, 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.5d, COIN-CHANGE | use long long | 0.0 | |
| 11259 | Fetching from uHunt | 3.5d, 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.5d, COIN-CHANGE | a variation to the coin change problem; also available at Kattis - exactchange2 | 0.0 | |
| 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 |
| 00216 | Fetching from uHunt | 3.5e, TSP | LA 5155 - WorldFinals KansasCity92; DP TSP problem; but still solvable with backtracking | 0.0 | |
| 01281 | Fetching from uHunt | 3.5e, TSP | LA 6028 - WorldFinals Warsaw12; DP TSP variant; also available at Kattis - bustour | 0.0 | |
| 10496 | Fetching from uHunt | 3.5e, TSP | DP or recursive backtracking with sufficient pruning; also available at Kattis - beepers | 0.0 | |
| 11795 | Fetching from uHunt | 3.5e, 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.5e, TSP | simply find and print the lexicographically smallest Hamiltonian path; use DP-TSP technique | 0.0 | |
| 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 |
| 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 |
| 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 |
| 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 |
