|
Match Editorials |
Monday, February 5, 2007
Match summary
As HS SRM 31 kicked off, 243 young competitors fought their way through traffic in order to complete this problem set. An exciting battle ensued, as the coders fought for victory in the penultimate SRM of the first season.As most competitors opened the 250 point problem, scoring was abundant early. Several quick solutions to this problem, including those by Zuza, exod40, and fatit, led to a high scoring affair. Weiqi was the first to submit on the tricky 500, followed shortly thereafter by MB__ , ahyangyi, parabola811, and TICKET_112022 almost simultaneously. As submissions to the 500 started to trickle in, fatit leapt into the lead at the 19 minute mark by going directly to the 1000 problem and submitting it. His lead was not to last long, as within minutes, Weiqi submitted his 1000 point problem for 912.02 points. By the end of the coding phase, Weiqi had a 52 point lead over ahyangyi, with g201513, Zuza, and TICKET_112022 trailing close behind.
The challenge phase continued the excitement, as many of the hard solutions fell to challenges. Weiqi cemented the lead with 175 points during the challenge phase, with Zuza and TICKET_112022 vaulting into second and third, respectively. However, their time at the top was short lived, as their hard solutions failed system tests. Weiqi emerged as the victor, with g201513 in second and ahyangyi in third.
The Problems
TrafficReport
Used as: Division One - Level One:
This is a straight forward problem that can be solved by iteration, and stresses the importance of having a string parser in your code library; if your language doesn't have a built-in parser, it might be a good idea to write one of your own and keep it handy. First, we parse all of the elements of route. We split each element into its two parts: the time and the street name. We sum all of the times, and keep the street names in a table. Next, we parse all of the elements of report. For each element, we first check to see if the street is located in the route. If it is, we add this to the total travel time. Once we have done this, we return this sum. Java code follows:
Value 250 Submission Rate 204 / 225 (90.67%) Success Rate 189 / 204 (92.65%) High Score Zuza for 248.45 points (2 mins 14 secs) Average Score 210.41 (for 189 correct submissions)
public class TrafficReport
{
public int bestRoute(String[] route, String[] report)
{
int ret = 0;
String[] rstreet = new String[60];
for(int i=0; i < route.length; i++)
{
String[] temp = route[i].split(" ");
ret += Integer.parseInt(temp[0]);
rstreet[i] = temp[1];
}
for(int i=0; i < report.length; i++)
{
String[] temp = report[i].split(" ");
int j;
for(j=0; j < rstreet.length; j++)
if(temp[1].equals(rstreet[j])) break;
if(j < rstreet.length) ret += Integer.parseInt(temp[0]);
}
return ret;
}
};
HighwayJam
Used as: Division One - Level Two:
Inspired by the daily commute to work, this problem turned out to be tricky. The first thing to realize about the problem is that you should only switch to a lane with a higher index if you are moving to a lane with a higher speed. To prove this, assume that the fastest route involves traveling in lane j (with speed lanes[j]), but where lanes[i] > lanes[j]. However, this means that dist/lanes[i] < dist/lanes[j], which contradicts the initial assumption. Thus, we only want to shift away from the exit lane if we will be traveling faster. Similarly, we want to spend as much time in this faster lane as is possible, to maximize our average velocity. Therefore, we can greedily try each lane, shifting to that lane as early as possible, and shifting back to the exit as late as possible. For each lane, the total time will equal the sum of the time taken to get into the lane (for lane i, this will be laneChange*(i-1)), the time taken to get back to exit 0 (also laneChange*(i-1)), and the time spent in the lane. We can set distance_in_lane = dist-sumof(2*laneChange*lanes[j]). Thus, the time = distance_in_lane / lanes[i]. We just need to watch out for the corner case in which this time is less than laneChange, at which point we cannot enter that lane (since we cannot safely return to lane 0 in time). Java code follows:
Value 500 Submission Rate 124 / 225 (55.11%) Success Rate 83 / 124 (66.94%) High Score Weiqi for 466.49 points (7 mins 43 secs) Average Score 321.13 (for 83 correct submissions)
public class HighwayJam
{
public double minTime(int[] lanes, int laneChange, int dist)
{
double ret = 1.0*dist/lanes[0];
double dleft = dist;
double ctime = 0;
for(int i=1; i<lanes.length; i++)
{
dleft -= 2*laneChange*lanes[i-1];
ctime += 2*laneChange;
if(dleft < laneChange*lanes[i]) break; // if no time to switch back, we're done
ret = Math.min(ret, ctime + dleft/lanes[i]);
}
return ret;
}
}
LicensePlate
Used as: Division One - Level Three:
One of the important things to check when evaluating algorithms is the size of the input. In this problem, n can range from 0 to 2,147,483,647, which is too large a number to attempt to generate license plates one by one. As a result, we need a faster way to parse the plates. As a simple example, consider a case where format="nu" and n = 123. If we enumerate all possible plates, we see that the value of the last character is based on the remainder modulo 26; plate 0 is "0A", plate 26 is "1A", plate 52 is "2A", etc. In this case, since n%26 = 19, we can replace the 'u' with 'T'. Now, to determine how many times we change the remaining characters, we divide n by 26 (so n=4). We can then repeat this process on the new plate "nT", with n=4. This demonstrates how to extend this to larger formats. We determine the last character, using modulo 10, 26, or 36 if the character in format was 'n', 'u', or 'a' respectively, and then calculating the new value of n by dividing by the same number. If n is 0 after we have assigned all lowercase letters in the format, then this plate fits in the format and we return it. If n is greater than 0, then there are not enough plates in this format, and we return "". Java code follows:
Value 1000 Submission Rate 85 / 225 (37.78%) Success Rate 29 / 85 (34.12%) High Score Weiqi for 912.02 points (9 mins 0 secs) Average Score 665.66 (for 29 correct submissions)
public class LicensePlate
{
public String getPlate(String format, int n)
{
String ret="";
for(int i=format.length()-1; i>=0; i--)
{
switch(format.charAt(i))
{
case 'a':
if(n%36 < 10) ret = (char)('0'+n%36) + ret;
else ret = (char)('A'+(n-10)%36) + ret;
n /= 36;
break;
case 'n':
ret = (char)('0'+n%10) + ret;
n /= 10;
break;
case 'u':
ret = (char)('A'+n%26) + ret;
n /= 26;
break;
default:
ret = format.charAt(i) + ret;
}
}
return n > 0 ? "" : ret;
}
}
Working left-to-right is also possible, but you need to make sure to use 64-bit integers to avoid running into overflow problems. See Weiqi's or fatit's code for an example of this method.
