DP Guide 1 v2.0

Universidad Centroamericana José Simeón Cañas
Facultad de Ingenierı́a y Arquitectura

Departamento de Electrónica e Informática
Análisis de Algoritmos Ciclo 02/2023
Guı́a de Ejercicios No. 8 Programación Dinámica
( Extracto de ejercicios de Competitive Programming 4 de Steve Halim )
Dynamic Programming
Max 1D Range Sum
1. UVA 10684 - The Jackpot (standard; Kadane’s algorithm)
https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=
1625
2. UVA 00787 - Maximum Sub ... (max 1D range product; be careful with 0; use Java BigInteger)
https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=728
3. Kattis - commercials (transform each input by -P; Kadane’s algorithm)
https://open.kattis.com/problems/commercials
4. Kattis - sellingspatulas (-8 per time slot initially; read sale data; 1D range sum; complete search)
https://open.kattis.com/problems/sellingspatulas
5. Kattis - alicedigital
https://open.kattis.com/problems/alicedigital
6. Kattis - purplerain
https://open.kattis.com/problems/purplerain
7. Kattis - shortsell
https://open.kattis.com/problems/shortsell
8. UVA 00507
448
9. UVA 12640
https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_
problem&problem=4388
10. UVA 13095

4993
0/1 Knapsack
1. UVA 10130 - SuperSale (very basic 0-1 Knapsack problem)
2. Kattis - knapsack (basic DP Knapsack; print the solution)
https://open.kattis.com/problems/knapsack
3. Kattis - orders (interesting Knapsack variant; print the solution)

https://open.kattis.com/problems/orders
4. Kattis - presidentialelections (pre-process the input to discard non winnable states; be careful of
negative total voters; then standard DP Knapsack)
https://open.kattis.com/problems/presidentialelections
5. Kattis - muzicari
https://open.kattis.com/problems/muzicari
6. Kattis - ninepacks
https://open.kattis.com/problems/ninepacks
7. UVA 01213 - Sum of Different Primes (LA 3619 - Yokohama06; extension of 0-1 Knapsack; s: (id,
remN, remK) instead of s: (id, remN))
3654
8. UVA 11566 - Let’s Yum Cha (Knapsack variant: double each dim sum; add one parameter to see if
we have bought too many dishes)
2613
1
9. UVA 11832 - Account Book (interesting DP; s: (id, val); use offset to handle negative numbers; t:
plus or minus; print solution)
https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_
problem&problem=2932
10. UVA 00431
https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=
372
11. UVA 00562
503
12. UVA 00990

931
13. UVA 10261
1202
14. UVA 10616
1557
15. UVA 10664

1605
16. UVA 10690
1631
17. UVA 10819
1760
18. UVA 11003
1944
19. UVA 11341
2316
20. UVA 11658

2705
21. UVA 12621
4344
Coin-Change
1. UVA 00674 - Coin Change (basic Coin-Change problem)
615
2. Kattis - bagoftiles (count number of ways to do Coin-Change; meet in the middle; DP combinatorics
(n choose k) to find the answer for a+b)
https://open.kattis.com/problems/bagoftiles
3. Kattis - canonical (complete search possible range of counter examples; do both greedy Coin-Change
and DP Coin-Change)
https://open.kattis.com/problems/canonical
4. Kattis - exactchange2 (a variation to the Coin-Change problem; also available at UVa 11517 - Exact
Change)
https://open.kattis.com/problems/exactchange2
5. UVA 00242 - Stamps and ... (LA 5181 - WorldFinals Nashville95; Complete Search + DP Coin-
Change)
178
2
6. UVA 10448 - Unique World (after dealing with traversal on tree, you can reduce the original problem
into Coin-Change; not trivial)
1389
7. UVA 11259 - Coin Changing Again (part of the problem is DP Coin-Change with restricted number
of coins per type; inclusion-exclusion)
2226
8. UVA 00147
83
9. UVA 00166
102
10. UVA 00357
293
11. UVA 10313
1254
12. UVA 11137
2078
LIS / LDS / LCS

1. UVA 00481 - What Goes Up? (O(n log k) LIS+solution)
422
2. Kattis - increasingsubsequence (LIS; n ≤ 200; print lexicographically smallest solution, 99% similar
to ‘longincsubseq’)
https://open.kattis.com/problems/increasingsubsequence
3. Kattis - alphabet
https://open.kattis.com/problems/alphabet
4. Kattis - longincsubseq
https://open.kattis.com/problems/longincsubseq
5. Kattis - manhattanmornings
https://open.kattis.com/problems/manhattanmornings
6. Kattis - studentsko
https://open.kattis.com/problems/studentsko
7. UVA 01196 - Tiling Up Blocks (LA 2815 - Kaohsiung03; sort all the blocks in increasing L[i], then
we get the classical LIS problem)
3637
8. UVA 10534 - Wavio Sequence (must use O(n log k) LIS twice)
9. UVA 11790 - Murcia’s Skyline (combination of LIS+LDS; weighted)
2890
10. UVA 00111
47
11. UVA 00231
167
12. UVA 00437
378
13. UVA 00497
438
3
14. UVA 10131
1072
15. UVA 10154
1095

DP Guide 1 v2.0

Uploaded by

Copyright:

Available Formats

DP Guide 1 v2.0

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DP Guide 1 v2.0

Uploaded by

Copyright:

Available Formats

Universidad Centroamericana José Simeón Cañas

Facultad de Ingenierı́a y Arquitectura

10. UVA 13095

3. Kattis - orders (interesting Knapsack variant; print the solution)

12. UVA 00990

15. UVA 10664

20. UVA 11658

LIS / LDS / LCS

You might also like