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
the file in.in contains:
the file answer.out 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
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:
And you have to find:Code:4 0 1 4 –1 0 –1 0 –1 0 0 0 0 5 –1 –1 1
- The maximum sum you can get
- Maximum number of squares you can get on
- 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..