Kindly Suggest Algorithms for the following programs.

[Nikhar]

Note:- I am NOT asking you to write the program for me. I am NOT asking you to do the homework for me either. All I am asking you is if you could suggest an algorithm for me.


Present below are two algorithms. Can you please suggest me an algorithm to make the c++ program for them.Thanks in advance. I previously asked this question. People asked me to solve it via backtracking or dynamic programming. At that time, I didn't know about backtracking or dynamic programming. Now, I have some idea about it. Yet, I am unable to figure out what exactly shall I do. Kindly suggest a suitable algorithm. I'll be highly obliged.

Problem 1 : Grid game

You are given a square grid of positive and negative numbers. You have to start at the top left corner of the grid and find a path to the bottom-right corner. In each step, you are only allowed to move one position to the right or one position down. As a special bonus, you are allowed at most one move that can be either to the left or up. Note that you are allowed to visit a position more than once as a result of this special move.

Your aim is to find such a path that has the maximum weight, where the weight of a path is the sum of all the numbers visited along the path.
Input format

The first line of the input contains one integer N, the number of rows and columns in the grid. Lines 2 to N+1 describe the N rows of the grid. Each of these N lines of input consists of N space separated integers, corresponding to the numbers in one row.
Notes

In all cases, N ≤ 2000. Each number in the grid is guaranteed to be less than 1000.

Sample Input
4
12 -16 10 -12
-16 13 -14 7
7 -4 16 -15
-7 16 -9 8
[B]

--------------------------------------

Problem 2 : Choosing chocolates

Santa Claus has lined up a row of bowls, each containing some chocolates. Nikhil has been told that he can pick up as many of these bowls as he wants, provided that he never picks two consecutive bowls.

Your aim is to help Nikhil choose a set of bowls so that he maximizes the number of chocolates that he picks up.
Input format

The first line of the input contains one integer N, the number of bowls. This is followed by a line containing N integers, describing the number of chocolates in each of the N bowls.
Notes

In all cases, N ≤ 100,000.

Sample Input

10
30 10 8 20 11 12 25 13 20 19

[jsmith]

Well I think we already did give you enough hints at algorithms.

Both problems can be solved using the same technique. The technique depends upon whether your requirements
are simply to output the best score or to output the best score AND the best "path".

In both cases, you can solve fairly trivially using recursion and a depth first search.

I wrote a program to solve the first problem. I'll give you the skeleton.

typedef long                            NodeScore;
typedef std::pair< unsigned, unsigned > Coord;
typedef std::vector< Coord >            Path;

static const NodeScore grid[4][4] = {
   {  12, -16,  10, -12 },
   { -16,  13, -14,   7 },
   {   7,  -4,  16, -15 },
   {  -7,  16,  -9,   8 }
};


// c is the coordinate you are currently at.  (0,0) is the top left;  (3,3) is the destination.
// usedSpecial is a flag indicating whether or not the special bonus move (up or left) has been used.
// pathSoFar is the list of coordinates visited so far to get to c.
// scoreSoFar is the sum of the grid values on pathSoFar.
// bestScore and bestPath are used to keep track of the highest score and its associated path found so far.
//
// When c == (3,3), you are at the end of the recursion.  At that time, see if the score so far is higher
// than the bestScore and update accordingly.
// If you are not at the end yet (3,3), then you will recursively call solve_grid up to four times, depending
// upon whether it is possible to move up, down, left, or right.
void solve_grid( Coord c, bool usedSpecial, Path pathSoFar, NodeScore scoreSoFar,
    NodeScore& bestScore, Path& bestPath )
{
}

int main() {
    Path      bestPath;
    NodeScore bestScore( 0 );

    solve_grid( Coord( 0U, 0U ), false, Path(), 0, bestScore, bestPath );
}

[jsmith]

Notice that the above algorithm does a depth first brute force search. Brute force means that it will find every single path
from start to finish and check every one of them.

You can use a similar technique for the second problem.

[Nikhar]

Thanks a lot Jsmith for your reply.
Btw, did you purposefully leave the solvegrid function blank?

Also, just another question. I think I have understood this brute force approach. Is there any other way to do it? Because, as far as I know, Brute force algorithm is very time costly.So, for longer arrays, this program is bound take a lot of time as it would go through each and every possible path.

[jsmith]

Yes, I wasn't going to give you the entire solution. From the comments I gave you should be able to write the
body of the function.

There may be other ways, but they will be much more complicated, and unless your professor is looking for
a solution based on graph theory, the brute force way is the way to go (especially if s/he is expecting a
recursive solution).

If it is not necessary to keep track of the best path, but only the best score, the program can be sped up by
an order of magnitude at least by removing all the vectors.

[jsmith]

Just doing a quick mental exercise, given an MxN grid, and forgetting the special bonus move, the number
of ways of getting from point (0,0) to (M-1,N-1) is MN + 1. Thinking about the special bonus move, it is
going to multiply that number in some way by a constant which is no more than 2*(M+N-1) (and probably
way less). Essentially it means that you would need an enormous grid to cause a brute force algorithm
to be too slow.

[jsmith]

EDIT: above math is totally wrong. Disregard. Though it's still O( MN ) possibilities.

[jsmith]

EDIT: Forgetting the special bonus move, if you were to tilt the grid 45 degrees so that (0,0) was the
root of the "binary tree" formed by the resulting grid, then the number of ways to get to the point
(M,N) from (0,0) is given by applying pascal's triangle rule to each vertex.

[chrisname]

Why would you post four times in a row? There's an edit button, you know. :l

[jsmith]

Why would you spend the energy asking the question when it really doesn't matter?
If you must know, the New Reply button is bigger and easier to hit.

[blackcoder41]

Why would you spend the energy asking the question when it really doesn't matter?
If you must know, the New Reply button is bigger and easier to hit.

haha, that's right.. ^ ^

[chrisname]

Why would you spend the time answering a question if it "doesn't matter?"

chrisname: 1, jsmith: some number presumably larger than 1.

[jsmith]

So constructing a 12x12 grid formed by making a 3x3 grid of the given 4x4 grid... it takes quite a while to churn
through all the possibilities (like, I killed it after more than a minute). When I removed the code that keeps track
of the best path (in addition to the best score), the execution time was reduced to about 2.2 seconds. Bear that
in mind -- I don't want to misguide you thinking your instructor just wants any recursive solution whereas in fact
s/he wants a more optimal solution.

[Nikhar]

Since the grid is always gonna be square, it would take o(n^2) time. Exponential!
As you can see in the question, the input can be as large as N=2000. Just imagine the time this would take. And to make things worse, the time limit is 2,000!

Btw, I am not doing it for an instructor. I'm preparing for an exam! And the exam's tomorrow!!! I am really panicking now. I have so much to do and so less time. Save me!


I don't need the best path but just the best score.

Hey, Jsmith, Can I ask you for a favour? Can you like give me your MSN or yahoo id? Otherwise, I'll flood this forum by tonight as I know I am gonna have many doubts. And its like really annoying to keep refreshing to see if someone has posted a reply.

Edit:- I don't know about rotating a tree! Panicking!

[jsmith]

Ok, there's another way, but I haven't come up with the complete solution. Work backwards.
(The part I haven't taken into account yet is the special move, so the below is not considering
that possibility. It will have to be up to you to solve that part, but I _think_ it isn't too hard.

Create a second grid and fill it with zeroes. The cells in this grid will contain the best score
if you started at that cell.

To run this algorithm, start at cell [3,3] (the end). If you started there, your
best score would be 8. Now work backwards. What if you started at cell
[3,2]? Best score would be -15 + 8 = -7, since there is only one way to go.
From cell [2,3], then best score would be -9 + 8 = -1. Starting at cell [2,2],
you have two ways to get to the end, so the best score from there is
16 plus the max score of the two ways to go. You've already completed
those calculations, so the best score is 16 + -1 = 15.

Continue working backwards until you've reached [0,0] and all cells are
filled. This will give you a root node [0,0] score of 54 if your program is
correct.

Note that the above algorithm is still N^2 for an NxN grid; it must visit all
the nodes.

I'll leave it up to you to figure out how to include the special move. Including
it will require a second N^2 pass at the grid, but 2N^2 is still O(N^2).

[Nikhar]

Ok. Thanks Jsmith. Now, this was more easy to understand. :)

Btw, Kindly have a look at the program I made for chosing chocolates and temme where I went wrong.

http://www.cplusplus.com/forum/general/18588/