JOIN
 Match Editorial
SRM 363
Saturday, August 11, 2007

## Match summary

As the last chance to practice before the TCCC 2007 qualification rounds, SRM 363 attracted 1312 coders. The match in Division 1 started very fast as the easy problem was quite standard. The tricky medium forced many high ranked competitors to resubmit their solutions, which caused unexpected results in the division summary. Unfortunately, the 1000 pointer was too hard (maybe even NP hard) to be solved by anyone (including me). On the other hand, in Division 2, the difficulty level of the problems was almost perfect, though the easy was a bit unusual.

Only 5 coders solved correctly the hard in Division 2 and they took the top five spots with ellenjuice on top (with a quite comfortable lead) and dzwiedziu and Mingfei_Li rounding up the top three.

# The Problems

MirroredClock
Used as: Division Two - Level One:
 Value 250 Submission Rate 699 / 747 (93.57%) Success Rate 476 / 699 (68.10%) High Score cdart. for 249.56 points (1 mins 11 secs) Average Score 189.72 (for 476 correct submissions)

It is obvious that if a minute hand points m minutes past some hour, it will point 60  m past some (possibly other) hour in the mirror. But what happens with the hour hand after mirroring the clock? Lets assume that we have the time h : m. The hour hand points exactly to an h hour (when m is equal to 0) or a bit past an h hour (when m is positive). What can we see in the mirror? When m is equal to 0, mirrored hour hand points exactly 12  h hour, and it points a bit before it, otherwise. So, getting all the things together, mirroring the time h : m, we get 12  h : m if m is equal to 0, and 11  h : 60  m, otherwise (note, that if an hour hand points some time before the x hour, it also points some time after the x  1 hour). Of course, we should be aware not to return 12 instead of 00 and also not to return a negative hour.

HandsShaking
Used as: Division Two - Level Two:
 Value 500 Submission Rate 383 / 747 (51.27%) Success Rate 200 / 383 (52.22%) High Score kilvdn for 492.80 points (3 mins 26 secs) Average Score 323.00 (for 200 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 531 / 565 (93.98%) Success Rate 486 / 531 (91.53%) High Score Petr for 249.24 points (1 mins 34 secs) Average Score 207.13 (for 486 correct submissions)

With a little imagination, we will quickly see that there exists a bijection between the set of perferct shakes for n businessmen and the set of valid bracket structures of length n. It seems quite intuitive when we treat each businessman as ( or ). The problem of counting those structures can be easily solved with dynamic programming as f(n) = (sum for all 0 < i <= n) f(i  1) * f(n  i  1). We can also look at this in such a way (and this is probably more intuitive) that each handshake divides the table in two, because the handshakes cannot cross. So, we can take businessman 0, iterate over all other businessmen and each time count recursively how many shakes are there for the rest. It leads to the same formula as above.

Also, it is worth mentioning that the number of valid bracket structures of length 2n is equal to the n-th Catalan number (you can see the Wikipedia article on Catalan numbers), so using an explicit formula for it, we can solve the problem in O(n) time instead of O(n2) dynamic programming. Its interesting, though its only a theory.

CrazyComponents
Used as: Division Two - Level Three:
 Value 1000 Submission Rate 16 / 747 (2.14%) Success Rate 5 / 16 (31.25%) High Score ellenjuice for 798.91 points (15 mins 3 secs) Average Score 606.65 (for 5 correct submissions)

Imagine that at some point of the process described in the problem, we have some component types already installed and k turns to complete. Such a state is uniquely defined by the values k and a boolean type for each component representing whether or not we have already installed it (they can be all represented as a bitmask). It shouldn't be a surprise, that we can now solve the problem with dynamic programming. In each state, all the components have an equal probability of being chosen, so we can check each possibility and compute the expected profit. Of course, we must keep in mind that we are building our application optimally  we wont install a new component if we would earn more without it  and that we cant install a component without its requirements satisfied. So, if A[k][mask] denotes the expected profit with k turns left to go and components represented by mask already installed, our recurrence equation would look like this:

```  A[k][mask] = (sum for all 0 <= i < n)
1/n * ( max( A[k  1][mask OR 2i], A[k  1][mask] ) if mask satisfies
all the requirements of component i, and
A[k  1][mask], otherwise )  ,
```
where n is the number of available components. See the fastest solution by ellenjuice for a perfect implementation of the above idea.

MirrorNumber
Used as: Division One - Level Two:

 Value 500 Submission Rate 262 / 565 (46.37%) Success Rate 121 / 262 (46.18%) High Score ACRush for 445.87 points (10 mins 9 secs) Average Score 272.54 (for 121 correct submissions)

The most obvious solution to this problem is a combinatorial one. If we had a function f(x) that returns how many numbers between 0 and x are the mirror ones, then we would simply compute an answer to the problem as f(B)  f(A  1). Although this approach seems quite straightforward at first, it turns out to be very complicated to make it work correctly (you can check Im2Good's solution or andrewzta's one just to see how much). The reason for this is that while it is easy to compute the number of mirror numbers of a given length, there arise many special cases when computing how many mirror numbers there are that are not greater than some given x. So, when all these special cases begin to appear, we should think how we can solve the problem in an easier way. The main observation is that there arent many mirror numbers smaller than 1018  there are exactly 3124999 of them. We can generate them all and count how many are in a given interval. It's tricky, but simple. Sample Java implementation follows:

```  public class MirrorNumber {
int dig[] = { 0, 1, 8, 2, 5 }, rev[] = { 0, 1, 8, 5, 2 };
int num[] = new int[20];
long A, B;
int res, len;

public void recur (int a, int b) {
if (a < b) for (int i = (a > 0) ? 0 : 1; i < 5; i++) {
num[a] = dig[i];
num[b] = rev[i];
recur(a + 1, b - 1);
}else if (a == b) for (int i = 0; i < 3; i++) {
num[a] = dig[i];
recur(a + 1, b - 1);
}else {
long tmp = 0, mul = 1;
for (int i = len; i >= 0; i--) {
tmp += num[i] * mul;
mul *= 10;
}
if (tmp >= A && tmp <= B) res++;
}
}

public int count (String A, String B) {
this.A = Long.parseLong(A); this.B = Long.parseLong(B);
res = 0;
for (len = 0; len < 18; len++) recur(0, len);
return res;
}
}
```

PackageDelivery
Used as: Division One - Level Three:
 Value 1000 Submission Rate 24 / 565 (4.25%) Success Rate 11 / 24 (45.83%) High Score almelv for 592.02 points (28 mins 2 secs) Average Score 466.68 (for 11 correct submissions)

When I came up with the idea for this problem (which all in all is not bad itself, I think), I was wondering what I could do to make the problem harder. I was making it harder and harder and finally I made it probably unsolvable. As people discovered, the detail that caused a flaw was truckCapacity. Lets assume that the truck has unlimited capacity (i.e. we can always take all the packages at once). First, let's see that we can park the truck only in packages' destinations (and the warehouse) and we will still be able to stay optimal (if in the optimal solution we park between some two destinations and walk to them from the truck, we can also park in one of them and walk to the other and the solution won't change). So, instead of a million of possible parking locations, we have just 50 - quite good. The next observation is that in the optimal solution we can deliver packages in increasing order of destination's distance from the warehouse. As we can pack all the packages to the truck, we will never need to come back. The only thing we need to find out is where to park the truck (and whether we should use it at all). We can define a state as the position of the truck and the number of packages from the beginning that we have already delivered. Now, we can easily solve the problem with dynamic programming - at each state we can move the truck or deliver some packages on foot. Well, that was not so hard...

...and then I came up with the idea of limited capacity of the truck. With the same assumptions as above I defined the state as the position of the truck, the number of packages from the beginning that we have already delivered, and the number of packages on the truck. As it turned out, with limited capacity of the truck, the assumption of delivering packages in order is wrong. And so, nobody knows if a correct (and fast enough) solution even exists.

By mateuszek
TopCoder Member