|
Match Editorial |
Monday, January 31, 2005
Match summary
SRM 229 was quite a bit easier than 228, and in division 1, ten coders
solved all three problems successfully. Top amongst them was
Jan_Kuipers, finishing in around 35 minutes. Next in line was haha,
who finished just a few minutes later. Rounding out the top 3 was
marian, over 100 points behind haha.
In division 2, things were a little harder, as a tricky easy problem
caused many coders to stumble, and the hard problem was hard enough
that only 6 coders even submitted it. entaroadun took top honors as
the only one to successfully submit all three problems. Helped by 200
points in the challenge phase, nidonido took second in his first
competition, with succcessful submission on the medium and hard
problems. Rounding out the top 3 was Philya, with solutions for the
easy and medium problems.
The Problems
Highscore
Used as: Division Two - Level One:
Value 250 Submission Rate 170 / 202 (84.16%) Success Rate 46 / 170 (27.06%) High Score entaroadun for 243.13 points (4 mins 48 secs) Average Score 177.73 (for 46 correct submissions)
This problem tripped a lot of people up, as evidenced by the low success rate. In fact, it set a new record for the lowest success rate every by a division 2 easy - beating out the previous record holder by over 14%! Of the failed solutions I looked at, most of them ended up calculating the ranks of all the scores in the table, and then trying to figure out the rank of the new score. Some of them inserted the new score into the table, and then sorted the table, finding the new ranks. Both of these approaches are way more complicated than is neccessary. Instead, notice that the rank of a score is exactly equal to the number of scores that beat it, plus 1. So, if no one beats you, then you are in first, or else tied for first. If 3 people beat you, you are in fourth, or tied for forth. Hence, the rank of the new score can be calculated with a simple for loop:
int place = 1;
for(i = 0 to scores.length-1){
if(newScore < scores[i]){
place ++;
}
}
Now, if the place is greater than the number of spaces return -1. Also, there
is the special case where the new score ties the bottom of the list, but the
list is already full. Both of these are pretty simple to check for:
if(place == numPlaces+1)
return -1;
if(scores.length == numPlaces-1 && scores[numPlaces-1] == score)
return -1;
Cafeteria
Used as: Division Two - Level Two:
Used as: Division One - Level One:
Value 500 Submission Rate 88 / 202 (43.56%) Success Rate 48 / 88 (54.55%) High Score {rustam} for 439.82 points (10 mins 48 secs) Average Score 297.05 (for 48 correct submissions)
Value 250 Submission Rate 202 / 217 (93.09%) Success Rate 171 / 202 (84.65%) High Score jshute for 242.61 points (4 mins 59 secs) Average Score 188.24 (for 171 correct submissions)
Coders had better luck with this problem and there are a couple of different ways to go about it. I think that the most straightforward and intuitive method is to work backwards from 2:30PM. First calculate the latest a bus could leave the bus stop and still arrive at 2:30PM. Then calculate the last time before or equal to that when the bus would actually leave, given its offset. Finally, calculate the time you would have to leave to get to the bus stop. Of all the bus stops, find the minimum time at which you would have to leave. If you represent all of your times as minutes past midnight (2:30PM = 14*60+30 = 870) it will make things relatively simple:
int time = 14*60+30;
time -= drivingtime[i];
time -=(time-offset[i])%10;
time -= walkingtime[i];
The only part that you have to think about a little is the one that deals with the offset, and there are
other ways to do it, though they require more typing (a loop, for
instance).At the end, you just had to convert the time into a string, being careful to get the leading zeros in the right place, and making sure you do all the hours correctly (the 12 in particular). SnowClearing
Used as: Division Two - Level Three:
Value 1000 Submission Rate 6 / 202 (2.97%) Success Rate 3 / 6 (50.00%) High Score nidonido for 507.92 points (36 mins 29 secs) Average Score 460.50 (for 3 correct submissions)
A dead end is any intersection that is only touched by a single street. There are also intersections that only lead to dead ends. We can define these recursively by saying that an intersection only leads to dead ends if following any of the outgoing edges except for one of them from that intersection either goes directly to a dead end, or else goes to an intersection that only leads to dead ends. There is one exception to this - the intersection associated with the garage may not be a dead end, nor an intersection that leads only to dead ends. This suggests something like the following algorithm:
for each dead end at (row,column)
set isDead(row,column) = true
do
look for an intersection at (row,column) != theGarage
such that for exactly one intersection (row',column')
connected to (row,column), isDead(row',column') == false
if (an intersection is found)
set isDead(row',column') = true
while(an intersection (row',column') is found)
Now, there are a lot of different ways to actually implement this approach. One
way, which I am fond of, is to create a large two-dimensional boolean array for
isDead, and then just loop over all intersections as long as the while condition
above is true. At the end, just count the number of locations for which isDead
is set to true. This approach runs rather slowly, but its fast enough for this
problem. Here is an approach that is much faster:
int[][] adjNonDeadCount = new int[rows][columns]
int[][] queue = new int[1000][2];
int head = 0, tail = 0;
for each intersection in the input at (row,column){
if((row,column) == theGarage){
adjNonDeadCount[row][column] = 0;
}else if((row,column) is a deadEnd){
adjNonDeadCount[row][column] = 1;
queue[tail][0] = row;
queue[tail][1] = column;
tail++;
}else{
adjNonDeadCount[row][column] = numberOfOutgoingEdgesFrom(row,column);
}
}
int[] dr = {0,1,0,-1};
int[] dc = {1,0,-1,0};
while(head < tail){
row = queue[head][0];
column = queue[head][1];
for(i = 0 to 3){
row' = row + dr[i];
column' = column + dc[i];
if((row',column') and (row,column) are connected &&
adjNonDeadCount[row'][column'] > 1){
adjNonDeadCount[row'][column'] --;
if(adjNonDeadCount[row'][column'] == 1){
queue[tail][0] = row';
queue[tail][1] = column';
tail++;
}
}
}
}
head++;
}
return tail;
The idea here is that we are keeping track of how many intersections
adjacent to each location have not been marked as dead or as only
leading to dead ends (both states are represented by a 1 in adjNonDeadCount).
Then, we look at each intersection that is marked as dead and reduce the
adjNonDeadCount of its neighbors. If any of them become dead, then we add that
location to the queue. The runtime of this algorithm is O(row*columns), as we
must look at every location once in the worst case.
BusinessPlan
Used as: Division One - Level Two:
Value 500 Submission Rate 176 / 217 (81.11%) Success Rate 92 / 176 (52.27%) High Score Jan_Kuipers for 483.67 points (5 mins 15 secs) Average Score 358.24 (for 92 correct submissions)
This problem requires a bit of dynamic programming, though it is on the easy side as far as dynamic programming problems go. The first important bit of information to glean from the problem statement is that the company can only work on one product at a time. So, all you need to do is maximize the total amount of money the company can have, at each time, assuming it has just finished a product. Let's say I have X dollars at time T. If I make product i, where expense[i] ≤ X, then I can have X+revenue[i]-expense[i] at time T+ptime[i]. Since I can't stop in the middle of making a product, and there is no reason to delay starting a new product once one is done, all I need to worry about is how much money I can have after just finishing a product. This leads to some elegantly short code:
int[] maxMoney = new int[10000000];
maxMoney[0] = C;
for(int i = 0;i<maxMoney.length ; i++){
if(maxMoney[i] >= D)return i;
for(int j = 0; j<expense.length; j++){
if(maxMoney[i] >= expense[j])
maxMoney[i+ptime[j]] = max(maxMoney[i+ptime[j]],
maxMoney[i]+revenue[j]-expense[j]);
}
}
return -1;
1,000,000 is always enough time, if it's possible, since no ptime is more than 10,
and if it is possible, you must profit at least 1. Hence, if you are making a
profit, you are doing so at a rate of at least 0.1 per time unit, and (D-C)/0.1 =
10*(D-C) < 1,000,000 when D-C < 100,000.An alternative approach is to do dynamic programming to compute the earliest time at which a particular amount of money could be achieved. I think it's a little bit harder to do it this way, but some people have an easier time with it, and it does run faster in this case.
if (C>=D)
return 0;
int [] bestTime = new int[D+1];
for (int i=0; i<bestTime.length; i++){
bestTime[i] = INF;
}
bestTime[C] = 0;
for (int i=C; i<D; i++) {
for (int j=0; j<ptime.length; j++){
if (expense[j]>i)
continue;
int money = min(D,i+revenue[j]-expense[j]);
if (bestTime[money]>bestTime[i]+ptime[j])
bestTime[money] = bestTime[i]+ptime[j];
}
}
if(bestTime[D] == INF)return -1;
return bestTime[D];
Hangman42
Used as: Division One - Level Three:
Value 1000 Submission Rate 25 / 217 (11.52%) Success Rate 11 / 25 (44.00%) High Score Jan_Kuipers for 682.83 points (21 mins 35 secs) Average Score 538.46 (for 11 correct submissions)
This is a classic sort of game theory problem. The basic approach used by most people is always the same: recursion + memoization. You have some game state, and you want to know, what should the player whose turn it is do in that game state. As intuition suggests, he should consider all of his options, and imagine what his opponent would do in each situation. When imagining what his opponent would do, he is applying recursion, because his opponent will have to do essentially the same thing, although with a different game state. So, in pseudocode, we have something like:
//returns the probability of winning from G
double winningProbability(gameState G){
if(G is a 'game over' state){
if(player whose turn it is won)
return 1;
else
return 0;
}
ret = 0
foreach(move M from gameState G){
tmp = 0, cnt = 0;
foreach(hidden word W consistent with previous moves){
gameState G' = G after move M where W is the hidden word
double d;
if(currentPlayer goes again)
d = winningProbability(G');
else
d = 1-winningProbability(G');
tmp += d;
cnt ++;
}
ret = max(ret,tmp/cnt);
}
return ret;
}
So, when considering a move, M, there is some set of potential hidden words that
are consistent with the previous moves. In practice, this set can be easily
implemented as a bitmask, and is all that is needed to know the game state. The
moves in the game are guessing a letter and guessing a word. So, what the
algorithm is doing is checking to see, if the current player makes a guess, M,
and the hidden word is really W, what is the probability that the current player
will win. Of course, this is one minus the probability that the other player
will win. After considering each possible hidden word, the overall probability
is computed for the move as a simple average of the probabilities for each
word.To avoid repeating the same calculations over and over again, and timing out, you should add the standard memoization code to the beginning and end of your code:
if(dp[G] exists)return dp[G];
...
dp[G] = ret;
return ret;
