JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (oldest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
[ 1 2 ]    NEXT >
Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply
I searched via google but found only "a few" problems that can be solved using DP on broken profile. Do you know some problems of this type both in Topcoder and other OJ?
Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply
Can you please also cover DP problems where the smallest/largest number/string is required which satisfies a certain property?
Re: 2.4.? Commonly used DP state domains (response to post by M.G.Z) | Reply
Fixed that. Thank you=)
Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply
In this line if(nj <= space && maxcost[ni][nj] > nmc), it must be if(nj <= space && maxcost[ni][nj] < nmc)
Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply
Can u explain This problem?
http://www.topcoder.com/stat?c=problem_statement&pm=6725&rd=10100
Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply
Thanx for the reply.
Now I understood the solution.
BTW this tutorial is very good and I was looking for this kind DP tutorial.
Re: 2.4.? Commonly used DP state domains (response to post by akshayk0406) | Reply
1. Middle point is the point at which we want to break the segment [L;R]. In the DP we have to consider all possible positions for the break(middle) point ranging from L+1 to R-1 inclusive. The mid(L,R) is the first middle point that gives optimal result for the (L,R) state.

2. The M positions of cuts plus beginning and the end are stored in the x vector. F.i. in the example test x = {0, 3, 8, 10, 20}. This array represents the required break points and it influences the DP results.

If you cannot understand the meaning of something from the text please refer to the code sample - it should be clear.
Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply
I didn't understand the solution to Breaking Strings problem

1) What does mid(L,R) actually denote . "First Middle Point" what does this signify.

2) Where are we dealing with the fact that we need to make M cuts at given indices.

Thanx.
Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply
This is a great post! Thanks for sharing it and congrats you are a smart guy!
Re: 2.4.? Commonly used DP state domains (response to post by dimkadimon) | Reply
1. The Result[i1,i2,...,ik] has nothing is common with knapsack. It is array of results for general problem with multidim-like state domain. Knapsack was an example of such a problem with dim=2.

2. I added explanation for M matrix and about the way answer is got. About M and matr - it is usual thing. Mathematics is used to short variable names (1-2 letters) whereas in programming short names is bad habbit. I have a strong feeling against naming a matrix with one letter, sorry=) By the way, didn't you notice that state result is denoted as R in text but as res in code?...

3. Changed l,m,r to L,M,R. (l+1) looks really weird=) Question mark represents something that depends on the problem. It is usually neutral element i.e. 0 in combinatoric problem, +inf in minimization problem, -inf in maximization problem. I don't want to explain it here and there may be exceptions. That's why I just put question mark. Look one of examples and you'll see 10^18 in this place.

a represents additional parameters. It must be explained somewhere in the recipe=) I added a note on this to the first place it is met.

I don't like that additional parameters are represented by letter "a". Because it is english article also... I've enclosed parameter "a" in quotes in most places in text so that the do not confuse reader.
Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply
For substrings of a given string. Can you avoid using 'l' in the code, because it looks too similar to one. You can use L and R instead. What is "tres=?;"? What is a in this case and is it actually used in the code?
Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply
For the subsets of a given set you should mention that M[x,y] is the distance between cities x and y. You should use M in the code (instead of matr). You should explain the reasoning behind R[X,a]+M[a,0]: R[x,a] is the shortest path that visits every node once starting from node 0, so R[X,a]+M[a,0] is the shortest Hamilton cycle for X.
Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply
For the multidimensional array, I don't understand what does Result[i1][i2][i3]...[ik] represent in terms of the Knapsack problem? Does it mean the maximum cost that we can obtain by using i1 number of items 1, i2 number of items2, ..., ik number of k-th item? If so, then it is no longer 0-1 Knapsack, but more like unbounded Knapsack. By the way, it will be great if you can use the Knapsack example for all the representation types.
Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply
Thank you! This is the most useful recipe I have read so far. Perhaps it will finally help me to understand DP and move to yellow...
Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply
This recipe is great, in my opinion, considering there's a few interesting tutorials about dp in the web (not just knapsack and LCS but with some more content) if any. Sought for one some time ago (especially wanted to read about dp over subsets) and now I have a chance to read it. I mean it's good not only for Cookbook but for me so thank you very much.
[ 1 2 ]    NEXT >

RSS