JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums TopCoder Cookbook Algorithm Competitions - New Recipes 2.4.? Commonly used DP state domains << 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?
 Forums TopCoder Cookbook Algorithm Competitions - New Recipes 2.4.? Commonly used DP state domains Previous Thread  |  Next Thread << PREV    [ 1 2 ]