Harta's blog

Dynamic Programming Type
By Harta, 15 years ago, In English
Dynamic Programming (DP) :

1. Classic Dynamic Programming
a. LCS
   Problem: 1. SAMER08D

b. LIS
   Problem: 1. Beautiful People
                 2. MDOLLS
                 3. MSTICK
                 4. MCARDS

c. Edit Distance

d. Matrix Chain Multiplication
   Problem: 1. Mixtures

e. Knapsack
   Problem: 1. Scubadiv

2. Advance DP
a. DP k-th lexicographical string
    Problem: 1. z-01 paths
                   2. z-board
                   3. Linear Garden (IOI 2008)

b. DP tree
    Problem: 1. z-sumpaths
                   2. River (IOI 2005)
                   3. z-company
                   4. Greedy Hydra (CNOI 2002)
                   5. VOCV
                   6. PT07F
                   7. PT07X
                   8. nagibni

c. DP+ BIT/segment tree
    Problem: 1. Salesman (IOI 2009)
                   2. explosion
                   3. intervali
                   4. RENT
                   5. INCSEQ
                   6. INCDSEQ

d. DP+ convex hull
    Problem: 1. Batch Scheduling (IOI 2002)
                   2. NKLEAVES
                   3. Harbingers (CEOI 2009)
                   4. Commando (APIO 2010)

e. DP pre-processing
    Problem: 1. Oil (APIO 2009)
                   2. Garden (IOI 2005)
                   3. Pyramid (IOI 2006)

f. DP bitmask
   Problem: 1. Reklame
                  2. Chess
                  3. Bond
                  4. TRSTAGE
                  5. HIST2
                  6. LAZYCOWS

g. Problem 1: Grid (BOI 2008)

h. DP matrix multiplication/ DP using recurrence
    Problem 1. SEQ
                  2. SPP
                  3. z-funkcija
                  4. mit-indiv09-words
                  5. Reading (Balkan 2009)
                  6. Super Climber
                  7. z-mario

i. DP+ trie
   Problem 1. MORSE

j. DP+geometry
   Problem 1. MPOLY
                 2. CVXPOLY
                 3. MTRIAREA

k. DP + Binary Search
   Problem 1. Game (IOI 2008, Practice session)

l. DP + Knuth Optimization
   Problem 1. Breaking Strings
Other Problems in SPOJ can be found here by pt1989
Thanks to pt1989

Here are problems in acm.sgu.ru 269, 273, 304, 317, 356, 396, 445, 447, 458, 489, 494
Thanks to natalia

Reference:
      1. Topcoder
      2. Codechef
  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (67)
| Write comment?
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
any feedbacks are welcomed
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Awesome!
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Some others are recommended by Amtrix
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
DP using recurrence:
http://www.spoj.pl/problems/SEQ/

Can I save ur link into my blog?
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
LIS:
http://acm.sgu.ru/problem.php?contest=0&problem=199
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
zillion thanks to all contributors
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Thanks.
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Great!

something about graph theory ?
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hi,

It seems that you added the problem NKLEAVES on ztrening. Can I know where you got the testcases from? I got 2 cases wrong (testcase 3 and 8) and I cannot figure out why :(.
→ Reply
15 years ago, # |
  Vote: I like it +1 Vote: I do not like it
some DP problems from acm.sgu.ru: 269, 273, 304, 317, 356, 396, 445, 447, 458, 489, 494




→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I Love DP :)
Thanks for it
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    can someone suggest some game problems solved using DP? thx
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Try this one. It is a problem that I came across in the past. Sorry, I forgot the website and don't have the testcases :(, but I know the algorithm though XD.

You have a N bowling pins (1<=N<=1000) arranged in a line. The pins are represented as a string of 1s and 0s. 1 means the pin is still standing and 0 means the pin has been knocked down. Player A and B take turns to play this game, with player A moving first.

In each of their turns, A or B chooses to knock down up to K (1<=K<=N) consecutive standing pins down. A player can only knock down exactly one consecutive block of standing pins during his turn. He must also knock down at least 1 pin. The player who cannot make a move loses.

Given N,K, and the initial starting configuration of the pins, determine who will win under optimal play. If A will win, output the resulting configuration of the pins after A has made his move. If there are multiple moves A can make, output the move that will result in a lexicographically smallest resulting formation.

Note: You do require a bit of game theory before you can solve this problem.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    ow.. thx for the problem, I just notice that someone had replied xD
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
hi,
I am facing problems with the chess problem  listed above. Can anyone suggest some hints to solving the problem.

P.S: I am a newbie in DP
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    since M is small (M<=10) you can use bitmask.
    0->no king
    1->there is a king
    dp[i][state] where state means the state of the kings in row-i
    you can add dp[i][state1] with dp[i-1][state2] if kings in state2 can't attack kings in state1.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
DP + Binary Search
(Game, IOI 2008, Practice session)
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
hi,
can you say some hints for problem MTRAREA? is there any solution better than O(n^2)?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You can solve it in O(n*log(n)). First find a convex hull, and then use the method described here.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      thanks. beautiful idea! I was trying to solve it using DP. does it have any efficient solution using DP?
      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
hi,
What is DP + Knuth Optimization?
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Anyone got a clue on how to approach The Greedy Hydra problem? It seems tough :|
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    If the number of colours >= 3, you can always colour the edges in such a way that no fruits are eaten. Just alternate the colouring.

    If the number of colours == 2, then you write the N^3 dp.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hi

Can anybody help me what is the problem with my solution for the mixtures problem? (I've got WA)

(I've checked spoj forum and my solution is correct those test case.. :( )
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Seems it won't even pass example input. There can be multiple input in single file - you read only first one.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Is there something wrong with z-trening!!!!
please provide some alternative(judge) for the z-trening problems in above list
→ Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Hello,

Any useful link,tutorial to get idea about Digit DP?

To solve problem like those here:

http://www.lightoj.com/volume_showproblem.php?problem=1122

http://www.lightoj.com/volume_showproblem.php?problem=1122

http://www.lightoj.com/volume_showproblem.php?problem=1125

THanks :)

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I don't know what you meant by "digit dp" but these are very simple dp problems. For example in "1122 — Digit Count" your state can be (number of digits taken so far, last digit taken), now you can just add new numbers if it is valid, go to next state and add the answers.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For the problem 1125, your DP should have three states like [current position of the array][how many left to take][remainder of the sums of the chosen elements].

    suppose you are in a state like this [25][2][5]

    then you can either

    1. take the 25th element and add it to remainder and mod it which will take you to the state [26][1][ (5+X[25] + mod)%mod ]

    2. or you can skip it and go to the next state which will be then [26][2][5]

    By this way you can figure out all the possible combinations.

    Here is my source code -->

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      In your code you did something like this ((mod+arr[pos])%d) +d )%d why ??

      isn't this enough (mod+arr[pos])%d because x%d always >=0 , right ??

      UDP : i got it , numbers can be negative , that's why .

      → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Awesome!!!!!!

→ Reply
»
11 years ago, # |
  Vote: I like it +7 Vote: I do not like it

why the links to problems not found? who can helpme? I need try resolve many exercise of DP... sorry for my english...

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    This post is 3 years old, and hasn't been updated since a moment. So it isn't surprising that some links doesn't exist anymore. After a little search on google, it seems that "z-trening" can't be found. But for the links who reference to a problem on spoj/codeforces/topcoder, there must be no problem.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone provide me some hints to solve this problem:- http://www.spoj.pl/problems/TRSTAGE/

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Some edit distance problems. Edit distance Aibohphobia Longest Palindrome Creating Palindrome

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can you give problems from Advanced Knapsack?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Page with other SPOJ problems by pt1989 isn't working

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain how to solve the problem explosion mentioned under category dp+segment tree...

Question link: http://www.codah.club/tasks.php?show_task=5000000441

Thank you!!

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone provide solution for spoj mdoll using lis

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

If codeforces provides bookmark options...It would be better to save blog post attached with account!!! :)

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually, you can save it to favourites, the little star under the post.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

OIL (APIO 2009) Editorial

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to approach z-sumpaths under DP tree category?

→ Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Here are some more problems- Atcoder dp contest

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

link was dropped

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good collection of practice problems for dp. Thanks!!

→ Reply