Thread: Algorithm help

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.