Harta's blog

Dynamic Programming Type
By Harta, 2 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 (53)
 
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it
any feedbacks are welcomed
→ Reply
 
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Awesome!
→ Reply
 
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I always appreciate the problems rather than theory, thanks.
→ Reply
 
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Some others are recommended by Amtrix
→ Reply
 
2 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
 
2 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
 
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it
zillion thanks to all contributors
→ Reply
 
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it
does this problem have own type ? http://www.spoj.pl/problems/ZUMA/
→ Reply
 
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it
awesome ,thanks man 
→ Reply
 
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

more problems: http://www.topcoder.com/tc?module=ProblemArchive&sr=&er=&sc=&sd=&class=&cat=Dynamic+Programming&div1l=&div2l=&mind1s=&mind2s=&maxd1s=&maxd2s=&wr=
→ Reply
 
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Thanks.
→ Reply
 
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it
i was solving problem of cutting sticks frm UVA.....i used some method tht was wasting lot of memory...i came to read tht this problem is exactly similar to the matrix chain multiplication problem bt i cant figure out the similarity between the two....can anyone help....the approach i used was to have all 1<<n subsets as the "states" of  DP...obviously its space requirement is tooo high...
thnx in advance......
→ Reply
 
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Great!

something about graph theory ?
→ Reply
 
23 months 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
 
23 months 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
 
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it
I Love DP :)
Thanks for it
→ Reply
  •  
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    can someone suggest some game problems solved using DP? thx
    → Reply
 
23 months 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
  •  
    22 months 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
 
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it
thanks
→ Reply
 
22 months 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
  •  
    22 months 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
 
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it
DP + Binary Search
(Game, IOI 2008, Practice session)
→ Reply
 
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it
thnx Harta
→ Reply
 
22 months 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
  •  
    22 months 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
    •  
      22 months 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
 
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it
hi,
What is DP + Knuth Optimization?
→ Reply
 
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it
How to solve MIXTURES in a complexity better than O(n^3) ?
→ Reply
  •  
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Do you mean the O(n*logn) algorithm?Or is there something easier?
    → Reply
 
20 months 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
  •  
    20 months 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
 
15 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it
Very  useful content.
Thanks!
I will mention my update whenver i solve any problem from above.

1. c. Edit Distance  - Done Source Code
      How to tackle array size .....declaring dp[2000][2000] gives seg. fault?
      Tutorial on Edit Distance
      Algo
→ Reply
 
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it
can u tell the level of difficulty too..
→ Reply
 
10 months 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
  •  
    10 months 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
 
9 months 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