JOIN
Get Time
statistics_w  Match Editorial
Archive
Printable view
 Discuss this match
SRM 248
Tuesday, June 21, 2005

Match summary

Turnout was high for SRM 248, as for the first time in a couple of years, there was money up for grabs in a TopCoder SRM! This match broke the previous record of most reds in an SRM. Tonight's final count, 44, exceeded the previous record of 32 from SRM 227. In the coding phase, SnapDragon came out of quasi-retirement and led a large group of Division 1 coders who solved all 3 problems. However, the challenge phase provided lots of activity with tomek picking up 5 successful challenges to pull ahead and win Division 1. Rounding out the top 5 were SnapDragon, krijgertje, antimatter and Yarin. In Division 2, first-timer yuhch123 took first place honours followed by nikola_borisof1, relic, first-timer hou and sorinelm.

The Problems

SyllableCounter discuss it
Used as: Division Two - Level One:
Value 250
Submission Rate 293 / 311 (94.21%)
Success Rate 254 / 293 (86.69%)
High Score gachobg for 248.27 points (2 mins 22 secs)
Average Score 218.62 (for 254 correct submissions)

To determine the number of syllables in a word, we have to identify groups of vowels. This is easy to do with a single loop over the letters in the word. If you encounter a vowel, increment the count of syllables, and skip to the first letter after this group that's not a vowel. In pseudocode: 

for i:1 to length word 
  if word[i] is a vowel 
     increment numSyllables 
     while word[i] is a vowel && i ≤ length word i++

It is possible to solve this problem in one line of Java code. I'll leave someone to start a "Shortest SRM 248 Div 2 250" thread to deal with this issue.

WordPattern discuss it
Used as: Division Two - Level Two:
Value 500
Submission Rate 147 / 311 (47.27%)
Success Rate 75 / 147 (51.02%)
High Score ctynan for 492.14 points (3 mins 36 secs)
Average Score 294.09 (for 75 correct submissions)
Used as: Division One - Level One:
Value 250
Submission Rate 281 / 311 (90.35%)
Success Rate 201 / 281 (71.53%)
High Score Petr for 244.26 points (4 mins 22 secs)
Average Score 178.23 (for 201 correct submissions)

This problem provided the greatest challenge material, as a number of coders forgot to handle the case when the input was only 1 character long in their closed-form solutions. For those coders who chose to solve the problem using simple memoization or a BFS, this turned out to not be an issue.

As mentioned in the problem statement, the procedure to create the actual pattern was part of the problem. This isn't very difficult. The pattern is constructed as follows:

write the word and it's reverse, overlapping the first character
word = word[2..length word]            // i.e. remove first character
for iter:1 to length word - 1
  write down word and it's reverse, overlapping the first character
  as the first and last row in the pattern
  word = word[2..length word]        // i.e. remove first character

Then, the number of ways to spell out the original word can be found by doing a very simple Breadth First Search (BFS). Starting at the center of the pattern, work outwards toward the fringe. At each location, the number of ways of getting to that location is simply equal to the sum of the number of ways of getting to the one or two locations that could be predecessors. For instance, in the upper right quadrant, the number of ways of getting to a location is equal to the sum of the number of ways of getting to the location to its left and the number of ways of getting to the location below it. Finally, the return value is simply the number of ways of reaching all the fringe squares.

Many people discovered the closed-form solution to this problem. This is given by: 

        if word.length < 2 return 1 else return (1 << (length word + 1)) - 4;

The proof is left as an exercise for the reader. :-)

BitStrings discuss it
Used as: Division Two - Level Three:
Value 1000
Submission Rate 117 / 311 (37.62%)
Success Rate 55 / 117 (47.01%)
High Score palmcron for 902.55 points (9 mins 32 secs)
Average Score 625.86 (for 55 correct submissions)

It may appear that this problem can be solved in a greedy manner. Two simple approaches come to mind. First, always attempt to form the shortest strings possible before attempting larger strings. However, this approach is flawed. Consider the case where 2 0s and 5 1s are available, and we have to make strings from the set {00, 011, 0111}. Then, if we were to greedily form the first string "00", we wouldn't have enough 0s to form any other strings, and our solution would return 1. Clearly, we can do better, by forming the second and third strings.

Another greedy approach is to always attempt to form strings that consume the least number of the digit which are in shortest supply. That is to say, if you have less 0s than 1s, you would attempt to construct strings that use a minimum number of 0s and in case of ties, break by the number of 1s. This approach is also flawed. Consider the case where you have 5 0s and 4 1 at your disposal, and the string list is {100000, 110, 110}. Noting that you have fewer 1s than 0s, you would construct the string "100000", since this consumes the least number of 1s. But now, you have no 0s left to construct the other strings.

The task can be solved with Dynamic Programming. First, we process the set of strings given to us and for each string, we store the number of 0s and 1s that appear in that string. In pseudo code,

for i:1 to number of strings
  for j:1 to length string[i]
      if character j in string i = 0 C0s[i]++;
      if character j in string i = 1 C1s[i]++;

Then, consider an array A, with dimensions [MAX_ZEROES][MAX_ONES]. The i,j entry of A represents the number of bitstrings that can be formed using i 0s and j 1s. So our algorithm is as follows (Note that we need to use an auxilliary array, B):

Initialze A to all 0
for i:1 to number of strings
  Initialize B to all 0
  string s = strings[i]

  // Consider s alone
  if C0s[i] ≤ numZeroes and C1s[i] ≤ numOnes B[C0s[i]][C1s[i]] = 1

  // Now, try making string s from everywhere we have previously reached
  for n0:0 to numZeroes
      for n1:0 to numOnes
          if A[n0][n1] > 0    // We can get here
             if n0 + C0s[i] ≤ numZeroes and // We have enough 0s
                n1 + C1s[i] ≤ numOnes and   // We have enough 1s
                A[n0][n1] + 1 > A[n0 + C0s[i]][n1 + C1s[i]]
                    Update [n0 + C0s[i]][n1 + C1s[i]] in B
               
  Copy B into A

The idea is to attempt to form new strings from positions that we can already reach from previous strings. So, if we can make X strings using i 0s and j 1s, and we're considering a string with u 0s and v 1s, it is obvious that we will reach the cell i + u, j + v in the array. Then, we only update the cell at that position if making this string actually improves the answer we already have stored there. The runtime of the above algorithm is on the order of MAX_STRINGS*MAX_ZEROES*MAX_ONES.

Note that with the constraint of 20 strings, this problem could actually be solved using simple bruteforce, by using bitmasks and iterating from 0 to 2^(# of bitstrings), which is the approach taken by most coders who solved this problem.

ContractWork discuss it
Used as: Division One - Level Two:
Value 500
Submission Rate 230 / 311 (73.95%)
Success Rate 172 / 230 (74.78%)
High Score SnapDragon for 490.21 points (4 mins 1 secs)
Average Score 360.84 (for 172 correct submissions)

Once again, it may appear that a greedy approach could work, but this is incorrect. Consider a simple example of only 3 tasks and 2 companies, with the following cost table: {"1 1 1", "10 10 100"}. If one attempts to perform each task greedily, i.e. choosing the cheapest company for each task, then tasks 1 and 2 would be assigned to company 1, since it has a cost of 1 for each of those tasks, which is less than what company 2 will charge. But now, we are FORCED to contract task 3 to company 2, since company 1 has already performed 2 consecutive tasks. Thus, we incur a cost of 100, bringing our total cost to 102. It is obvious that the correct minimum cost here is 12 (company 2 must be given either task 1 or 2, and the remaining tasks are performed by company 1).

To solve this problem, we can use memoization. Create an array cache[NUM_TASKS][NUM_COMPANIES][NUM_COMPANIES] and used the following function: 

int getAnswer(int curTask, int beforePrev, int prev)

  if curTask == NUM_TASKS return 0
  if cache[curTask][beforePrev][prev] > -1
     return cache[curTask][beforePrev][prev]  // Obviously, check range

  int best = INF
  for i:0 to NUM_COMPANIES
      if beforePrev == prev && prev == i continue; // 3 in a row
         best = min(best, cost[i][curTask] + getAnswer(curTask + 1, prev, i)

  cache[curTask][beforePrev][prev] = best

The idea here is as follows: If you can discover a function to return the optimal cost of performing the current task, then it is easy to use the same function to determine the total cost. So we just try all the possibilities for performing the current task and recursively calculate the optimal answer for the remaining subproblem. Naturally, we use memoization to speed-up the process. This problem can also be solved using a DP approach, using straight iteration rather than a recursive formulation.

ClockManagement discuss it
Used as: Division One - Level Three:
Value 1000
Submission Rate 73 / 311 (23.47%)
Success Rate 45 / 73 (61.64%)
High Score antimatter for 768.10 points (16 mins 42 secs)
Average Score 549.94 (for 45 correct submissions)

By lbackstrom
On the night of an exciting game 6 in the NBA finals, this problem asked us to help two basketball teams manage the clock. Luckily, the game was grossly simplified with the removal of fouls, timeouts and three point shots. This left only 2 point baskets, and a rather standard mini-max type of problem. Like most problems in this class, it is best solved with recursion, where the recursive function determines what to do for a particular game state. In this case, the game state consisted of who has the ball, the score differential, and the amount of time left. Note that the absolute scores don't have any impact -- only the difference matters.

From a particular game state, a team has a number of different options of what to do, corresponding to the numbers of seconds the team can take to set up. When it is team A's turn to decide, it should do so to maximize the probability of winning down the road. When it is team B's turn to decide, it should do so to maximize its probability of winning or tying down the road. Here is the basic idea, where a team makes its decision of what to do by looking at each option and picking the best: 

double recurse(timeLeft, diff, curTeam){
  double ret = 0
  foreach(number of seconds to set up i){
      d = probability of curTeam winning (or tieing in the case of 
          team B) if curTeam shoots after i seconds
      ret = max(ret,d)
  }
  return ret
}
As you can see, when it is A's turn to make a decision, A maximizes the return. When it is B's turn to make a decision, B minimizes the return. However, this is only the beginning of a solution. To make it work, we have to figure out how to determine d, add the base case, and then make it run fast. Calculating d above requires 3 recursive calls, based on the three possible outcomes of a shot: scoring, missing and getting a rebound, missing and losing possession. If we let a value of 0 represent team A, and 1 represent team B, and put the probabilities in 2-D arrays p and r (for percentage and rebound), then we can calculate d as follows: 
 //in order, the calls correspond to scoring, missing, and missing and rebounding
 d = (1-recurse(timeLeft-i,diff+(curTeam==A?2:-2),1-curTeam)) * p[curTeam][i-2]
 + (1-recurse(timeLeft-i,diff,1-curTeam)) * (1-p[curTeam][i-2]) * (1-r[curTeam][i-2])
 + recurse(timeLeft-i,diff,curTeam) * (1-p[curTeam][i-2]) * r[curTeam][i-2]
Notice that the recursive function returns the probability of curTeam coming out on top. As a result, when the ball changes possession, you must subtract the probability from the recursive call from 1. For instance, the first recursive call above correlates to curTeam scoring, and the recursive call returns the probability that the other team will win (or tie for B). To convert this to the probability that curTeam will win, simply subtract it from 1.

Next we have to add our base case. This is simply a matter of returning 1 when the game has 0 or 1 seconds left and curTeam is going to win, and 0 if curTeam is going to lose: 
if(timeLeft <=1){
  if(diff > 0 && curTeam == A || 
     diff ≤ 0 && curTeam == B)return 1;
  else return 0;
}
Finally, to make the solution run fast enough, we need to use memoization to cache the results. This amounts to saving the result of a recursive call for a particular (timeLeft,diff,curTeam) triple after it has been computed. Then, if the recursive function is ever called again with the same arguments, the results can be looked up in the table.

antimatter's solution follows the approach outlined here quite closely.

Author
By NeverMore
TopCoder Member