Algorithm help

Hello,

I've come across two problems given on a contest this year that I don't really know how to solve. This isn't really a C++ question as much as it is an idea / algorithm one, so I'm not asking for any code, just a description of an efficient algorithm...

The first one sounds like this:

Given two arrays of numbers a_1, a_2 ... a_n, and b_1, b_2 ... b_n, find the length of the maximum contiguous subsequence m_1, m_2 ... m_x which has both a_1, a_2 ... a_x and b_1, b_2 ... b_x in increasing order, knowing that you can perform as many inverse operations as you wish. An inverse operation means inversing the contents of a_j and b_j

Example:

the file in.in contains:

Code:

12
7 5 8 2 7 2 1 0 5 3 1 3
3 6 1 6 3 0 0 4 3 2 4 3

the file answer.out contains:
3

we inverse number 8 (0 and 4) and we get the maximum increasing contiguous subsequence from 7 to 9 (1 4 5 and 0 0 3)

I've no idea how to approach this one, the closest i've come to increasing subsequence is the maximum sum subsequence...
Dynamic programming maybe?



The second one you're given an NxN array like this one:

Code:

4
0      1      4     –1
0     –1      0     –1
0      0      0      0
5     –1     –1      1

And you have to find:
- The maximum sum you can get
- Maximum number of squares you can get on
Knowing that:
- You can only move on squares that have the value > -1
- You can only move down and to the right
- You need to reach the (N, N) coordinates

So, considering the example, the answer to the maximum sum you can get would be 6 ( (1,2), (1,3) and (N, N) ) and the maximum number of squares you can get on would be 10...

I have an idea for this one, it seems to work for this example, but im not sure it would on others...

1. Have a function dead_end() that returns 0 if a square lets you move to another square and 1 if it doesn't.
2. Walk through the array one by one, calling dead_end() every iteration.
3. If dead_end() returns 0, update the max_sum and max_squares variables, skip the square otherwise. Also skip it entirely if it's -1.

I realize you only have my word on it that this isn't actually homework, so as I said, I'll be more than happy with just getting a few pointers on how to approach these...

Thanks in advance..

Sorry to bump this, but no one can give me any ideas? Maybe a link to a site specialising in this sort of stuff, anything?

First of all, your descriptions of the problems are ambiguous and inaccurate. For example, in the first problem your sequences "a_1, ..., a_x" and "b_1, ..., b_x" falsely imply that both subsequences have to start at the beginning, but your example contradicts that. Your example also indicates that the subsequences have to be nondecreasing, not increasing. I can't even begin to understand what the second problem is. It's much easier to describe the problems accurately than to solve them, so if you want help you should do that first.

Having said that, if I understand the first problem correctly, the solution is pretty simple. For each horizontal position i from 2 to 12, let c(i) = T if either

Code:

((a_{i-1} <= a_i) and (b_{i-1} <= b_i))

or

Code:

((a_{i-1} <= b_i) and (b_{i-1} <= a_i))

, and c(i) = F otherwise. By convention we can just let c(1) = T. Hence the values c(i) for c=1 to 12 are

T F F F T F F T T F F F

and now you just look for the longest subsequence which has all T's except possibly for an F at the beginning. This is the subsequence "F T T" from i=7 to i=9. In general, for sequences with N elements, the running time is O(N). You do one O(N) sweep to compute the c(i)'s and another O(N) sweep to read off the longest subsequence.

I found a link on Google corresponding to this problem. Unfortunately I can't read Romanian, so I don't know what it's about.

http://lsp.vs.edu.ro/pracsiu/Centrul...cte%209-12.htm

Originally Posted by robatino

First of all, your descriptions of the problems are ambiguous and inaccurate. For example, in the first problem your sequences "a_1, ..., a_x" and "b_1, ..., b_x" falsely imply that both subsequences have to start at the beginning, but your example contradicts that. Your example also indicates that the subsequences have to be nondecreasing, not increasing. I can't even begin to understand what the second problem is. It's much easier to describe the problems accurately than to solve them, so if you want help you should do that first.

Having said that, if I understand the first problem correctly, the solution is pretty simple. For each horizontal position i from 2 to 12, let c(i) = T if either

Code:

((a_{i-1} <= a_i) and (b_{i-1} <= b_i))

or

Code:

((a_{i-1} <= b_i) and (b_{i-1} <= a_i))

, and c(i) = F otherwise. By convention we can just let c(1) = T. Hence the values c(i) for c=1 to 12 are

T F F F T F F T T F F F

and now you just look for the longest subsequence which has all T's except possibly for an F at the beginning. This is the subsequence "F T T" from i=7 to i=9. In general, for sequences with N elements, the running time is O(N). You do one O(N) sweep to compute the c(i)'s and another O(N) sweep to read off the longest subsequence.

I found a link on Google corresponding to this problem. Unfortunately I can't read Romanian, so I don't know what it's about.

http://<ol class="decimal"><li style....htm</li></ol>

First problem:

Yes, you're right, the example is correct. And, yes, non-decreasing, not necessarily increasing. I'm sorry, it's pretty difficult to translate in english. That link doesn't work, but the problem is from a romanian contest, so that's probably the problem statement in romanian.

Anyway, let me try again, based on that same example:

you're given two vectors:

Code:

7	5	8	2	7	2	1	0	5	3	1	3  //vector a
3	6	1	6	3	0	0	4	3	2	4	3  //vector b

You can switch any two values a_i and b_i. Using such switch operations, what is the length of the maximum common non-decreasing subsequence you can obtain? In this case, by switching a_8 and b_8 (0 and 4), we get 3.

I see the logic behind your method. Could you tell me if this code (based on the example, so far) is correct? Seems to be giving correct results, at least in this case. One thing, though, shouldn't we have something that checks if c[0] <= c[1] or not before assigning it to true?

Code:

#include <iostream>
using namespace std;

int main ()
{
	int a[12] = {7,5,8,2,7,2,1,0,5,3,1,3};
	int b[12] = {3,6,1,6,3,0,0,4,3,2,4,3};

	bool c[12];
	int length = 0;
	int ltemp = 0;

	c[0] = true;
	for ( int i = 1; i < 12; ++i )
		if ( (a[i-1] <= a[i] && b[i-1] <= b[i]) || (a[i-1] <= b[i] && b[i-1] <= a[i]) )
		{
			c[i] = true;
		}
		else
			c[i] = false;
	for ( int i = 0; i < 12 - 1; ++i )
	{
		if ( c[i+1] == true && c[i] == false )
			ltemp += 2;
		else if ( c[i+1] == true )
			++ltemp;
		if ( ltemp > length )
		{
			length = ltemp;
			ltemp = 0;
		}
	}

	cout << length << endl;

	return 0;
}

For the second problem:

You're given a matrix (bidimensional array), for example the one i posted in my o.p.
You start at (0,0) and have to get to (n-1,n-1) (to use C-style indexing), knowing that:

You can only move one box to the right or one box to the bottom of the matrix at a time.
If a box (any coordinates (i,j) where 0 <= i,j < n) contains the value -1, you have to skip it. If a box contains a value 0, you can get there. If a box contains a value higher than 0, it's considered, say, money, and you have to take it.

The question is:
What is the maximum sum of money you can collect going from (0,0) to (n-1,n-1)? And the number of boxes you move through to reach the end must also be max. It's pretty tricky, since, as seen in the example, you have to account for dead ends, you can't just walk the matrix and update a money variable...


Thanks a lot for your help, and don't hesitate to ask if you have any more questions.

For what they are worth here's my thoughts:
Problem 1:
Assuming the nondecreasing sequences need to be read left to right (if you flip the 7 and 3 at element 5 in the example you get a 4 element nondecreasing sequence going left to right) then you could find longest nondecreasing sequence(s) in each array and just flip the bracketing elements (start -1 and end + 1) to see if they extend the sequence.

Problem 2:
The max number of squares visited may not be the same sequence used to discover the max value obtained, as in the example. Are you supposed to have one, the other, or both? If you can only move down and to the right how can you back track? The maximum number of boxes visited without backtracking is 7, if I'm counting right. (00, 01, 02, 21, 22, 23, 33) or (00, 01, 02, 21, 22, 23, 33)

Problem 2:
First you need to find all possible ways to get from start to finish. As you find each solution, store the quality value (number of rooms, most gold, whatever) in an array. At the end just compare which is the highest or lowest value as needed.

To find all possible solutions, the easiest way is as follows:
1)execute a choice(Eg go right) untill you can't.
2)Then you choose the other choice.
3)Repeat 1 and 2 untill you reach a dead end
4) if the dead end is the finish, mark it as so.
5) backtrack to the previous square.
6) if possible make a choice you haven't yet at that square (eg go left if you are following the right wall unless you just came from the left. else if you are not at the start then go to step 5. if you are at the start you are done.
6) go to step 1)

The implementation of this can either be done using recursive functions, or your own stack object. I don't think there would be much difference between the two.

Originally Posted by elad

For what they are worth here's my thoughts:
Problem 1:
Assuming the nondecreasing sequences need to be read left to right (if you flip the 7 and 3 at element 5 in the example you get a 4 element nondecreasing sequence going left to right) then you could find longest nondecreasing sequence(s) in each array and just flip the bracketing elements (start -1 and end + 1) to see if they extend the sequence.

Problem 2:
The max number of squares visited may not be the same sequence used to discover the max value obtained, as in the example. Are you supposed to have one, the other, or both? If you can only move down and to the right how can you back track? The maximum number of boxes visited without backtracking is 7, if I'm counting right. (00, 01, 02, 21, 22, 23, 33) or (00, 01, 02, 21, 22, 23, 33)

1:
Not sure I follow...
if you flip 7 and 3 at 5, you get:

Code:

7	5	8	2	3	2	1	0	5	3	1	3
3	6	1	6	7	0	0	4	3	2	4	3

which is two, not four.

2:
Supposed to have both...


I'm not really familiar with backtracking, but I know recursive functions can be very slow. Can't this be solved by dynamic programming, maybe? I don't really know how to implement backtracking here.

By the way, King Mir, you said go left at step 6. You can't go left, you can only go to the right or down...

Problem 1:
if you flip element five you 3210 reading left to right and 0123 reading right to left. Of course, if you are only allowed to read left to right, then it's a moot point.

Problem 2:
If the final number of elements doesn't allow backtracking then the path 00, 10, 20, 30, 20, 21, 22, 23, 33 isn't valid, correct? Presumably, you can backtrack internally, but not backtracking to make a longer path.

This boils down to solving a maze with optimazation of points accumulated and maximum path length. If you've not written a maze solving program here's your chance. Briefly you need some way to keep track of where you are and where you've been. As indicated previously, this can be done using recursion or stacks. Define the board as a multidimensional array of type cell where cell is declared as a user defined type containing an int to indicate which row the cell in, an int to represent which column the cell is in, and an int value representing the 0, 2, 4, -1, etc. Have some way to determine whether a given cell has another cell to the right or down or not, either intrinsic to the cells declaration or outside the cell declaration in a validation function.

Here's a rough algorhythm using stacks that I think will work if you want to go that way. Start by pushing the cell at 00 it on the stack. Always look in one direction first (either right or down), say down. So look down from 00 at cell 10. 10 is not the end and is a valid move so push it on the stack and keep going down 'til the stack includes 00, 10, 20, 30 since they are all valid moves. Then since there isn't a 40 look to the right of 30 at 31, which is a -1. This means that 30 has no down and right is invalid, so 30 is a dead end, so pop 30 from the stack. Now look right (you've already looked down from here since it's already on the stack) from the cell at the top of the stack, that is, look at 21 from 20. 21 is not the end and is valid so keep pushing cells on the stack until you get to 23 (31 and 32 aren't the end and aren't valid when you look down from 21 and 22 so they aren't added to the stack although 21 and 22 are added to the stack going from 20 to 23). Looking down from 23 is 33, which is the end, so you now have a valid path. Determine the length, value, and cells in the path and store the values somewhere for later comparison with any other valid paths. Then pop 33 from the stack and rexamine all the remaining paths by examining any down or right options left in the top cell of the stack and popping any cell that has had both right and down looked at already or are invalid. In essence in this scenario after each push you look down from the cell at the top of the stack and after each pop you look right from the cell at the top of the stack.

I think this is correct:

Code:

#include <iostream>

int main()
{
  int a[12] = {7,5,8,2,7,2,1,0,5,3,1,3};
  int b[12] = {3,6,1,6,3,0,0,4,3,2,4,3};
  int length = 1;
  int ltemp = 1;

  for (int i=1; i<12; i++) {
    if ((a[i-1] <= a[i] && b[i-1] <= b[i]) || (a[i-1] <= b[i] && b[i-1] <= a[i])) ltemp++;
    else ltemp = 1;
    if (ltemp > length) length = ltemp;
  }
  std::cout << length << std::endl;
}

I found the link by doing a Google search for "7 5 8 2 7 2 1 0 5 3 1 3". There were two matches, this thread and that link. It worked right after I posted, so they took it down.

Edit: The above code should work for arbitrary array length N >= 1 instead of 12. One needs to check for N == 0 first and return length 0 immediately in that case.

Originally Posted by Sfel

2:
Supposed to have both...


I'm not really familiar with backtracking, but I know recursive functions can be very slow. Can't this be solved by dynamic programming, maybe? I don't really know how to implement backtracking here.

By the way, King Mir, you said go left at step 6. You can't go left, you can only go to the right or down...

I ment down.

I don't think the overhead of function calls is that significant. But like I said you could use your own stack, like the STL stack container. You then need some way to store each location as an object with some sort of references to it's two branches.

I don't know a thing about dynamic programming, but backtracking just means everytime you go to a new location, you put that location on a stack. Then to backtrack, you pop the last item off the stack. Read about stack datastructures.

All right, I'll look into it, thank you.

For the second problem, convert it into an equivalent maximum-weight graph problem solvable with Dijkstra's algorithm. Use dynamic programming to find the path between squares [0] and [N^2 - 1] with the most weight. It should run in O(N^2 log N) time if you do the necessary optimizations (eg. using a Fibonacci heap). To check which squares are reacheable, save the intermediate results from the algorithm; read the Wikipedia article for details.

Dijkstra's algorithm is simple and easy to understand; if you're a speed freak (or the organizers of this contest are) some specialized, optimized, esoteric maze-solving algorithms will undoubtedly perform a lot faster for large (say, 1000+) grid sizes.

I don't know anything about graphs - I doubt they expected such a solution anyway, since graphs aren't usually used at this level of the competition...

I guess I'll ask my teacher how I should approach it. Or maybe it's just beyond me right now...

Anyway, thanks everyone!

Your square maze is already a graph; each number represents the cost to each other square. You need to find a path from (0, 0) to (N-1, N-1) with the maximal cost.

King Mir: your solution is simple, but slow; an NxN square may contain as many as C(2(N-1), N-1) possible paths from start to finish. That's at least about 2^N.

Sfel: this is easy to implement, actually. It's very straightforward to implement Dijkstra's algorithm in code. Just use the given rewards as a cost of valid paths, and use the top-left square (0, 0) as a starting point. As a bonus, the algorithm will give you the cost of the path from (0, 0) to every other square in the grid, not just the endpoint. You can then use these costs to determine whether a given square is reachable or not.

Okay, here's a brief walkthrough:

Given maze of size 4:

0 1 -1 –1
2 –1 3 –1
4 0 1 0
5 –1 –1 1


Using Dijkstra's algorithm, we see that the shortest paths from (0, 0) to the various squares are:

Maximum reward from square (0, 0) to...

(0,0) 0
(0,1) 1
(0,2) inf
(0,3) inf
(1,0) 2
(1,1) inf
(1,2) inf
(1,3) inf
(2,0) 6
(2,1) 6
(2,2) 7
(2,3) 7
(3,0) 11
(3,1) inf
(3,2) inf
(3,3) 8

The answers may not be correct; I just solved it "by eye". Just try to get the gist of it.

We see that distance to (3, 3) is 8, which is the maximum possible. By checking for each square, we see that only those with non-negative rewards are reachable from the starting square. This is the motivation for using a big negative value as the illegal

This algorithm has the bonus of being able to check the reachable squares and their associated rewards, starting with any given square, not just (0, 0).


PS: robatino's code for problem 1 is correct and easily scaled to larger lists, up into to the hundreds of millions. Happy cheating.