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. The ProblemsMirroredClockUsed as: Division Two  Level One:
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? Lets 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. HandsShakingUsed as: Division Two  Level Two: Used as: Division One  Level One:
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. Used as: Division Two  Level Three:
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 wont install a new component if we would earn more without it and that we cant 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 2^{i}], 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
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 arent many mirror numbers smaller than 10^{18} 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:
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. Lets 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... 
