Match Editorial

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

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.

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)

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(n²) dynamic programming. It’s interesting, though it’s only a theory.

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 )  ,

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 10¹⁸ – 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;
    }
  }

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.