By supernova
TopCoder Member

It has been said that life is a school of probability. A major effect of probability theory on everyday life is in risk assessment. Let's suppose you have an exam and you are not so well prepared. There are 20 possible subjects, but you only had time to prepare for 15. If two subjects are given, what chances do you have to be familiar with both? This is an example of a simple question inspired by the world in which we live today. Life is a very complex chain of events and almost everything can be imagined in terms of probabilities.

Gambling has become part of our lives and it is an area in which probability theory is obviously involved. Although gambling had existed since time immemorial, it was not until the seventeenth century that the mathematical foundations finally became established. It all started with a simple question directed to Blaise Pascal by Chevalier de M�r�, a nobleman that gambled frequently to increase his wealth. The question was whether a double six could be obtained on twenty-four rolls of two dice.

As far as TopCoder problems are concerned, they're inspired by reality. You are presented with many situations, and you are explained the rules of many games. While it's easy to recognize a problem that deals with probability computations, the solution may not be obvious at all. This is partly because probabilities are often overlooked for not being a common theme in programming contests. But it is not true and TopCoder has plenty of them! Knowing how to approach such problems is a big advantage in TopCoder competitions and this article is to help you prepare for this topic.

Before applying the necessary algorithms to solve these problems, you first need some mathematical understanding. The next chapter presents the basic principles of probability. If you already have some experience in this area, you might want to skip this part and go to the following chapter: Step by Step Probability Computation. After that it follows a short discussion on Randomized Algorithms and in the end there is a list with the available problems on TopCoder. This last part is probably the most important. Practice is the key!

Basics
Working with probabilities is much like conducting an experiment. An outcome is the result of an experiment or other situation involving uncertainty. The set of all possible outcomes of a probability experiment is called a sample space. Each possible result of such a study is represented by one and only one point in the sample space, which is usually denoted by S. Let's consider the following experiments:

int wager (vector  scores, int wager1, int wager2)
{
 int best, bet, odds, wage, I, J, K;
 best = 0; bet = 0;

 for (wage = 0; wage ≤ scores[0]; wage++)
 {
  odds = 0;
  //  in 'odds' we keep the number of favorable outcomes
  for (I = -1; I ≤ 1; I = I + 2)
   for (J = -1; J ≤ 1; J = J + 2)
    for (K = -1; K ≤ 1; K = K + 2)
     if (scores[0] + I * wage > scores[1] + J * wager1  &&
      scores[0] + I * wage > scores[2] + K * wager2)   { odds++; }
  if (odds > best)  { bet = wage ; best = odds; }
  //  a better wager has been found
 }
 return bet;
}

1. What is the probability that all events will occur?
2. What is the probability that at least one event will occur?

int minPeople (int minOdds, int days)
{
 int nr;
 double target, p;

 target = 1 - (double) minOdds / 100;
 nr = 1;
 p = 1;

 while (p > target)
 {
  p = p * ( (double) 1 - (double) nr / days);
  nr ++;
 }

 return nr;
}

After the first nesting all integers have the same probability to occur, which is 1 / 4. For the second nesting there is a 1/4 chance for each of the following functions to be called: random(0), random(1), random(2) and random(3). Random(0) produces an error, random(1) returns 0, random (2) returns 0 or 1 (each with a probability of 1/2) and random(3) returns 0, 1 or 2. As a result, for the third nesting, random(0) has a probability of 1/4 + 1/8 + 1/12 of being called, random(1) has a probability of 1/8 + 1/12 of being called and random(2) has a probability of 1/12 of being called. Analogously, for the fourth nesting, the function random(0) has a probability of 1/4 of being called, while random(1) has a probability of 1/24. As for the fifth nesting, we can only call random(0), which produces an error. The whole process is described in the picture to the right.

NestedRandomness for N = 4

double probability (int N, int nestings, int target)
{
 int I, J, K;
 double A[1001], B[2001];
 // A[I] represents the probability of number I  to appear

 for (I = 0; I < N ; I++)  A[I] = (double) 1 / N;
 for (K = 2; K ≤ nestings; K++)
 {
  for (I = 0; I < N; I++)  B[I] = 0;
  // for each I between 0 and N-1 we call the function "random(I)"
  // as described in the problem statement
  for (I = 0; I < N; I++)
   for (J = 0; J < I; J++)
    B[J] +=  (double) A[I] / I;
    for (I = 0; I < N; I++)  A[I] = B[I];
 }
  return A[target];
}

• at least one parent has two dominant genes. (p = 1)
• each parent has exactly one dominant gene. (p = 0.5)
• one parent has one dominant gene and the other has only recessive genes (p = 0.25)
• both parents have two recessive genes (p = 0)

int n, d[200];
double power[200];

// here we determine the characteristic for each gene (in power[I]
// we keep the probability of gene I to be expressed dominantly)
double detchr (string p1a, string p1b, string p2a, string p2b, int nr)
{
 double p, p1, p2;
 p = p1 = p2 = 1.0;
 if (p1a[nr] ≤ 'Z')  p1 = p1 - 0.5;
 //  is a dominant gene
 if (p1b[nr] ≤ 'Z')  p1 = p1 - 0.5;
 if (p2a[nr] ≤ 'Z')  p2 = p2 - 0.5;
 if (p2b[nr] ≤ 'Z')  p2 = p2 - 0.5;
 p = 1 - p1 * p2;

 if (d[nr] != 1) power[nr] = p * detchr (p1a, p1b, p2a, p2b, d[nr]);
 // gene 'nr' is dependent on gene d[nr]
    else power[nr] = p;
 return power[nr];
}

double cross (string p1a, string p1b, string p2a, string p2b,
 vector  dom, vector  rec, vector  dependencies)
{
  int I;
 double fitness = 0.0;

 n = rec.size();
 for (I = 0; I < n; i++) d[i] = dependencies[i];
 for (I = 0 ;I < n; I++) power[i] = -1.0;
 for (I = 0; I < n; i++)
  if (power[I] == -1.0) detchr (p1a, p1b, p2a, p2b, i);
  // we check if the dominant character of gene I has
  // not already been computed
 for (I = 0; I ≤ n; I++)
  fitness=fitness+(double) power[i]*dom[i]-(double) (1-power[i])*rec[i];
  // we compute the expected 'quality' of an animal based on the
  // probabilities of each gene to be expressed dominantly

 return fitness;
}

1. Monte Carlo algorithms: may sometimes produce an incorrect solution - we bound the probability of failure.
2. Las Vegas algorithms: always give the correct solution, the only variation is the running time - we study the distribution of the running time.

1. the submission was just a desperate attempt and will most likely fail on many inputs.
2. the algorithm was tested rather thoroughly and the probability to fail (or time out) is virtually null.

Max = 1000000; attempt = 0;
while (attempt < Max)
{
 answer = solve_random (...);
 if (better (answer, optimum))
 // we found a better solution
 {
  optimum = answer;
  cout << "Solution " << answer << " found on step " << attempt << "\n";
 }
 attempt ++;
}