__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-board3. 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

http://www.spoj.pl/problems/SEQ/

http://acm.sgu.ru/problem.php?contest=0&problem=199

thnx in advance......

something about graph theory ?

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 :(.

Thanks for it

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.

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

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.

can you say some hints for problem MTRAREA? is there any solution better than O(n^2)?

What is DP + Knuth Optimization?

If the number of colours == 2, then you write the N^3 dp.

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

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.

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.. :( )

Also mine. :)

please provide some alternative(judge) for the z-trening problems in above list

I have the same problem .

same problem here.

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

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

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 :)

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.

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 -->

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 .Awesome!!!!!!

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

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.

I can see that, z-treining references not work, you can tellme where I can try Harbingers (CEOI 2009) exercise, thanks for your help!!

For this precise task: http://www.ceoi2009.ro/tasks/harbingers.pdf Else, if you want more archive for CEOI: http://ceoi.inf.elte.hu/tasks-archive/

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

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

BitMask!!! :P ;)

i need some list of lcs related dp problem.. thanks in advance

mohieddine we start doing those tomorrow?

great problem set , but one big problem when i solve problems is that after hours i can't solve some hard problem for me try to find algorithm but there is nothing to find solution,it's sometimes wasted time. can someone tell me how to find solutions(tutorial) for exapmle spoj great problems.?? thanks.

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

Can you give problems from Advanced Knapsack?

Page with other SPOJ problems by pt1989 isn't working

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!!

can someone provide solution for spoj mdoll using lis

Can be MDOLLS on Spoj solved using LIS tecnique?

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

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

OIL (APIO 2009) Editorial