JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Questions abuot the paragraph which discusses the "StarAdventure" problem | Reply
In the paragraph which discusses the StarAdventure problem, I read:
"take every possible pair of, k (where j < k), and for each i (1 i < j) consider the move from position (i-1,j,k) to position (i,j,k)."

What does "i (1 i < j)" mean? And why here take the pair of k (where j < k)?

Thanks a lot!
Re: Questions abuot the paragraph which discusses the "StarAdventure" problem (response to post by cj_df) | Reply
- I have the same question..
- Also please clarify an example for the process..

Thanks
Re: Questions abuot the paragraph which discusses the "StarAdventure" problem (response to post by betamoo) | Reply
Hi all,
I'm wondering if anyone figure out the solution and have passed the system tests based on algorithm described by the author of this tutorial.

I have also checked the solutions of the competitors in this contest. most of them (as I understand) use a dp strategy based on the steps of each of the three paths (they all need to move level.size() + level[0].size() - 2 steps)

For the editor's strategy (based on rows), I only know how to initialize the first row
for (int i = 0; i < N; i++)
    for (int j = i+1; j < N; j++)
        for (int k = j+1; k < N; ++k)
            Max[i][j][k] = accumulate(level[0].begin(), level[0].begin() + (k+1), -'0'*k); 

the number of stars in all the cells of first row till cell k.

and how to get the result when reach the last row
for (int i = 0; i < N; i++)
    for (int j = i+1; j < N; j++)
        for (int k = j+1; k < N; ++k)
        {
            int starsOfLastRow = 0;
            for (int x = i+1; x < N; ++x)
            {
                if (x!=j && x!=k)
                    starsOfLastRow += level[M-1][x] - '0';
            } 
            res = max(res, Max[i][j][k] + starsOfLastRow);
         }


I'm struggling to figure out the recursion to process Max[i][j][k] of the rightward moves while processing each row.

Any one can help on this?

Thanks a lot in advance!
Re: Questions abuot the paragraph which discusses the "StarAdventure" problem (response to post by chuchao333) | Reply
I too have trouble to understand the solution. However, I am wondering why a simple approach wouldn't work. Make one trip and take the max route (very simple dp); then erase all the stars on the route; do the same thing again two more times and sum up all the result should be the answer.

Why the solution sound so complicated and the problem is listed as 'hard'? Am I missing something?
Re: Questions abuot the paragraph which discusses the "StarAdventure" problem (response to post by ouzh) | Reply
I also had the same idea as ouzh, implemented this approach and it worked just fine. It is so much simpler and is efficient.

I really donĀ“t understand why explain in a tutorial a solution that is more complicated when there is a better and simpler solution.
Re: Questions abuot the paragraph which discusses the "StarAdventure" problem (response to post by ouzh) | Reply
Yes, on a first look it seems as if the solution is pretty trivial. Since we know how to calculate the maximum stars collected for a single run, let's just mark the cells from where the stars have been collected as 0. And rerun again, and similar to what we did after the previous run. mark the cells involved to 0, and then do a final third run. What we will get will be the answer! WRONG.

The approach used for a single run, tries to take a path which will maximize the total stars. But here we have the ability to run three runs. So the approach has to be cover the maximum possible number of cells using the three paths. Consider this test case, and watch the above solution fail : "0 9 8 3 4 3 4", "2 3 4 2 4 2 3", "2 3 4 2 3 4 2".

To do that the solution is pretty tough. That's why this problem is listed under Advanced category in the DP tutorial.

The breakthrough is to realize that there are three paths going from upper left corner, to lower right corner. And they all need to go through all the rows at some point of the time.

So let us have an array[50][50][50], where array[i][j][k] will depict the left path to be in column i, middle in column j, and right in column k.

Another thing is the paths must not intersect in rows 1 till n-2. They can overlap in row 0 and row n-1. (Use a few examples to convince yourself.)

So we begin our journey from Row 0.

array[i][j][k] where i < j < k, will be equal to sum (level[0][i]) 0<=i <= k.

Now comes the route from Row1 to row n-2,

array1[i][j][k] where i<j><k = array[i][j][k] + level[1][i] + level[1][j] + level[1][k].

This depicts the movement in vertical direction of all the three paths.

But the paths may move towards right in a given row as well.

To manage that also, we need to consider 8 scenarios,

where left moves from left-1 to left, but middle, and right come vertically down.

That would be array1[i][j][k] = array1[i-1][j][k] + level[1][i];

other 7 cases are like, (i,m-1,r) -----> (i,m,r), (i-1,m-1,r) -----> (i,m,r) ....Hope you are getting it.
RSS