Today’s Topcoder Single Round Match was Star Wars themed. Here are two problems that Obi-Wan featured in.
The first problem was that Obi-Wan is in a building guarded by droids and wishes to choose the safest exit. All the doors are along the same wall, and you are given the coordinates of the doors (distances from the corner) and of the droids along the wall outside (these coordinates are also distances from the corner). The safety of an exit is the distance between the door and the nearest droid.
This is the solution I came up with:
import java.util.Arrays;
public class ThePhantomMenace {
public int find(int[] doors, int[] droids) {
Arrays.sort(doors);
Arrays.sort(droids);
int maxSafety = 0;
for (int door : doors) {
int safety = 0;
for (int i = 0; i < droids.length; i++) {
if (droids[i] >= door) {
if (i == 0) safety = droids[i] — door;
else safety = Math.min(droids[i] — door, door — droids[i-1]);
if (safety > maxSafety) maxSafety = safety;
break;
}
}
}
return maxSafety;
}
}
This fails (as I found out the hard way) if there is only one door, at coordinate 100, and one droid, at coordinate 0. Basically, what do you do if there is no droid to the right of the door?
The second problem was that Obi-Wan is on a mission and is carrying N shirts. After he wears a shirt, it takes N-2 days to wash and dry it before he can wear it again.
If you’re given the order in which he wore his shirts on the first week of the mission (the week here has N days) and the order on the last week, can you figure out how short (in weeks) the mission could have been?
My solution was:
public class AttackOfTheClones {
public int count(int[] firstWeek, int[] lastWeek) {
int totalTime = 0;
for (int x = 0; x < firstWeek.length; x++) {
for (int y = 0; y < lastWeek.length; y++) {
if (firstWeek[x] == lastWeek[y]) {
int time = 0;
if (x > y) {
time = x — y + 1;
} else if (x < y) {
time = 1;
} else {
time = 0;
}
if (time > totalTime) totalTime = time;
break;
}
}
}
if (totalTime == 0) return 1;
else return totalTime;
}
}
Why does this work? It basically takes a week to move a shirt from day X to day X-1, or x-y weeks to move a shirt from day x to day y (if y is smaller than x). You have to count the first week too, so the mission would have taken x-y+1 weeks.
It will take one week to move a shirt from day X to a later day in the week (say X+n). The question that remains is — why don’t these weeks add up?
Let me know your thoughts!