Harta's blog

By Harta5 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 269273304317356396445447458489494
Thanks to natalia

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

 
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it
any feedbacks are welcomed
 
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Awesome!
 
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I always appreciate the problems rather than theory, thanks.
 
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Some others are recommended by Amtrix
 
5 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?
 
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it
LIS:
http://acm.sgu.ru/problem.php?contest=0&problem=199
 
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it
zillion thanks to all contributors
 
5 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/
 
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it
awesome ,thanks man 
 
5 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=
 
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Thanks.
 
5 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......
 
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Great!

something about graph theory ?
 
4 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 :(.
 
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it
some DP problems from acm.sgu.ru269273304317356396445447458489494




 
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I Love DP :)
Thanks for it
  •  
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    can someone suggest some game problems solved using DP? thx
 
4 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.
  •  
    4 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
 
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
thanks
 
4 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
  •  
    4 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.
 
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
DP + Binary Search
(Game, IOI 2008, Practice session)
 
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
thnx Harta
 
4 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)?
  •  
    4 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.
    •  
      4 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?
 
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
hi,
What is DP + Knuth Optimization?
 
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
How to solve MIXTURES in a complexity better than O(n^3) ?
  •  
    4 years 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?
 
4 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 :|
  •  
    4 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.
 
4 years 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
  •  
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the problem will be solved if you increase the size to 3000, same happened with me too.

    Just take a global static int of size 3000.

 
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
can u tell the level of difficulty too..
 
3 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.. :( )
  •  
    3 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.
 
3 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
 
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For editDistance problem in above for which you haven't added any problem, you can add this problem :

http://www.spoj.com/problems/EDIST/

 
»
20 months ago, # |
  Vote: I like it +3 Vote: I do not like it
  •  
    »
    »
    19 months 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.

  •  
    »
    »
    19 months 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 -->

 
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Awesome!!!!!!

 
»
15 months 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...

  •  
    »
    »
    15 months 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.

 
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hi guys very new to this field...Can someone explain me what is the segment in the first problem in the post...i.e the problem based on LCS topic

 
»
4 months 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/