Saturday, 10 January 2015

bfs and dfs spoj questions extra dp question list

BFS & DFS


Dijkstra, Floyd Warshall, Prim & Kruskal


• Longest Increasing Subsequence (LIS) – Classical
1. UVa 103 - Stacking Boxes (Longest Path in DAG ≈ LIS)
2. UVa 111 - History Grading (straight-forward)
3. UVa 231 - Testing the Catcher (straight-forward)
4. UVa 481 - What Goes Up? (must use O(n log k) LIS)
5. UVa 497 - Strategic Defense Initiative (solution must be printed)
6. UVa 10051 - Tower of Cubes (can be modeled as LIS)
7. UVa 10534 - Wavio Sequence (must use O(n log k) LIS twice)
8. UVa 11790 - Murcia’s Skyline (combination of classical LIS+LDS, weighted)
9. UVa 11003 - Boxes
10. UVa 11456 - Trainsorting (get max(LIS(i) + LDS(i) - 1), ∀i ∈ [0 . . . N -1])
11. LA 2815 - Tiling Up Blocks (Kaohsiung03)
• Coin Change – Classical
1. UVa 147 - Dollars (similar to UVa 357 and UVa 674)
2. UVa 166 - Making Change
3. UVa 357 - Let Me Count The Ways (a variant of the coin change problem)
4. UVa 674 - Coin Change
553.4. DYNAMIC PROGRAMMING
c Steven & Felix, NUS
5. UVa 10306 - e-Coins
6. UVa 10313 - Pay the Price
7. UVa 11137 - Ingenuous Cubrency (use long long)
8. UVa 11517 - Exact Change
• Maximum Sum
1. UVa 108 - Maximum Sum (maximum 2-D sum, elaborated in this section)
2. UVa 836 - Largest Submatrix (maximum 2-D sum)
3. UVa 10074 - Take the Land (maximum 2-D sum)
4. UVa 10667 - Largest Block (maximum 2-D sum)
5. UVa 10827 - Maximum Sum on a Torus (maximum 2-D sum)
6. UVa 507 - Jill Rides Again (maximum 1-D sum/maximum consecutive subsequence)
7. UVa 10684 - The Jackpot (maximum 1-D sum/maximum consecutive subsequence)
• 0-1 Knapsack – Classical
1. UVa 562 - Dividing Coins
2. UVa 990 - Diving For Gold
3. UVa 10130 - SuperSale
4. LA 3619 - Sum of Different Primes (Yokohama06)
• String Edit (Alignment) Distance – Classical (see Section 6.3)
• Longest Common Subsequence – Classical (see Section 6.3)
• Non Classical (medium difficulty)
1. UVa 116 - Unidirectional TSP (similar to UVa 10337)
2. UVa 473 - Raucuous Rockers
3. UVa 607 - Scheduling Lectures
4. UVa 10003 - Cutting Sticks (discussed in this book)
5. UVa 10337 - Flight Planner (DP solvable with Dijkstra)
6. UVa 10891 - Game of Sum (2 dimensional states)
7. UVa 11450 - Wedding Shopping (discussed in this book)
8. LA 3404 - Atomic Car Race (Tokyo05)
• DP + Bitmasks
1. UVa 10364 - Square (bitmask technique can be used)
2. UVa 10651 - Pebble Solitaire
3. UVa 10908 - Largest Square
4. UVa 10911 - Forming Quiz Teams (elaborated in this section)
5. LA 3136 - Fun Game (Beijing04)
6. PKU 2441 - Arrange the Bulls
• DP on ‘Graph Problem’
1. UVa 590 - Always on the Run
2. UVa 910 - TV Game (straightforward)
3. UVa 10681 - Teobaldo’s Trip
4. UVa 10702 - Traveling Salesman
5. LA 4201 - Switch Bulbs (Dhaka08)
6. SPOJ 101 - Fishmonger
563.5. CHAPTER NOTES
c Steven & Felix, NUS
• DP with non-trivial states
1. LA 4106 - ACORN (Singapore07) (DP with dimension reduction)
2. LA 4143 - Free Parentheses (Jakarta08) (Problem set by Felix Halim)
3. LA 4146 - ICPC Team Strategy (Jakarta08) (DP with 3 states)
4. LA 4336 - Palindromic paths (Amritapuri08)
5. LA 4337 - Pile it down (Amritapuri08)
6. LA 4525 - Clues (Hsinchu09)
7. LA 4526 - Inventory (Hsinchu09)
8. LA 4643 - Twenty Questions (Tokyo09)
• DP on Tree
1. UVa 10243 - Fire! Fire!! Fire!!! (Min Vertex Cover ≈ Max Independent Set on Tree)
2. UVa 11307 - Alternative Arborescence (Min Chromatic Sum, 6 colors are sufficient)
3. LA 3685 - Perfect Service (Kaohsiung06)
4. LA 3794 - Party at Hali-Bula (Tehran06)
5. LA 3797 - Bribing FIPA (Tehran06)
6. LA 3902 - Network (Seoul07)
7. LA 4141 - Disjoint Paths (Jakarta08)