Wednesday, September 3, 2014

CatsOnTheLineDiv2

Problem:

TopCoder Problem Statement - CatsOnTheLineDiv2

Overview:

Try to spread a bunch of cats out along a line in the given amount of time such that no two cats occupy the same position.

Java Source:
001: import java.util.ArrayList;
002: import java.util.Collections;
003: import java.util.List;
004: 
005: public class CatsOnTheLineDiv2 {
006: 
007:     public static String PASS = "Possible";
008:     public static String FAIL = "Impossible";
009: 
010:     /*
011:     * This class ties together a position with the number of cats at that
012:     * position.  It also implements Comparable so we can sort them.  After
013:     * sorting, we can go through the positions from left to right.
014:     */
015:     class Position implements Comparable {
016:         int position;
017:         int numCats;
018: 
019:         Position(int position, int numCats) {
020:             this.position = position;
021:             this.numCats = numCats;
022:         }
023: 
024:         // Compare based on position.  There should be no duplicates.
025:         @Override
026:         public int compareTo(Position o) {
027:             if (this.position < o.position) return -1;
028:             if (this.position > o.position) return 1;
029:             return 0;
030:         }
031:     }
032: 
033:     public String getAnswer(int[] position, int[] count, int time) {
034: 
035:         List initialLine = new ArrayList<>();
036: 
037:         int numCats = 0;
038: 
039:         /*
040:         * For each element of the position and count arrays, create a new
041:         * Position object and adds it to initialLine.  Also counts the
042:         * total number of cats.
043:         */
044:         for (int i = 0; i < position.length; i++) {
045:             initialLine.add(new Position(position[i], count[i]));
046:             numCats += count[i];
047:         }
048: 
049:         Collections.sort(initialLine);
050: 
051:         // Calculate the size of the line after allowing that cats to move.
052:         int minPos = initialLine.get(0).position - time;
053:         int maxPos = initialLine.get(initialLine.size() - 1).position + time;
054:         int numPositions = maxPos - minPos + 1;
055: 
056:         // See if there are more cats than positions.  Maybe we can quit early.
057:         if (numCats > numPositions) return FAIL;
058: 
059:         /*
060:         * Holds the positions that have a cat after they've moved.  Note that
061:         * the array cannont have negative indexes, so we'll need to shift
062:         * the position over by minPos in order to map it.
063:         * Also, when done, each position can only have 1 cat (or zero), so we
064:         * can use an array of booleans instead of ints.
065:         */
066:         boolean[] newLine = new boolean[numPositions];
067: 
068:         /*
069:         * Loop through each Position (working left to right, since they were
070:         * sorted).  At each Position, loop through the number of cats.  For
071:         * each cat, try to find a final position for them.  If a position
072:         * cannot be found, then return FAIL.
073:         */
074:         for (Position p : initialLine) {
075:             for (int i = 0; i < p.numCats; i++) {
076: 
077:                 /*
078:                 * Note (p.position - minPos).  This shifts all the values over
079:                 * so they are zero-based.
080:                 */
081:                 if (!findPositionForCat(newLine, p.position - minPos, time))
082:                     return FAIL;
083:             }
084:         }
085: 
086:         // If we've found positions for all the cats, return PASS.
087:         return PASS;
088:     }
089: 
090:     /*
091:     * Attempts to find a position to place the cat.  Returns true if a position
092:     * can be found; otherwise false.
093:     * We'll move the cat to the furthest position left as possible given the
094:     * amount of time.  If that position is full (true), then keep looking to
095:     * the right.
096:     */
097:     private static boolean findPositionForCat(boolean[] line, int p, int time) {
098: 
099:         for (int i = (p - time); i <= (p + time); i++) {
100:             if (!line[i]) {
101:                 line[i] = true;  // Mark the position is occupied.
102:                 return true;
103:             }
104:         }
105: 
106:         return false;
107:     }
108: 
109: }
Notes:

The strategy is to work from left to right and move each cat as far to the left as they can in the given amount of time. If that position is already taken, then try the next position to the right. If any cat cannot find a suitable position, then we declare the problem to be impossible.

For example, lets say we have 2 cats (labeled A and B) at position zero, and three cats (labeled C, D and E) at position one. time = 2.

E
B D
A C
-2 -1 0 1 2 3

First, process the cats at position 0. Cat B can move two spaces to the left (time is 2, and position -2 is empty). Next we try to move cat A two spaces to the left, but that's already occupied (by B), so A goes in the first available space to the right.

E
D
B A C
-2 -1 0 1 2 3

Now we're done with position 0, and move on to position 1. Cat E cannot move into position -1 because it's occupied by cat A, so E moves to position 0. Cat D stays where it is, and cat C moves one position to the right.

B A E D C
-2 -1 0 1 2 3

It's important to note that the initial positions and final positions are kept in two separate arrays (initialLine and newLine). That's how cat D could stay put even though cat C had not been moved yet. The initial array is represented as a List of Position objects, where Position objects hold the location and number of cats at that location. The final position is represented by the boolean array newLine - either a cat has been placed there already or not. All indexes of newLine are initially set to false and become true when a cat is placed there.

On lines 52-55 we calculate the size needed for the newLine array. The cats can potentially move time positions to the left of the minimum starting position, or to the right of the maximum starting position. Be careful when mapping these positions between initialLine and newLine. We need to shift the values over so that the left most possible position aligns with the 0 index of newLine.

Since it's easy enough to count the number of cats at the start, and we now know the number of possible locations; I choose to add a check to see if the number of cats exceeds the number of locations. It's good to quit early and save a lot of computation if we can.

Note that we could have choosen to move all the cats to the right. The sort order on line 49, along with the directions on the for loop at line 99 would need to be reversed; but that's all.

As a final comment, I'll add that this seemed tougher than the typical Division 2 - Level 2 problem. If you don't see the algorithm, you're not likely to get done in time. I'd be interested to see if anyone solved this by working one time interval at a time. That is, something like:

  while (time > 0)  {
      moveCats();
      if (isSatisfied()) return "Possible";
      time--;
  }
  return "Impossible";

I spent too much time on that line of thinking before stepping back and trying another approach.

No comments:

Post a Comment