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.
for (int casenr = 1; casenr <= testcases; casenr++) {
Integer time = 0;
Integer boosters = scanner.nextInt(); // L
long buildTime = scanner.nextLong(); // t
Integer finalStar = scanner.nextInt(); // N
Integer stars = scanner.nextInt(); // C
List<Integer> distances = new ArrayList<Integer>();
for (int i = 0; i < stars; i++) {
distances.add(scanner.nextInt() * 2);
}
// lay out the track we'll travel
List<Integer> track = new ArrayList<Integer>();
for (int i = 0; i < finalStar; i++) {
track.add(distances.get(i % distances.size()));
}
// let the ship fly till the boosters are ready
while (track.size()>0 && track.get(0) <= buildTime) {
time += track.get(0);
buildTime -= track.get(0);
track.remove(0);
}
// check if we're between two planets when the boosters are ready
if (track.size() > 0 && buildTime > 0) {
time += (int) buildTime;
track.set(0, track.get(0) - (int)buildTime);
}
// reorder by distance use boosters on longest distance until we're out of boosters
Collections.sort(track);
Collections.reverse(track);
while (track.size() > 0) {
if (boosters > 0) {
time += track.get(0) / 2;
track.remove(0);
boosters--;
} else {
time += track.get(0);
track.remove(0);
}
}
System.out.printf("Case #%d: %s\n", casenr, time);
out.printf("Case #%d: %s\n", casenr, time);
}
}
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.
integer overflow
The problem you might have spotted is our resulting times being bigger than a regular int, so we’ll have an overflow and end up using negative time for the trip. As we’re not allowed to invent time travel here, this would be an incorrect solution.
performance issue
Did you see it? Permanently removing the first element of an ArrayList is surely not the smartest thing to do.
You’re asking why? Let’s see what the javadoc says to this operation:
Removes the element at the specified position in this list. Shifts any subsequent elements to the left (subtracts one from their indices).
So you’re using all your cpu to rearrange the ArrayList.
Instead of removing the elements, use an int as “pointer” and let it travel through the ArrayList. Alternatively an Iterator would do the same job.
for (int casenr = 1; casenr <= testcases; casenr++) {
long time = 0;
Integer position = 0;
Integer starsPassed = 0;
Integer boosters = scanner.nextInt(); // L
long buildTime = scanner.nextLong(); // t
Integer finalStar = scanner.nextInt(); // N
Integer stars = scanner.nextInt(); // C
List<Integer> distances = new ArrayList<Integer>();
for (int i = 0; i < stars; i++) {
distances.add(scanner.nextInt() * 2);
}
// lay out the track we'll travel
List<Integer> track = new ArrayList<Integer>();
for (int i = 0; i < finalStar; i++) {
track.add(distances.get(i % distances.size()));
}
// let the ship fly till the boosters are ready
// count the stars passed to remove them later
while (position < finalStar && track.get(position) <= buildTime) {
time += track.get(position);
buildTime -= track.get(position);
position++;
starsPassed++;
}
// check if we're between two planets when the boosters are ready
if (position < finalStar && buildTime > 0) {
time += (int) buildTime;
track.set(position, track.get(position) - (int) buildTime);
}
// get the remaining track, subtract the nr of stars we've already passed
// reset position to zero
track = track.subList(starsPassed, track.size());
finalStar -= starsPassed;
position = 0;
// reorder by distance use boosters on longest distance until we're out of boosters
Collections.sort(track);
Collections.reverse(track);
while (position < finalStar) {
if (boosters > 0) {
time += track.get(position) / 2;
position++;
boosters--;
} else {
time += track.get(position);
position++;
}
}
System.out.printf("Case #%d: %s\n", casenr, time);
out.printf("Case #%d: %s\n", casenr, time);
}
}
Nico Heid
Latest posts by Nico Heid (see all)
- Raspberry Pi Supply Switch, start and shut down your Pi like your PC - August 24, 2015
- Infinite House of Pancakes – code jam 2015 - July 13, 2015
- google code jam 2014 – magic trick - April 18, 2014