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 can be stacked? |
|
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 |
Kattis - knapsack |
3.5c, 0-1 KNAPSACK |
basic DP KNAPSACK; print the solution |
687 |
4.8 |
ninepacks |
Kattis - 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 |
Kattis - orders |
3.5c, 0-1 KNAPSACK |
interesting KNAPSACK variant; print the solution |
713 |
4.5 |
presidentialelections |
Kattis - presidentialelecti... |
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 |
Kattis - 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 |
Kattis - 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 |
Kattis - 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 |
Kattis - beepers |
3.5e, TSP |
DP or recursive backtracking with sufficient pruning; also available at UVa 10496 - Collecting Beepers |
196 |
4.6 |
bustour |
Kattis - bustour |
3.5e, TSP |
LA 6028 - WorldFinals Warsaw12; DP TSP variant; also available at UVa 01281 - Bus Tour |
124 |
6.1 |
cycleseasy |
Kattis - cycleseasy |
3.5e, TSP |
Count number of HAMILTONIAN-TOURs |
108 |
4.1 |
errands |
Kattis - errands |
3.5e, TSP |
map location names to integer indices; DP TSP |
51 |
7.0 |
maximizingyourpay |
Kattis - maximizingyourpay |
3.5e, TSP |
Max-Traveling-Salesman-Problem; can go back to vertex 0 early; use DP bitmask |
60 |
6.4 |
pokemongogo |
Kattis - pokemongogo |
3.5e, TSP |
DP TSP variant; there can be more than one Pokemon in the same location |
154 |
5.0 |
race |
Kattis - 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 best |
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 |
Kattis - absurdistan3 |
4.6e, Bipartite Graph |
can be modeled as MCBM; or greedy graph construction with PQ |
312 |
5.6 |
bookclub |
Kattis - bookclub |
4.6e, Bipartite Graph |
check if perfect MCBM is possible |
307 |
4.5 |
elementarymath |
Kattis - elementarymath |
4.6e, Bipartite Graph |
left set: (a, b); right set: possible scores; possible if MCBM = n; use long long |
365 |
5.1 |
escapeplan |
Kattis - escapeplan |
4.6e, Bipartite Graph |
left set: robots; right set: holes; 3 version of similar bipartite graphs; MCBM |
98 |
5.7 |
flippingcards |
Kattis - 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 |
Kattis - gopher2 |
4.6e, Bipartite Graph |
MCBM; also available at UVa 10080 - Gopher II |
337 |
4.3 |
paintball |
Kattis - paintball |
4.6e, Bipartite Graph |
very similar with bookclub |
335 |
4.3 |
pianolessons |
Kattis - 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 actually small enough for recursive backtracking |
|
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 this is no longer possible |
|
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 actually small enough for recursive backtracking |
|
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 |
Kattis - councilling |
8.4a, Network Flow, Standard |
matching; max flow; print the assignment; also available at UVa 10511 - Councilling |
89 |
7.1 |
dutyscheduler |
Kattis - dutyscheduler |
8.4a, Network Flow, Standard |
try all possible (small range of answers); assignment problem; matching with capacity; max flow |
94 |
3.8 |
jupiter |
Kattis - 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 |
Kattis - maxflow |
8.4a, Network Flow, Standard |
standard max flow problem for practice; print edges used in the max flow |
531 |
6.3 |
mazemovement |
Kattis - 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 |
Kattis - 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 |
Kattis - piano |
8.4a, Network Flow, Standard |
good modeling problem; afterwards it is just a standard max flow problem |
230 |
4.1 |
tomography |
Kattis - tomography |
8.4a, Network Flow, Standard |
max flow; somewhat assignment problem; matching with capacity; bipartite graph: left-set: rows/right-set: col; can also be solved with greedy algorithm |
239 |
3.8 |
waif |
Kattis - waif |
8.4a, Network Flow, Standard |
two layers of graph matching; with capacity; use max flow solution |
159 |
2.7 |
water |
Kattis - 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 cut from source (left side) to sink (right side) |
|
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 |
Kattis - avoidingtheapocaly... |
8.4b, Network Flow, Variants |
interesting max flow modeling; blow the vertices based on time |
191 |
4.4 |
budget |
Kattis - budget |
8.4b, Network Flow, Variants |
max flow with lower bound |
66 |
6.8 |
chesscompetition |
Kattis - chesscompetition |
8.4b, Network Flow, Variants |
baseball elimination problem; similar to Kattis - unfairplay |
87 |
4.9 |
congest |
Kattis - congest |
8.4b, Network Flow, Variants |
LA 6395 - World Finals StPetersburg13; compute SSSP from downtown to other vertices; repeated edge-disjoint path computations using Max Flow |
256 |
3.7 |
conveyorbelts |
Kattis - conveyorbelts |
8.4b, Network Flow, Variants |
max flow; blow up the vertices K times; reroute edges |
89 |
3.7 |
copsandrobbers |
Kattis - copsandrobbers |
8.4b, Network Flow, Variants |
min cut; similar to Kattis - thekingofthenorth |
125 |
3.7 |
darkness |
Kattis - 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 is either 43 or 11 depending on the light level of adjacent cells |
28 |
6.5 |
floodingfields |
Kattis - floodingfields |
8.4b, Network Flow, Variants |
similar with UVa 11380; must be very careful |
48 |
5.5 |
landscaping |
Kattis - landscaping |
8.4b, Network Flow, Variants |
min cut; hard to spot the required modeling |
70 |
6.0 |
marchofpenguins |
Kattis - 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 |
Kattis - neutralground |
8.4b, Network Flow, Variants |
min cut; similar to Kattis - thekingofthenorth |
28 |
6.0 |
thekingofthenorth |
Kattis - thekingofthenorth |
8.4b, Network Flow, Variants |
interesting min cut problem |
193 |
5.0 |
transportation |
Kattis - transportation |
8.4b, Network Flow, Variants |
max flow with vertex capacities |
165 |
5.6 |
unfairplay |
Kattis - 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, Easier |
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, Easier |
LONGEST-PATH problem; small input/general graph |
|
0.0 |
00574 |
Fetching from uHunt |
8.6a, NP-hard/C, small, Easier |
print all solutions with backtracking |
|
0.0 |
00624 |
Fetching from uHunt |
8.6a, NP-hard/C, small, Easier |
input size is small; backtracking is enough |
|
0.0 |
00775 |
Fetching from uHunt |
8.6a, NP-hard/C, small, Easier |
backtracking suffices as the search space is small; it is more likely to have a HAMILTONIAN-TOUR in a dense graph, so we can prune early |
|
0.0 |
00989 |
Fetching from uHunt |
8.6a, NP-hard/C, small, Easier |
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, Easier |
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, Easier |
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, Easier |
SUBSET-SUM; try all; see the harder UVa 12911 that requires meet in the middle |
|
0.0 |
balanceddiet |
Kattis - balanceddiet |
8.6a, NP-hard/C, small, Easier |
PARTITION; n ≤ 20; use DP SUBSET-SUM style |
316 |
4.0 |
equalsumseasy |
Kattis - equalsumseasy |
8.6a, NP-hard/C, small, Easier |
PARTITION; generate all possible subsets with bitmask; use set to record which sums have been computed |
474 |
2.3 |
flowfree |
Kattis - flowfree |
8.6a, NP-hard/C, small, Easier |
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 |
Kattis - font |
8.6a, NP-hard/C, small, Easier |
count number of possible SET-COVERs; use 2^N backtracking; but use bitmask to represent small set of covered letters |
199 |
4.2 |
satisfiability |
Kattis - satisfiability |
8.6a, NP-hard/C, small, Easier |
SAT(isfiability); n ≤ 20; try all possible subsets |
244 |
3.8 |
socialadvertising |
Kattis - socialadvertising |
8.6a, NP-hard/C, small, Easier |
MIN-DOMINATING-SET/MIN-SET-COVER; n ≤ 20; use compact Adjacency Matrix technique |
59 |
5.1 |
tightfitsudoku |
Kattis - tightfitsudoku |
8.6a, NP-hard/C, small, Easier |
SUDOKU variant; backtracking + pruning |
87 |
4.2 |
vivoparc |
Kattis - vivoparc |
8.6a, NP-hard/C, small, Easier |
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, Harder |
LA 4793 - WorldFinals Harbin10; HAMILTONIAN-TOUR; backtracking+pruning; meet in the middle |
|
0.0 |
01217 |
Fetching from uHunt |
8.6b, NP-hard/C, small, Harder |
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, Harder |
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, Harder |
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 - sumsets |
|
0.0 |
10160 |
Fetching from uHunt |
8.6b, NP-hard/C, small, Harder |
optimization version of Min Vertex Cover on general graph; Dominating Set; which is NP-Hard; strategies: backtracking; sort by decreasing degrees; heavy pruning |
|
0.0 |
10571 |
Fetching from uHunt |
8.6b, NP-hard/C, small, Harder |
hard backtracking problem; it has similar flavor as Su Doku puzzle |
|
0.0 |
11065 |
Fetching from uHunt |
8.6b, NP-hard/C, small, Harder |
optimization version of MAX-INDEPENDENT-SET problem on general graph; also report the number of Independent Sets; bitmask helps in speeding up the solution |
|
0.0 |
11095 |
Fetching from uHunt |
8.6b, NP-hard/C, small, Harder |
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, Harder |
SUBSET-SUM; we cannot use DP as 1 ≤ N ≤ 40 and -10^9 ≤ T ≤ 10^9; use meet in the middle |
|
0.0 |
beanbag |
Kattis - beanbag |
8.6b, NP-hard/C, small, Harder |
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 |
Kattis - busplanning |
8.6b, NP-hard/C, small, Harder |
MIN-CLIQUE-COVER; DP bitmask over sets |
91 |
5.4 |
coloring |
Kattis - coloring |
8.6b, NP-hard/C, small, Harder |
GRAPH-COLORING; n ≤ 11; greedily set vertex 0 to have color 0 to reduce max N to 10; backtracking |
313 |
4.8 |
programmingteamselection |
Kattis - programmingteamsel... |
8.6b, NP-hard/C, small, Harder |
PARTITION-INTO-TRIANGLES; prune if #students % 3 != 0; generate up to m/3 teams; backtracking with memo |
64 |
7.2 |
tugofwar |
Kattis - tugofwar |
8.6b, NP-hard/C, small, Harder |
PARTITION; DP Knapsack with optimization to avoid TLE; also available at UVa 10032 - Tug of War |
68 |
7.4 |
01194 |
Fetching from uHunt |
8.6c, NP-hard/C, special, Easier |
LA 2523 - Beijing02; Min Vertex Cover/MVC |
|
0.0 |
01347 |
Fetching from uHunt |
8.6c, NP-hard/C, special, Easier |
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, Easier |
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, Easier |
MIS: V-MCBM; also available at Kattis - antennaplacement |
|
0.0 |
10859 |
Fetching from uHunt |
8.6c, NP-hard/C, special, Easier |
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, Easier |
MAX-INDEPENDENT-SET; on Bipartite Graph; ans equals to its MCBM |
|
0.0 |
11357 |
Fetching from uHunt |
8.6c, NP-hard/C, special, Easier |
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, Easier |
MVC; Konig theorem |
|
0.0 |
12083 |
Fetching from uHunt |
8.6c, NP-hard/C, special, Easier |
LA 3415 - NorthwesternEurope05; MIS; also available at Kattis - guardianofdecency |
|
0.0 |
12168 |
Fetching from uHunt |
8.6c, NP-hard/C, special, Easier |
LA 4288 - NorthwesternEurope08; MIS; also available at Kattis - catvsdog |
|
0.0 |
13115 |
Fetching from uHunt |
8.6c, NP-hard/C, special, Easier |
just a SUDOKU solution verifier; an NP-problem |
|
0.0 |
antennaplacement |
Kattis - antennaplacement |
8.6c, NP-hard/C, special, Easier |
MIS: V-MCBM; also available at UVa 10349 - Antenna Placement |
36 |
5.2 |
bilateral |
Kattis - bilateral |
8.6c, NP-hard/C, special, Easier |
MIN-VERTEX-COVER on Bipartite Graph; MCBM; Konig's theorem that can handle the 1009 case correctly |
43 |
6.5 |
bookcircle |
Kattis - bookcircle |
8.6c, NP-hard/C, special, Easier |
left set: boys; right set: girls; add edge (i, j) if boy i reads same book as girl j; MIN-VERTEX-COVER on Bipartite Graph = MCBM |
137 |
4.4 |
catvsdog |
Kattis - catvsdog |
8.6c, NP-hard/C, special, Easier |
LA 4288 - NorthwesternEurope08; MIS; also available at UVa 12168 - Cat vs. Dog |
199 |
5.5 |
citrusintern |
Kattis - citrusintern |
8.6c, NP-hard/C, special, Easier |
modified MIN-WEIGHT-VERTEX-COVER on tree; some edges can be ignored |
169 |
3.6 |
countingclauses |
Kattis - countingclauses |
8.6c, NP-hard/C, special, Easier |
special case of 3-SAT; a bluffing task |
480 |
1.7 |
europeantrip |
Kattis - europeantrip |
8.6c, NP-hard/C, special, Easier |
STEINER-TREE with 3 terminal vertices and up to 1 Steiner point; we can use two ternary searches |
297 |
3.3 |
guardianofdecency |
Kattis - guardianofdecency |
8.6c, NP-hard/C, special, Easier |
LA 3415 - NorthwesternEurope05; MIS; also available at UVa 12083 - Guardian of Decency |
45 |
6.3 |
reactivity |
Kattis - reactivity |
8.6c, NP-hard/C, special, Easier |
verify if a HAMILTONIAN-PATH exists in the DAG; find one topological sort of the DAG; verify if it is the only one in linear time |
280 |
4.0 |
01086 |
Fetching from uHunt |
8.6d, NP-hard/C, special, Harder |
LA 4452 - WorldFinals Stockholm09; can be modeled as a 2-SAT problem |
|
0.0 |
01096 |
Fetching from uHunt |
8.6d, NP-hard/C, special, Harder |
LA 4791 - WorldFinals Harbin10; Bitonic TSP variant; print the actual path |
|
0.0 |
01184 |
Fetching from uHunt |
8.6d, NP-hard/C, special, Harder |
LA 2696 - Dhaka02; MPC on DAG ~ MCBM |
|
0.0 |
01201 |
Fetching from uHunt |
8.6d, NP-hard/C, special, Harder |
LA 3126 - NorthwesternEurope04; MPC on DAG; also available at Kattis - taxicab |
|
0.0 |
01212 |
Fetching from uHunt |
8.6d, NP-hard/C, special, Harder |
LA 3483 - Hangzhou05; MWIS on Bipartite Graph |
|
0.0 |
01220 |
Fetching from uHunt |
8.6d, NP-hard/C, special, Harder |
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, Harder |
can be modeled as a 2-SAT problem |
|
0.0 |
11294 |
Fetching from uHunt |
8.6d, NP-hard/C, special, Harder |
can be modeled as a 2-SAT problem; also available at Kattis - wedding |
|
0.0 |
airports |
Kattis - airports |
8.6d, NP-hard/C, special, Harder |
MIN-PATH-COVER; on DAG; MCBM |
92 |
6.4 |
eastereggs |
Kattis - eastereggs |
8.6d, NP-hard/C, special, Harder |
BSTA; MAX-INDEPENDENT-SET on Bipartite Graph; V-MCBM |
82 |
5.2 |
ironcoal |
Kattis - ironcoal |
8.6d, NP-hard/C, special, Harder |
STEINER-TREE with 3 terminal vertices and up to 1 Steiner point; SSSP on unweighted graph; BFS; similar to Kattis - jailbreak |
216 |
5.0 |
itcanbearranged |
Kattis - itcanbearranged |
8.6d, NP-hard/C, special, Harder |
MIN-PATH-COVER; on DAG; weighted; Max Flow |
50 |
5.1 |
jailbreak |
Kattis - jailbreak |
8.6d, NP-hard/C, special, Harder |
STEINER-TREE; on grid; 3 terminal vertices: 'outside' and 2 prisoners; BFS; get the best Steiner point that connects them |
130 |
4.8 |
joggers |
Kattis - joggers |
8.6d, NP-hard/C, special, Harder |
MIN-VERTEX-COVER on Tree; root tree at vertex 0; limit tree up to depth S/2 |
46 |
6.1 |
mafija |
Kattis - mafija |
8.6d, NP-hard/C, special, Harder |
MAX-INDEPENDENT-SET; Special case: on Pseudoforest; use Greedy MIS; handle unvisited cycle separately |
100 |
3.7 |
ridofcoins |
Kattis - ridofcoins |
8.6d, NP-hard/C, special, Harder |
not the minimizing COIN-CHANGE problem; but the maximizing one; greedy pruning; complete search on much smaller instance |
94 |
7.9 |
taxicab |
Kattis - taxicab |
8.6d, NP-hard/C, special, Harder |
LA 3126 - NorthwesternEurope04; MPC on DAG; also available at UVa 01201 - Taxi Cab Scheme |
38 |
5.5 |
wedding |
Kattis - wedding |
8.6d, NP-hard/C, special, Harder |
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 Algorithm |
LA 3276 - WorldFinals Shanghai05; try all configurations; weighted matching; pick the best; Kuhn-Munkres |
|
0.0 |
10746 |
Fetching from uHunt |
9.kuhn, Kuhn-Munkres Algorithm |
min weighted bipartite matching |
|
0.0 |
10888 |
Fetching from uHunt |
9.kuhn, Kuhn-Munkres Algorithm |
BFS/SSSP; min weighted bipartite matching |
|
0.0 |
11553 |
Fetching from uHunt |
9.kuhn, Kuhn-Munkres Algorithm |
brute force; DP bitmask; or Hungarian |
|
0.0 |
aqueducts |
Kattis - aqueducts |
9.kuhn, Kuhn-Munkres Algorithm |
build bipartite graph; weighted MCBM; Hungarian |
51 |
6.0 |
cheatingatwar |
Kattis - cheatingatwar |
9.kuhn, Kuhn-Munkres Algorithm |
build weighted bipartite graph K26,26; L: Yraglac's card; R: Opponent's card; assign value: 2/1/0; weighted MCBM; Hungarian |
97 |
3.1 |
engaging |
Kattis - engaging |
9.kuhn, Kuhn-Munkres Algorithm |
LA 8437 - HoChiMinhCity17; Hungarian; print solution |
135 |
5.8 |
cheeseifyouplease |
Kattis - cheeseifyouplease |
9.line, Linear Programming |
simple Linear Programming problem; use Simplex |
51 |
3.3 |
maximumrent |
Kattis - maximumrent |
9.line, Linear Programming |
basic Linear Programming problem with integer output; we can use simplex algorithm or another simpler solution |
241 |
3.1 |