Weekly Algorithm for this week. From TopCoder. Level 500.

[Seabook]

This is Weekly Algorithm. I thought we should start from now on a bit by bit.
Every Monday, I will post an algorithm or puzzle here. People can discuss your solution or show ur code in the post by reply.

After a month or 2, I will find the best solutions in the post and rearrange them in the top announcement post, also put them into svn.

As owner, I will always participate and try my utmost to solve the problems every week hopefully.

Happy Coding,
Seabook


Problem Statement
????
Often the maintenance staff of a large building wants to verify that the elevator in the building is being used appropriately. The manufacturer designates safety limits regarding the maximum number of people that should be on the elevator at the same time. Also, there is a physical limitation as to how many people can actually be in the elevator simultaneously. The building in question has very primitive sensing equipment, and only has data telling how many people entered and exited on a particular stop. That is, the data does not explicitly state how many people were on the elevator at any given point in time.
You are to write a class ElevatorLimit, with a method getRange, which takes as parameters a int[] enter, a int[] exit, and an int physicalLimit, where the ith element in each int[] indicates the number of people that entered and exited, respectively, the elevator on the ith stop. At each stop people exit the elevator first, and then people enter. physicalLimit is how many people are physically capable of being in the elevator simultaneously. You are to determine the maximum and minimum numbers of people that could have been on the elevator before the simulation begins, and return these values in a int[] containing exactly two elements. The first element of the return value is the minimum, and the second element is the maximum number.
If the data entered yields an impossible situation, you are to return an empty int[].
Definition
????
Class:
ElevatorLimit
Method:
getRange
Parameters:
int[], int[], int
Returns:
int[]
Method signature:
int[] getRange(int[] enter, int[] exit, int physicalLimit)
(be sure your method is public)
????

Constraints
-
enter and exit will have between 1 and 50 elements, inclusive.
-
enter and exit will have the same number of elements.
-
Each element of enter and exit will be between 0 and 1000, inclusive.
-
physicalLimit will be between 1 and 1000, inclusive.
Examples
0)

????
{1,0}
{0,1}
1
Returns: { 0,  0 }
With a physicalLimit of one person on the elevator at a time, there had to be 0 to start with.
1)

????
{1,0}
{0,1}
2
Returns: { 0,  1 }
With a physicalLimit of 2 people, the elevator could have started with 0 or 1 people on it.
2)

????
{0,1}
{1,0}
1
Returns: { 1,  1 }

3)

????
{0,2}
{1,0}
1
Returns: { }
Since there is only a maximum of 1 person, 2 people cannot get on at the second stop. Therefore, there is no possible solution.
4)

????
{6, 85, 106, 1, 199, 76, 162, 141}
{38, 68, 62, 83, 170, 12, 61, 114}
668
Returns: { 223,  500 }

5)

????
{179, 135, 104, 90, 97, 186, 187, 47, 152, 100, 119, 28, 193, 11, 103, 100,
 179, 11, 80, 163, 50, 131, 103, 50, 142, 51, 112, 62, 69, 72, 88, 3, 162,
 93, 190, 85, 79, 86, 146, 71, 65, 131, 179, 119, 66, 111}
{134, 81, 178, 168, 86, 128, 1, 165, 62, 46, 188, 70, 104, 111, 3, 47, 144,
 69, 163, 21, 101, 126, 169, 84, 146, 165, 198, 1, 65, 181, 135, 99, 100,
 195, 171, 47, 16, 54, 79, 69, 6, 97, 154, 80, 151, 76}
954
Returns: { 453,  659 }

6)

????
{2}
{3}
2
Returns: { }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

[Seabook]

I took a peak. It's not very difficult. Easy to find the math function behind the problem. But maybe there is a better algorithm. Will present my solution late tonight.

[Seabook]

//Stupid Solution, easy to write and easy to understand.
//Wish guys could find a better solution for this. I am pretty sure there should be a good math function behind this.

package com.seabook.google.algorithm;

import java.util.ArrayList;
import java.util.List;


public class ElevatorLimit {
    public static void main(String[] args) {
        ElevatorLimit elevatorLimit = new ElevatorLimit();
        printResult(elevatorLimit.getRange(new int[]{1,0}, new int[]{0, 1}, 1));
        printResult(elevatorLimit.getRange(new int[]{1,0}, new int[]{0, 1}, 2));
        printResult(elevatorLimit.getRange(new int[]{0,1}, new int[]{1, 0}, 1));
        printResult(elevatorLimit.getRange(new int[]{0,2}, new int[]{1, 0}, 1));
        printResult(elevatorLimit.getRange(new int[]{6, 85, 106, 1, 199, 76, 162, 141}
        , new int[]{38, 68, 62, 83, 170, 12, 61, 114}, 668));
       
        printResult(elevatorLimit.getRange(new int[]{179, 135, 104, 90, 97, 186, 187, 47, 152, 100, 119, 28, 193, 11, 103, 100,

                 179, 11, 80, 163, 50, 131, 103, 50, 142, 51, 112, 62, 69, 72, 88, 3, 162,
                 93, 190, 85, 79, 86, 146, 71, 65, 131, 179, 119, 66, 111}

        , new int[]{134, 81, 178, 168, 86, 128, 1, 165, 62, 46, 188, 70, 104, 111, 3, 47, 144,

                 69, 163, 21, 101, 126, 169, 84, 146, 165, 198, 1, 65, 181, 135, 99, 100,

                 195, 171, 47, 16, 54, 79, 69, 6, 97, 154, 80, 151, 76}, 954));
       
        printResult(elevatorLimit.getRange(new int[]{2}, new int[]{3}, 2));
    }
   
    public static void printResult(int[] result) {
        if (result == null || result.length == 0) {
            System.out.println("{ }");
            return ;
        }
        System.out.println("{" + result[0] + ", " + result[1] + "}");
    }
   
    public int[] getRange(int[] enter, int[] exit, int physicalLimit) {
        List<Integer> storage = new ArrayList<Integer>();
        for (int start = exit[0]; start <= physicalLimit; start ++ ) {
            boolean valid = true;
            int temp = start;
            for (int i = 0; i < exit.length; i++) {
                temp -= exit[i];
                if (temp < 0) {
                    valid = false;
                    break;
                }
                temp += enter[i];
                if (temp > physicalLimit) {
                    valid = false;
                    break;
                }
            }
            if (valid)
                storage.add(start);
        }
       
        if (storage.size() ==0 ) {
            return new int[]{};
        }
       
        return new int[] {storage.get(0), storage.get(storage.size() - 1)};
    }
}

[Seabook]

//Improve the algorithm, just store MIN and Max value of the range.
// Doesn't improve really,  still need N(O2).

List<Integer> storage = new ArrayList<Integer>(2);

        for (int start = exit[0]; start <= physicalLimit; start ++ ) {
            boolean valid = true;
            int temp = start;
            for (int i = 0; i < exit.length; i++) {
                temp -= exit[i];
                if (temp < 0) {
                    valid = false;
                    break;
                }
                temp += enter[i];
                if (temp > physicalLimit) {
                    valid = false;
                    break;
                }
            }

            if (valid) {
                if (storage.size() == 0) {
                    storage.add(start);
                } else if (storage.size() == 1) {
                    storage.add(1, start);
                } else {
                    storage.set(1, start);
                }
            }
               
        }