Home ›

Google Code Jam - Space Emergency

Nico Heid's picture
by Nico Heid on Mon, 07/18/2011 - 13:54
in

Space Emergency is a nice little puzzle from Google Code Jam 2011.

The solution is quite simple. Fly as long as the boosters are built. Once they are done, reorder your remaining distance. Use the boosters on longest distances. Voila - that's it.

Let’s see the straight forward implementation for the small input.

  1.  for (int casenr = 1; casenr <= testcases; casenr++) {
  2.  
  3.             Integer time = 0;
  4.             Integer boosters = scanner.nextInt();       // L
  5.             long buildTime = scanner.nextLong();      // t
  6.             Integer finalStar = scanner.nextInt();      // N
  7.             Integer stars = scanner.nextInt();          // C
  8.             List<Integer> distances = new ArrayList<Integer>();
  9.             for (int i = 0; i < stars; i++) {
  10.                 distances.add(scanner.nextInt() * 2);
  11.             }
  12.  
  13.             // lay out the track we'll travel
  14.             List<Integer> track = new ArrayList<Integer>();
  15.             for (int i = 0; i < finalStar; i++) {
  16.                 track.add(distances.get(i % distances.size()));
  17.             }
  18.  
  19.  
  20.             // let the ship fly till the boosters are ready
  21.             while (track.size()>0 && track.get(0) <= buildTime) {
  22.                 time += track.get(0);
  23.                 buildTime -= track.get(0);
  24.                 track.remove(0);
  25.  
  26.             }
  27.             // check if we're between two planets when the boosters are ready
  28.             if (track.size() > 0 && buildTime > 0) {
  29.                 time += (int) buildTime;
  30.                 track.set(0, track.get(0) - (int)buildTime);
  31.             }
  32.  
  33.             // reorder by distance use boosters on longest distance until we're out of boosters
  34.             Collections.sort(track);
  35.             Collections.reverse(track);
  36.  
  37.             while (track.size() > 0) {
  38.                 if (boosters > 0) {
  39.                     time += track.get(0) / 2;
  40.                     track.remove(0);
  41.                     boosters--;
  42.                 } else {
  43.                     time += track.get(0);
  44.                     track.remove(0);
  45.                 }
  46.  
  47.  
  48.             }
  49.  
  50.             System.out.printf("Case #%d: %s\n", casenr, time);
  51.             out.printf("Case #%d: %s\n", casenr, time);
  52.  
  53.         }
  54.  
  55.     }

Do you trust this to handle this code to handle the large input?

There’s one minor arithmetic error and one major performance problem in the given solution. Take a few seconds and try to spot them.

If you think you did, continue on page two to see the solution.