Match Editorial

Match summary

SRM 372 was the scene for fierce TopCoder programming action, as 1450 competitors showed up to do battle in the penultimate warmup to the TCCC '07 finals. gevak jumped out to an early lead with a fast submission of the 1000. As the coding phase ended, ACRush led, followed by gawry and Petr. gevak and OpenGL leapt back into the fray with 2 successful challenges each. In the end, ACRush squeaked out victory, just edging out gevak and OpenGL.

In division 2, tstan436 leapt into the early lead, but gave way to the dominating XiaoXiaoqing. With the fastest times on both the medium and hard problems, XiaoXiaoqing easily won the match. Following in second place was Werevovk with a very impressive debut, and algoboy took home third.

The Problems

Value	250
Submission Rate	662 / 731 (90.56%)
Success Rate	590 / 662 (89.12%)
High Score	tstan436 for 246.90 points (3 mins 11 secs)
Average Score	195.89 (for 590 correct submissions)

Due to the low constraints on input, this problem can easily be solved by brute force. You can simply loop over all possible types of food ('A'-'Z'), and check to see whether they are present in the diet, and in the food you have already eaten. If you've eaten it and it is not part of the diet, then you have cheated, and we return "CHEATER". If you have not eaten it and it is in the diet, then we add it to the return string. By looping in alphabetical order, we can then return the appropriate string. Java code for this would look like:

String eaten = breakfast + lunch;
String ret="";
for(char c='A'; c<='Z'; c++)
 if(diet.indexOf(c)==-1 &&  eaten.indexOf(c)!=-1)    // We ate it but not in diet
     return "CHEATER";
 else if(diet.indexOf(c)!=-1 && eaten.indexOf(c)==-1) // We didn't eat it yet
     ret += c;
return ret;

Homework

Let's make the problem a little harder and say that you may need to eat multiples of certain foods (for example, your diet may consist of 2 'A', 3 'B', and 1 'D'). Can you solve this problem in O(D+E) time, where D is the size of diet and E is the size of breakfast+lunch?

Value	500
Submission Rate	246 / 731 (33.65%)
Success Rate	136 / 246 (55.28%)
High Score	XiaoXiaoqing for 473.83 points (6 mins 45 secs)
Average Score	281.40 (for 136 correct submissions)

Value	250
Submission Rate	493 / 603 (81.76%)
Success Rate	423 / 493 (85.80%)
High Score	Petr for 241.70 points (5 mins 18 secs)
Average Score	173.74 (for 423 correct submissions)

This problem (inspired by the fact that drivers in certain US states apparently don't understand how to merge into one lane when entering a construction zone) can be solved simply through simulation. For each time step, we determine which car is allowed to exit; we can keep track of which cars have already yielded by keeping a boolean array called yield, in which yield[i] is true if the front car in lane i has already yielded to another car. The car that is due to exit during this timestep will be the car in the lowest numbered lane that has already yielded. If no cars have yielded, then the car in the highest lane that still has a car can exit. If that car is 'D', we can return the number of cars that have previously exited. The code to determine which lane can exit is O(N) (where N is the number of lanes), and in the worst case (where the car exits last) we have to go through all M cars, thus making the algorithm overal O(NM); for N=50 and M=2500, this is more than sufficient. Java code follows:

 int N = lanes.length;
 boolean yield[] = new boolean[N];
 int frontCar[] = new int[N];
 
 for(int ret = 0; true; ret++)
 {
  int i=0, last = 0;
  for(i=0; i < N ; i++)
   if(yield[i]) break;    // if the car has already yielded, we want it
   else if (frontCar[i] != lanes[i].length() )
   {
    yield[i] = true;    // the front car of this lane has now yielded
    last = i;            // and we keep track of the last car we see
   }			
			// if no lanes have yielded
  if(i==N) i = last;    // pick the highest numbered lane
  if(lanes[i].charAt(frontCar[i])=='D') return ret;
  frontCar[i]++;    // move the pointer to the next car
  yield[i] = false;    // the new car has not yet yielded
 }

Homework

1) Assume that you can find the location of the diplomat's car in constant time. Find a O(N) algorithm to determine the cars that exit before the diplomat.

2) Assume that there are still N lanes, but now there are an infinite number of cars in each lane. You know the lane that the diplomat is in, and the number of cars in front of him. Determine the number of cars that exit before the diplomat in O(1) time.

Value	1000
Submission Rate	47 / 731 (6.43%)
Success Rate	9 / 47 (19.15%)
High Score	XiaoXiaoqing for 710.11 points (19 mins 56 secs)
Average Score	532.87 (for 9 correct submissions)

Approach 1 - Dynamic Programming

This problem proves to be a good exercise in dynamic programming. In order for a dynamic programming solution to be attempted, we need to show that we can break down the big problem into subproblems, and then build up from there. Assume that we are at section n at time t. We can thus let dpTable[n][t] be the minimum number of times that we get wet to get home from there. This means that the value to return will be dpTable[y][0] (where y is the section in which you start). To prove that this will not exceed memory/time limits, we need to determine the maximum time that we will take to reach home while as dry as possible. Assume that the section in which you are standing is covered. Your next move that does not involve you standing still should move you one step closer to your home (proof: If you move away from home in some optimal route, you eventually will return to that section on your way home; if you choose to just stand still until that time instead, you will be just as dry). Furthermore, let N be the number of sections of path; there will be an optimal time to move toward home within N minutes of arriving in that section. Thus, there is an optimally dry route to the home that takes at most N² minutes. With N being at most 50, the dpTable will take up to 125,000 bytes of memory and thus easily will fit into memory.

int N;
int dpTable[][];
String p, f;

int getWet(int cur, int t)
{
 if(cur < 0 || cur >=N) return 1; // illegal input
 if(p.charAt(cur)!='.') return 0; // can't get wet
 if(f.charAt((cur+t)%N)=='R') return 1; // wet
 return 0; // dry
}

int dp(int cur, int t)
{
 if(t > N*N) return 10000;
 if(cur < 0 || cur >=N) return 10000;
 if(p.charAt(cur)=='H') return 0; // HOME!
 if(dpTable[cur][t] > -1) return dpTable[cur][t];

 dpTable[cur][t] = 10000; // set dpTable to high value
 // Step 1:  Try not moving
 dpTable[cur][t] = Math.min(dpTable[cur][t],
        getWet(cur, t) + getWet(cur, t+1) + dp(cur, t+1) );
 // Step 2:  Try moving right
 dpTable[cur][t] = Math.min(dpTable[cur][t],
        getWet(cur+1, t) + getWet(cur+1, t+1) + dp(cur+1, t+1) );
 // Step 3:  Try moving left
 dpTable[cur][t] = Math.min(dpTable[cur][t],
        getWet(cur-1, t) + getWet(cur-1, t+1) + dp(cur-1, t+1) );

 return dpTable[cur][t];

}

public int minimumRainTime(String path, String forecast)
{
 N = path.length();
 dpTable = new int[N][N*N+1];
 for(int i=0; i < N; i++)
  Arrays.fill(dpTable[i], -1);
 p = path;
 f = forecast;

 return dp(path.indexOf('Y'), 0);
}

Although this is sufficient, if the constraints were a little larger this algorithm would not work. For instance, if N were 500, the dpTable would take up 125,000,000 bytes. To fix this issue, consider the state that we currently use; it is based on the position and time. However, N minutes later, we face exactly the same subproblem; the forecast is the same as it was N minutes ago, and we are at the same position. Thus, we can save the state as dpTable[n][t%N], and this program uses N² memory, easily working for N=500.

Approach 2 - (alternatively titled, "You mean I could have avoided DP this whole time?')

If you aren't a fan of dynamic programming, there is a greedy method which can be used to solve the problem. Assume you are about to embark from a covered section into an uncovered section. One can prove that any time you step into an uncovered section, your next move will be to immediately move 1 section closer to home. The only time you should delay is when standing in a dry area while waiting for the forecast to rotate to its optimal place. Assume you start with the index of 'H' greater than that of 'Y'. If you come across n consecutive sections that are uncovered, you will move across them in n minutes. During that time period, you will be exposed to 2n sections from the forecast (since you alternate moving with the forecast). Since you are allowed to wait as long as you want to move, you can simply start at each part of forecast (from 0 to N-1) and determine how many times you get wet in that time. We can easily do this in O(N²) time, which is no problem with N=50. If 'H' is to the left of 'Y', we can use the same principle, except that we only care about segments of forecast of length 2 (because the rain is moving in the same direction as you). The code will therefore look something like this:

int minWet(String f, int t)
{
 t *= 2;    // we can potentially get wet twice per section
 int ret = 100000;
 for(int i=0; i < f.length(); i++)
 { int counter = 0;
  for(int j=0; j < t; j++)
   if(f.charAt((i+j)%f.length() ) == 'R')    // if there's rain there
    counter++;    // increment the counter
  ret = Math.min(ret, counter);    // take the best so far
 }
 return ret;
}

public int minimumRainTime(String path, String forecast)
{
 int y = path.indexOf('Y');
 int h = path.indexOf('H');
 if(y < h) // if we move right
 {
  int ret = 0;
  int openCount = 0;
  for(int i=y; i<=h; i++)
  {
     // keep track of how long the open space is
   if(path.charAt(i)=='.') openCount++;
   else
   {    // call the function to find out minimum wetness
    ret += minWet(forecast, openCount);
    openCount = 0;
   }
  }
  return ret;
 }
 else
 {
  int wetCount = minWet(forecast, 1);
  int ret = 0;
  for(int i=y; i>=h; i--)
   if(path.charAt(i)=='.') ret += wetCount;
  return ret;
 }

}

Homework

The above getWet() function runs in O(N²) time. Rewrite the function to run in O(N) time instead.

Value	500
Submission Rate	268 / 603 (44.44%)
Success Rate	204 / 268 (76.12%)
High Score	JongMan for 485.00 points (5 mins 1 secs)
Average Score	317.30 (for 204 correct submissions)

Let us represent the number n in base 10. So n = a₀*10⁰ + a₁*10¹ + ... + a_m*10^m. Now if we write this expression modulo 11, and keep in mind that (p-1) mod p = -1 mod p, we get:

n = (a₀*10⁰ + a₁*10¹ + a₂*10² ... + a_m*10^m) % 11
n = (a₀*10⁰)%11 + (a₁*10¹)%11 + (a₂*10²)%11 ... + (a_m*10^m) % 11
n = a₀*1 + a₁*(-1) + a₂*1 + ... + a_m*(-1^m)

Thus, to determine if n is a multiple of 11, we can alternately add and subtract the digits of the number; if the result is 0 modulo 11, then the original number was a multiple of 11.

So, how do we apply this to the problem at hand? We can solve the problem using DP; in this case, our state consists of which digit we are at (from 0 to m), the current sum modulo 11, and the amount of money that we have left. Our goal is to have the sum equal to 0 after processing digit m; if that is the case, we return the money we have left. To process each digit, we can simply try changing it to all digits between 0 and 9; it costs us abs(a_i-d) dollars to convert a_i into d. We then add this to the alternating sum, and move on to the next digit. Java code follows:

 long dpTable[][][];
String N;

long dp(int cur, int mod, int money)
{
 if(money < 1) return 0;
 if(cur==N.length() )
  return mod==0?money:0;

 if(dpTable[cur][mod][money] > -1)
  return dpTable[cur][mod][money];
 dpTable[cur][mod][money] = 0;
       // Try changing digit
 for(int i=0; i < 10; i++) // cur to i
 { int tempMod;
  if(cur%2==0) // if at an even place
   tempMod = (mod+i)%11;
  else   // if at an odd place
   tempMod = (mod-i+11)%11;
  dpTable[cur][mod][money] += 
   dp(cur+1, tempMod, money-Math.abs(N.charAt(cur)-'0'-i));
 }

 return dpTable[cur][mod][money];
}

public long maxIncome(int n, int money)
{
 N = "" + n;
  dpTable = new long[12][11][money+1];
 for(int i=0; i < 12; i++) for(int j=0; j < 11; j++)
  Arrays.fill(dpTable[i][j], -1);

 return dp(0, 0, money);
}

Homework

1. If we change the game from Round of Eleven to some other number (for example, Round of Twenty Three), how can we adapt the above algorithm to solve this problem?

2. Assume that there are N people in your kingdom, where N may be less than the number of prizes available from the show. Find a DP algorithm to determine your subjects' winnings in O(LM), where L is the number of digits in n, and M is the money you start with.

Value	1000
Submission Rate	119 / 603 (19.73%)
Success Rate	55 / 119 (46.22%)
High Score	ACRush for 941.35 points (7 mins 10 secs)
Average Score	676.83 (for 55 correct submissions)

This problem is a classic example of the min-cost maximum flow algorithm. We can represent this problem as a bipartite graph, placing the enter times on the left, and the exit times on the right. We then connect these nodes, giving them costs of 0 if end[j]-start[i] >= speedTime, infinity if start[i] >= end[j], or the appropriate cost otherwise. We then attach the source to all start nodes, and the sink to all exit nodes. Runnning the minimum cost flow algorithm yields the minimum fine that we can collect; if this is an infinite amount, then we know it is impossible to correctly pair the points. Now that we have the minimum fines, we want to determine the maximum fines that can be collected. The easiest way to do this is simply to multiply all of the weights (except for infinity) by -1. By running the minimum cost flow algorithm again, we then get a number that equals -1 times the maximum weight. We can thus return the correct answer, as can be seen in gevak's code.

Homework

Assume that there is no longer a fineCap. Is there an algorithm with O(1) additional memory (e.g. no DP tables allowed) that can determine the maximum fines to collect? What about the minimum?