Topcoder BridgeCrossing – SRM 146 Div 2

https://www.topcoder.com/community/competitive-programming/tutorials/how-to-find-a-solution/

A group of people is crossing an old bridge. The bridge cannot hold more than two people at once. It is dark, so they can’t walk without a flashlight, and they only have one flashlight! Furthermore, the time needed to cross the bridge varies among the people in the group. When people walk together, they always walk at the speed of the slowest person. It is impossible to toss the flashlight across the bridge, so one person always has to go back with the flashlight to the others. What is the minimum amount of time needed to get all the people across the bridge?

There are at most 6 people.

Problem hints:

• First look at the constraints – there are at most ONLY 6 people! It’s enough for generating all possible permutations, sets etc.
• There are different possible ways to pass the people from one side to another and you need to find the best one.

This is of course a problem solved with a backtracking: at the beginning choose any 2 people to pass the bridge first, and after that at each step try to pass any of those that have been left on the start side. From all these passages select the one that needs the smallest amount of time. Note that among persons that have passed over the bridge, the one having the greatest speed should return (it’s better than returning one having a lower speed). This fact makes the code much easier to implement. After having realized these things – just code the solution. There may be others – but you will lose more time to find another than to code this one.

https://github.com/irpap/TopCoder/blob/master/BridgeCrossing/src/BridgeCrossing.java
    public int minTime(int[] times) {
        LinkedList<Integer> sideA = new LinkedList<Integer>();
        for (int t : times) sideA.add(t);
        return movePeople(sideA, new LinkedList<Integer>(), true);
    }

    /**
     * returns the min time to move the people from sideA to sideB
     */
    int movePeople(List<Integer> sideA, List<Integer> sideB, boolean torchIsAtSideA) {
        int minTime = Integer.MAX_VALUE;

        if (torchIsAtSideA) {
            if (sideA.isEmpty()) return 0;
            if (sideA.size() == 1) return sideA.get(0);

            for (int i = 0; i < sideA.size(); i++) {
                for (int j = i + 1; j < sideA.size(); j++) {
                    Integer person1 = sideA.get(i);
                    Integer person2 = sideA.get(j);

                    move(person1, sideA, sideB);
                    move(person2, sideA, sideB);

                    minTime = min(minTime, max(person1, person2) + movePeople(sideA, sideB, !torchIsAtSideA));

                    move(person1, sideB, sideA);
                    move(person2, sideB, sideA);
                }
            }
        } else {
            if (sideB.isEmpty() || sideA.isEmpty()) return 0;
            for (int i = 0; i < sideB.size(); i++) {
                Integer personToMove = sideB.get(i);

                move(personToMove, sideB, sideA);

                minTime = min(minTime, personToMove + movePeople(sideA, sideB, !torchIsAtSideA));

                move(personToMove, sideA, sideB);
            }
        }
        return minTime;
    }

    private void move(Integer person, List<Integer> from, List<Integer> to) {
        from.remove(person);
        to.add(person);
    }

X.

https://github.com/charles-wangkai/topcoder/blob/master/BridgeCrossing.java

https://github.com/kmather73/TopCoder/blob/master/SRM-146-DIV-2/BridgeCrossing.cpp

public int minTime(int[] times) {

if (times.length==1) {

return times[0];

}

Arrays.sort(times);

int total=0;

int rest=times.length;

while (rest>3) {

total+=Math.min(times[0]*2+times[rest-2]+times[rest-1], times[0]+times[1]*2+times[rest-1]);

rest-=2;

}

if (rest==3) {

return total+times[0]+times[1]+times[2];

}

else if (rest==2) {

return total+times[1];

}

return -1;

}

https://sites.google.com/site/topcodingsolutions/srm/div2/146/1000

In order to minimize the time it takes for everyone to cross, we'll want to use the following strategy:

• Group the slowest people together. If the slowest two people take 5 and 10 minutes respectively, then the trip will take 10 minutes, but there is no faster way to get the slowest person across. By sending the second slowest with the slowest, the second slowest person gets across "for free".
• Utilize the fastest person in situations where we're just bringing the flashlight back and forth.

The algorithm looks like this:

Repeat until side 1 is empty:

1. Send the two fastest people (person 1 and person 2) from side 1 to side 2.
2. Send the fastest (person 1) from side 2 back to side 1.
3. Send the two slowest people from side 1 to side 2.
4. Send the fastest person on side 2 (person 2) from side 2 back to side 1.

Once you have the algorithm, the main method is pretty straight forward. I created a method sendOver() to abstract the details of moving people from one side to another.

The sendOver() method takes as parameters the number of people to send (1 or 2), whether we want to send the fastest or slowest people (fastest = true|false), the source side, and the destination side.

Lines 41-45 and 53-58 are a little tricky. Basically, if we're sending the fastest people over, then I'll set currentMax to a high number, and then update it whenever I find something smaller. If I'm looking for slow people, then I set it to a low number, and update it whenever I find something larger. I could have picked a better name than currentMax, since often it will actually be a minimum.

Line 115 might also be confusing. We'll reach this line either once or twice depending on the value of numToSend. The first time, eTime will equal 0, so it will get set to currentMax, the time it took for the first person to cross the bridge. The second time, it will either keep it's value, or get set to the new person's time, depending on who is slower.

015:     /*
016:     Use two hash sets to hold the people that are on
017:     the starting side (side1) and the finish (side2)
018:      */
019:     private final Set side1 = new HashSet();
020: 
021:     private final Set side2 = new HashSet();
022: 
023:     /*
024:     Move people from the "fromSide" set to the "toSide" set.
025:     numToSend - indicates the number of people moving across together.  It
026:     must be either 1 or 2.
027:     fastest - indicates whether we want the fastest people (true), or the
028:     slowest (false) to go across.
029:     Returns the amount of time it will take to move the people across.
030:      */
031:     private static int sendOver(int numToSend, boolean fastest,
032:                                 Set fromSide, Set toSide) {
033: 
034:         int eTime = 0;
035:         int currentMax;
036: 
037:         // Loop either 1 or 2 times, depending on the number being asked to
038:         // send.
039:         for (int n = 0; n < numToSend; n++) {
040: 
041:             if (fastest) {
042:                 currentMax = Integer.MAX_VALUE;
043:             } else {
044:                 currentMax = 0;
045:             }
046: 
047:             /*
048:             If we're looking for the fastest person (fastest = true),
049:             then look for values that are below currentMax.
050:             If we're looking for the slowest person (fastest = false),
051:             then look for values that are above currentMax.
052:              */
053:             for (int i : fromSide) {
054:                 if ((fastest && (i < currentMax)) ||
055:                         (!fastest && (i > currentMax))) {
056:                     currentMax = i;
057:                 }
058:             }
059: 
060:             /*
061:             We've found either the fastest or slowest.  Remove them from the
062:             from side and add them to the to side.
063:             Set eTime to either eTime (if this is the first time through the
064:             loop) or the greater of eTime and currentMax if we've been
065:             through the loop before.  The effect is that eTime will contain the
066:             slower person's time.
067:              */
068:             fromSide.remove(currentMax);
069:             toSide.add(currentMax);
070:             eTime = Math.max(eTime, currentMax);
071:         }
072: 
073:         // Return the slower person's time.  (Just the time if numToSend = 1)
074:         return eTime;
075:     }
076: 
077:     public int minTime(int[] times) {
078: 
079:         int eTime = 0;  // Holds the elapsed time.  The return value.
080: 
081:         // Put all the people onto the starting side
082:         for (int i = 0; i < times.length; i++) {
083:             side1.add(times[i]);
084:         }
085: 
086:         /*
087:         Send the two fastest from side1 to side2.
088:         Check to make sure there are more than 1 people on side 1.
089:         If there is only one person on side1, then just send that one.
090:         */
091:         eTime += sendOver((side1.size() >= 2) ? 2 : 1, true, side1, side2);
092: 
093:         // When side1 no longer has any people, we're done.
094:         while (side1.size() != 0) {
095: 
096:             // Send the fastest person back from side2 to side1
097:             eTime += sendOver(1, true, side2, side1);
098: 
099:             /*
100:             Send the two slowest people from side1 to side2.
101:             There must be at least two people, since we weren't done,
102:             and above we've just sent one more back.
103:              */
104:             eTime += sendOver(2, false, side1, side2);
105: 
106:             // Check again to see if we're done.
107:             if (side1.size() == 0) {
108:                 return eTime;
109:             }
110: 
111:             // Send the fastest person back from side2 to side1
112:             eTime += sendOver(1, true, side2, side1);
113: 
114:             // Send the two fastest from side1 to side2.
115:             eTime += sendOver(2, true, side1, side2);
116:         }
117: 
118:         return eTime;
119:     }

https://tsenkov.net/2013/04/08/topcoder-srm-146-div2-problems-and-solutions

Bridge Crossing wasn't very hard to see through (luck maybe). The algorithm is consistent of the repetition of this complex action:

1. Get the fastest couple on the left side;
2. Return the fastest element back on the right side;
3. Get the slowest (with highest sum, also) couple on the left side;
4. Return the second element passed in step 1. back on the right.

​​This is repeated until all elements are on the left side.

For ease I am sorting the elements at the beginning and then always insert at sorted positions the elements I am moving.


    public int minTime(int[] times)

    {

        Array.Sort(times);

        if (times.Length == 1)

        {

            return times[0];

        }

        else if (times.Length == 2)

        {

            return Math.Max(times[0], times[1]);

        }

 

        List<int> right = new List<int>(times);

        List<int> left = new List<int>();

 

        int time = 0;

        bool moveLeft = true;

        // -1 0 1

        int probeStage = 1;

        while (right.Count > 0)

        {

            if (moveLeft)

            {

                int first, second;

                switch (probeStage)

                {

                    case 1:

                        first = right[0];

                        second = right[1];

                        left.Insert(0, first);

                        left.Insert(1, second);

                        right.RemoveRange(0, 2);

                        time += second;

                        probeStage = -1;

                        break;

                    case 0:

                        int lastIndex = right.Count - 1;

                        first = right[lastIndex - 1];

                        second = right[lastIndex];

                        left.Add(first);

                        left.Add(second);

                        right.RemoveRange(lastIndex - 1, 2);

                        time += second;

                        break;

                }

                moveLeft = false;

            }

            else

            {

                int firstLeft = left[0];

                int firstRight = right[0];

                left.RemoveAt(0);

                int index = 1;

                if (firstLeft < firstRight)

                {

                    index = 0;

                }

                right.Insert(index, firstLeft);

                probeStage++;

                moveLeft = true;

                time += firstLeft;

            }

        }

        return time;

    }