CODEWITHSUNDEEP
algorithmdynamic-programming
A. Sam
A. Sam

Reputation: 893

How do we solve the given scenario efficiently?

We are given a maze in which we need to visit as many rooms as possible. The specialty of the maze is that once you enter any room it will only lead you to rooms with a higher tag in the direction you move . B and C decide to move in opposite directions trying their luck to maximize the number of rooms they search .(They can start with any room , need not be the same)

We need to find out the maximum number of rooms that can be searched.

1. Access to any room with a higher tag is allowed, not just adjacent rooms or the next room with a higher tag. 
2. Tags are unique.

So given the input: 

12 11 10 1 2 3 4 13 6 7 8 5 9 
the answer is 12: (1,2,3,4,6,7,8,9) for B and (5,10,11,12) for C.

I thought of solving this using longest increasing sub sequence first from right and then from left.And the count of unique elements in above two sub sequence would be the answer.

But my logic seems to fail,how can this be done?

Upvotes: 4

Views: 159

Answers (2)

phoenix
phoenix

Reputation: 3159

My program below computes the maximum number of rooms searched. This has time complexity of O(n^3). I modified the DP algorithm for computing the longest increasing sequence available online to solve OP's problem. This also addresses OP's concerns on arrays like {1,4,6,2,5}. I rightly get the max value as 5 for the previous example. So, I used the idea from @BeyelerStudios that we need to compute the longest increasing subsequence from both left to right and from right to left. But, there is a caveat. If we compute the Left to right max sequence, the sequence from right to left should be on the remaining elements. Example:
For the array {1, 4, 6, 2, 5}. If the forward rooms selected are {1, 4, 5 }, then the reverse longest increasing sequence should be computed on the left out elements {6, 2}.

Below is my program:

#include <iostream>
using namespace std;


// compute the max increasing sequence from right to left.
int r2lRooms (int arr[], int n) 
{

    int dp[n];
    int i =0, j = 0;
    int max = 0;

    for ( i = 0; i < n; i++ ) {
        dp[i] = 1;
    }

    for (i = n-2; i >= 0; i--) {
        for ( j = n-1; j > i; j-- ) {
            if ( arr[i] > arr[j] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }
    }

    for ( i = 0; i < n; i++ ) {
        if ( max < dp[i] ) {
            max = dp[i];
        }
    }
    return max;

}


// compute max rooms.
int maxRooms( int arr[], int n )
{

    int dp[n], revArray[n];
    int i =0, j = 0, k = 0;
    int currentMax = 0;
    int forwardMax = 0, reverseMax = 0;

    for ( i = 0; i < n; i++ ) {
        dp[i] = 1;
    }

    // First case is that except for first elem, all others are in revArray
    for (i=1; i < n; i++, k++) {
        revArray[k] = arr[i];
    }
    reverseMax = r2lRooms (revArray, k);
    forwardMax = 1;
    if (currentMax < (forwardMax + reverseMax)) {
        currentMax = forwardMax + reverseMax;
    }
    cout << "forwardmax revmax and currentmax are: " << forwardMax << " " << reverseMax << " " << currentMax << endl;
    cout << endl;

    for ( i = 1; i < n; i++ ) {
        k = 0;
        forwardMax = 1;
        reverseMax = 0;

        cout << "Forward elems for arr[" << i << "]=" << arr[i] << endl;

        for ( j = 0; j < i; j++ ) {
            if ( arr[i] > arr[j] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
                forwardMax = dp[i]; 
                cout << arr[j] << " ";
            }
            else {
                // element was not in DP calculation, so put in revArray.
                revArray[k] = arr[j];
                k++;
            }
        }
        // copy the remaining elements in revArray.
        for ( j = i+1; j < n; j++ ) {
            revArray[k] = arr[j];
            k++;
        }
        cout << endl;
        reverseMax = r2lRooms (revArray, k);
        if (currentMax < (forwardMax + reverseMax)) {
            currentMax = forwardMax + reverseMax;
        }
        cout << "forwardmax revmax and currentmax are: " << forwardMax << " " <<  reverseMax << " " << currentMax << endl;
        cout << endl;
    }
    cout << " Max rooms searched " << currentMax << endl;
    return currentMax;
}

int main (void) {

    int arr[] = {12, 11, 10, 1, 2, 3, 4, 13, 6, 7, 8, 5, 9 };
    int size = sizeof(arr) / sizeof(int);

    cout << maxRooms (arr, size);


}

Upvotes: 1

Sorin
Sorin

Reputation: 11968

I think the trick is at the intersection, where B and C might share a value or there's options to go around that (say the sequence is 12 11 10 1 2 3 4 <3 5> 13 6 7 8 9 The extra numbers here adds 1 to the solution, but doesn't change the result for either longest increasing sub-sequences.

So the only problem is the one room in the middle, since on both side the values chosen diverge.

What I would do is this: do the longest subsequence in one direction, figure out a solution (any solution), take out the numbers in the solution and do the longest subsequence in the other direction. This way if there's a way around the crossing room in the middle the second pass will prefer it, unless that's the chosen number is really needed. To check for that do the same thing, but build the first subsequence in the opposite direction and the second one (after removing the solution) in the direction chosen initially.

Complexity remains O(N) but with a slightly higher constant factor.

Upvotes: 1

Related Questions