JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
<< PREV    [ 1 2 ]
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 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
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 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
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 M.G.Z) | Reply
Fixed that. Thank you=)
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 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?
<< PREV    [ 1 2 ]

RSS