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. The ProblemsHighscoreUsed as: Division Two  Level One:
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.length1){ 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 == numPlaces1 && scores[numPlaces1] == score) return 1;Cafeteria Used as: Division Two  Level Two: Used as: Division One  Level One:
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 =(timeoffset[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:
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 twodimensional 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:
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 (DC)/0.1 = 10*(DC) < 1,000,000 when DC < 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:
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 = 1winningProbability(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; 
