Match Editorial

Match summary

Formula One has got its light signals, Soccer World Cup has the first whistle, for Olympic Games there is a great opening ceremony. The Algorithm competition of TCO 2008 was launched in a less spectacular way: by a small gray window stating that the coding phase has started. But even if the start wasn't that spectacular, the battle that soon started was as fierce as in any of the other competitions.

The problemset offered many ways to qualify: Solving a tricky 250, implementing an almost-textbook dynamic programming in the 600, or finding a working approach for the 900... And last but not least, there was the opportunity to gain easy points from challenges, especially on the easy submissions.

An interesting consequence of a less-traditional easy problem: After a quarter of an hour, the top 20 was populated by coders of all colors. (And there didn't seem to be much corelation between their colors and the correctness of their solutions.) The most significant event in the coding phase was blackmath's great time on the hard problem. This gave him a comforting lead at the beginning of the challenge phase.

But things were about to change. Astein's 275 points from challenges gave him the first place, and blackmath had to settle for second. Third place went to showbu.

Congratulations to all the advancers, and let the best ones advance in the remaining two qualification rounds!

The Problems

Value	250
Submission Rate	815 / 1014 (80.37%)
Success Rate	268 / 815 (32.88%)
High Score	bcloud for 244.60 points (4 mins 14 secs)
Average Score	161.90 (for 268 correct submissions)

Notation: Let C(N,K) be the number of ways in which we can choose K out of N objects. We can compute C(N,K) as N! / ( K! * (N-K)! ).

Monsters only

First, let's solve an easier version of the problem – for now, we will try to solve the situation where there are no bunnies.

The first important thing is to notice that in each meeting either 0 or 2 monsters die. This means that the parity of monsters never changes. If the initial number of monsters is odd, it will always be odd, and thus it can never decrease to zero. In other words, if the initial number of monsters is odd, we can not win.

Furthermore, we can make the following observation: If there are M monsters and me, there are C(M+1,2) possibilities for the first meeting. In M of these, we meet a monster and die. In the remaining C(M,2), two monsters meet and die, and we are left with M-2 monsters.

Let p(M) be the probability that we win the game if there are currently M≥2 monsters in the town. We just explained the following formula:

p(M) = ( C(M,2) / C(M+1,2) ) * p(M-2)

Together with the initial conditions p(0)=1 and p(1)=0 this gives us a solution that runs in time O(M).

Constant time solution

Using the above formula, we can compute:

P(2) = C(2,2) / C(3,2) = 1/3
P(4) = (C(4,2) / C(5,2)) * P(2) = 6/10 * 1/3 = 3/5 * 1/3 = 1/5
P(6) = (C(6,2) / C(7,2)) * P(4) = 15/21 * 1/5 = 5/7 * 1/5 = 1/7

We start to see a pattern emerging: p(2K)=1/(2K+1). This can easily be proved using mathematical induction. Instead, we will show a combinatorial argument.

Consider a game where the number of monsters is 2K. We will make two slight modifications to our game rules:

• When you meet a monster, you kill each other.
• If you die, the game continues until there is only one monster left.

Clearly, these changes don't affect your chance of survival. However, they have an important consequence: They make the game symmetric. Each of the 2K+1 players (that is, 2K monsters + us) has got an equal probability of being the last one alive. And this probability clearly has to be 1/(2K+1).

What about the bunnies?

Imagine that you have a fair 6-sided dice. Consider the following algorithm: "Repeatedly throw the dice until you get either a 1, or a 6." Clearly, the probability of ending with a 1 is the same as the probability of ending with a 6.

Now, what would happen if the dice were biased? For example, let prob(1)=1/13 and prob(6)=3/13. How will this affect the final outcome of our algorithm?

Note that we don't even need to know how probable each of the outcomes 2, 3, 4, and 5 is. What matters is that in each throw the outcome 6 is three times more likely than the outcome 1. If we make many throws, we will get approximately three times as many 6s as 1s. Thus, for example, if we executed our algorithm 400 times, we can expect 300 runs to end with a 6, and only 100 to end with a 1.

This reasoning can be formalized using conditional probability. The probability of our algorithm returning 6 is the probability of a throw returning 6, given that we know it returned (6 or 1). This probability can be computed as prob(6) / (prob(1)+prob(6)).

The moral of the story: The outcome of our algorithm only depends on the ratio prob(1):prob(6).

Okay, but what about the bunnies?

The bunnies don't influence monster count in any way. We can simply ignore all meetings that involve bunnies, just as in the above experiment we ignored outcomes 2, 3, 4, and 5, and only focused on 1s and 6s.

More precisely, we have a town with monsters and possibly some bunnies. We will generate the meetings (throw the dice), until we get an important meeting that does not involve a bunny (the throw ends with a 1 or a 6). Now there are two possible outcomes: either we meet a monster and lose (the algorithm returns 1), or two monsters meet and we win (the algorithm returns 6).

We can make the same argument as before: The probability that in the important meeting two monsters meet (the algorithm returns a 6) depends only on the ratio of probabilities prob(two monsters meet):prob(you meet a monster).

The two probabilites in question can be expressed as:

prob(two monsters meet)  = C(M,2) / C(M+B+1,2)
prob(you meet a monster) =      M / C(M+B+1,2)

And thus their ratio is always the same, C(M,2):M.

This means that if we completely ignore the bunnies, and only focus on the meetings that involve us and the monsters, we will get the correct result.

(A good way of looking at the bunnies: We and the monsters are playing the game. The bunnies just roam around and get into our way, but they don't influence our game in the same way ducks that fly above the town don't influence it.)

(Yet another way of getting the right intuition on bunnies: Consider the modified rules that make the game symmetric. The bunnies can't help you, and they also can't help the monsters, simply because of the symmetry. If there was an argument that shows, say, "if there are more bunnies, you have a higher chance to win", the same argument could be used to show "if there are more bunnies, the k-th monster has a higher chance to win", and that is not possible.)

Summary

We just explained that for all values of B and even values of M the answer is 1/(M+1), and for all other inputs the answer is 0.

Dynamic programming

Finally, we would like to note that the entire task was solvable without the above analysis, just by rewriting the problem statement as a recursive formula, and then use dynamic programming to evaluate it. The code for such a solution follows.

  double fullDP(int M, int B) {
    double[][] prob = new double[M+1][B+1];
    for (int m=0; m<=M; m++)
      for (int b=0; b<=B; b++) {
        if (m==0) { prob[m][b]=1.0; continue; }
        int allEvents = (m+b+1)*(m+b)/2;
        int MMEvents = m*(m-1)/2;   double MMProb = 1.0*MMEvents/allEvents;
        int MBEvents = m*b;         double MBProb = 1.0*MBEvents/allEvents;
        int BBEvents = b*(b-1)/2;   double BBProb = 1.0*BBEvents/allEvents;
        int HMEvents = m;           double HMProb = 1.0*HMEvents/allEvents;
        int HBEvents = b;           double HBProb = 1.0*HBEvents/allEvents;
        double pp = 0.0;
        if (m>=2) pp += MMProb * prob[m-2][b]; // two monsters meet and die
        if (b>=1) pp += MBProb * prob[m][b-1]; // a monster kills a bunny
        if (b==0) {
          prob[m][b] = pp;
        } else {
          // we meet a bunny, examine whether killing it is better than
          // letting it go, and pick the better possibility
          prob[m][b] = Math.max( (1-BBProb)*(pp + HBProb*prob[m][b-1]) , (1-BBProb-HBProb)*pp );
        }
      }
    return prob[M][B];
  }

Value	600
Submission Rate	339 / 1014 (33.43%)
Success Rate	143 / 339 (42.18%)
High Score	antimatter for 573.35 points (6 mins 10 secs)
Average Score	390.08 (for 143 correct submissions)

This task could be split into two separate questions:
1. "How many sub-bags of the given bag have weight W?"
2. "Is W a prime number?"

The bag has at most 50 elements, and they don't exceed 10,000. Thus the values W for which we need to answer these questions lie in the range from 0 to 500,000.

Prime numbers

Checking whether a number is prime can be done by a trivial algorithm: The number N is prime if it is greater than 1, and no number between 2 and sqrt(N), inclusive, divides N.

There are also more efficient methods. One particularly suitable and easy to implement is the Sieve of Eratosthenes.

Subset counts

This part of the problem was an exercise in knapsack-style dynamic programming.

First, let's show how to solve the problem for sets, i.e., in the case when all input values are distinct.

Let N(X,W) be the number of subsets that only use first X elements from the input, and have weight W.

Clearly, N(0,0)=1, and N(0,W)=0 for any positive W.

Now, how to compute N(X,W) for a positive X?

We can split all the subsets counted by N(X,W) into two kinds: those that don't contain the X-th element, and those that do. For the first kind, the count of such subsets is clearly N(X-1,W). For the second kind, take a look at how the rest of the set can look like. It may only contain some of the first X-1 elements, and its weight has to be W-(weight of the X-th element). Thus the number of subsets of the second type is N(X-1,W-weight(X)).

In this simple case, all the values N(X,W) can be computed at the same time using the following pseudocode:

set N(0,0)=1
for all w from 1 to maxW: set N(0,w)=0
for all x from 1 to maxX:
   for all w from 0 to maxW:
      N(x,w) = N(x-1,w)
      if (weight(x) ≤ w): N(x,w) += N(x-1,w-weight(x))

Handling duplicates

In the general case we need to make sure we don't count identical sub-bags more than once. To achieve this, we will simply process all equal values at the same time. This means that the recurrence relation won't have 2 cases (take element X or not?), but multiple cases (take element X how many times?).

Fitting it all into memory

The entire array needed to store the values N(x,w) would not fit into the memory limit. Luckily, we have two circumstances speaking in our favor: First, we only need the values N(maxX,*). Second, to compute the values N(X,*) we only need the values N(X-1,*). This means that we can only remember two rows of the table at any time.

Java code follows.

  int SUM;
  boolean[] isPrime;
  long[][] ways;

  public long getCount(int[] bag) {
    SUM=0;
    for (int i=0; i<bag.length; i++) SUM += bag[i];
    Arrays.sort(bag);

    // do the sieve
    isPrime = new boolean[SUM+1];
    Arrays.fill(isPrime,true);
    isPrime[0]=isPrime[1]=false;
    for (int i=2; i*i<=SUM; i++)
      if (isPrime[i])
        for (int j=i*i; j<=SUM; j+=i) isPrime[j]=false;

    ways = new long[2][SUM+1];
    Arrays.fill(ways[0],0);
    Arrays.fill(ways[1],0);
    ways[0][0] = 1;

    int last=0, next=1;
    for (int i=0; i<bag.length; i++) {
      if (i>0) if (bag[i]==bag[i-1]) continue; // skip duplicates
      // count duplicity
      int cnt=1;
      while (i+cnt < bag.length) if (bag[i+cnt]==bag[i]) cnt++; else break;
      // fill in new values
      for (int s=0; s<=SUM; s++) {
        ways[next][s] = ways[last][s];
        for (int t=1; t<=cnt; t++) if (s-t*bag[i] >= 0) ways[next][s] += ways[last][s-t*bag[i]];
      }
      // prepare next step
      last=1-last; next=1-next;
    }

    long result = 0;
    for (int i=0; i<=SUM; i++) if (isPrime[i]) result += ways[last][i];

    return result;
  }

Footnote

There is at least one asymptotically better algorithm than this one. Can you find one? (Hint: There is a better way how to handle the duplicates.)

Value	900
Submission Rate	69 / 1014 (6.80%)
Success Rate	34 / 69 (49.28%)
High Score	blackmath for 738.74 points (13 mins 55 secs)
Average Score	500.91 (for 34 correct submissions)

There were two possible approaches, and they can be labeled "filter and precompute", and "generate".

Filtering

If implemented efficiently, the magic fingerprint method is pretty fast, and any reasonably fast computer can process all numbers up to 1 billion in a matter of a few minutes. Well, but the time limit is just two seconds... What can we do to help?

The answer is: let your computer do most of the work. For example, pre-compute the answer for inputs of the type [k*10^6,(k+1)*10^6). You will get around 1,000 values. Store these in your program as an array of integer constants. Now, if you get a large input, it surely contains many of these ranges. Just add together all their counts. Now you only need to compute magic fingerprints for a few elements at the beginning and at the end of the given range.

A similar approach was used in blackmath's fastest solution.

Generating

Clearly, the number N is lucky if and only if magic(N) is lucky. So far, we used one direction: given N, compute magic(N). However, a more efficient way is to do it backwards: given magic(N), determine all possible N.

This isn't too hard. For example, suppose that magic(N)=8111. How many five-digit Ns are there? We can generate them recursively. We start by trying the first digit 1. Then the second digit has to be 9, the third has to be 8. We have two choices for the fourth digit: the first one leads to the numbers 19876 and 19878, the second one yields the number 19898. And so on. (In this case, leading digits 8 and 9 will bring some more solutions.)

We can now use breadth-first search to generate all lucky numbers less than a billion: Start with the number 7, and for each number X we process, find all N≤10^9 such that magic(N)=X, and add them into the queue to be processed.

Java code that generates all lucky numbers follows.

  Set<Integer> lucky;
  Queue<Integer> process;
  int[] digits;
  int digitCount;
  int[] newDigits;

  void generate(int where) {
    if (where==-1) {
      int current = 0;
      for (int d=digitCount; d>=0; d--) {
        current *= 10;
        current += newDigits[d];
      }
      if (!lucky.contains(current)) {
        lucky.add(current);
        process.add(current);
      }
    } else {
      newDigits[where] = newDigits[where+1] + digits[where];
      if (newDigits[where]>=0 && newDigits[where]<=9) generate(where-1);
      newDigits[where] = newDigits[where+1] - digits[where];
      if (newDigits[where]>=0 && newDigits[where]<=9) generate(where-1);
    }
  }

  public int countLuckyNumbers(int A, int B) {
    lucky = new HashSet<Integer>();
    process = new LinkedList<Integer>();
    digits = new int[12];
    newDigits = new int[12];

    lucky.add(7);
    process.add(7);
    while (!process.isEmpty()) {
      int current = process.remove();
      digitCount = 0;
      while (current > 0) { digits[digitCount++] = (int)current%10; current /= 10; }
      while (digitCount<=8) {
        for (int i=1; i<10; i++) {
          newDigits[digitCount]=i;
          generate(digitCount-1);
        }
        digits[ digitCount++ ] = 0;
      }
    }
    int result = 0;
    for (Integer x : lucky) {
      if (A<=x && x<=B) result++;
      System.out.println(x);
    }
    return result;
  }