Competitive Programming Book

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 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
muzicari	Kattis - 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', respectively), minimize to favor knapsack 1, get solution	343	4.9
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
mapcolouring	Kattis - mapcolouring	8.6b, NP-hard/C, small, Harder	GRAPH-COLORING; n ≤ 16; DP over sets; O(3^n); Subset of vertices that are Independent can be 1-colored	200	5.2
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
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 K_26,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

Loading, Please Wait...

Methods to Solve

(back to Competitive Programming Book website)