SRM_Blog
SRM Editorials

Rookie SRM 2 Editorial

FriendFinder

This problem is fairly straightforward, requiring the solution to find the location of self and friend in the string. Once those two locations are known, it’s just a matter of subtracting the two values to determine the distance.

The problem constraints ensure that there is nothing too tricky. The only thing to be careful about is to avoid returning a negative number, in case yourself and your friend appear in the opposite order you expect.

It’s possible to solve this in a single line, even:


public int distance(String line) {
return Math.abs(line.indexOf('S') - line.indexOf('F'));
}

PairedMultiples

The biggest thing to observe in this problem--because we’re dealing only with positive values--is that if any two values can sum to something with the proper divisibility, they should always be included in the subset.

Knowing this, our solution is in two steps: loop through each possible pair of initial values and test the divisibility of the sum, making off both members of the pair if the divisibility works out. Then, iterate through the full set, adding all the previously marked values that should be included in the subset.


public int selectedTotal(int[] values, int multiple) {
boolean[] marked = new boolean[values.length];
for (int i = 0; i < values.length; i++)
for (int j = i + 1; j < values.length; j++)
if ((values[i] + values[j]) % multiple == 0)
marked[i] = marked[j] = true;
int total = 0;
for (int i = 0; i < marked.length; i++)
if (marked[i])
total += values[i];
return total;
}

MarbleDrawGame

First, we recall the basic rule of probability… our chances of winning are the number of ways to win divided by the total number of possible outcomes. Now, we just need to calculate those two values, and divide to get our desired result. We might recall in basic combinatorics that the number of ways to select r things from a set of n is given by nCr = n! / ((n-r)! r!). In fact, why don’t we write a function to calculate this for us, using long integers to avoid overflow. (Note that we will never be selecting more than 9 items from a maximum of 50, thus we can be sure this function won’t overflow a 64-bit integer.) We will use this function in our solution below.


public long nCr (int n, int r) {
if (r
n) return 0;
long ret = 1;
for (int x = 0; x < r; x++) ret *= (n - x);
for (int x = 1; x <= r; x++) ret /= x;
return ret;
}

Now, we will want to sum up the total number of marbles in our bag, which we will call “count”. And thus, nCr(count, 9) is the denominator of our initial equation.

Now, how many ways can we draw marbles and win? We could draw exactly 5 of the first color, and 4 of any other color, or 6 and 3, or 7 and 2, or 8 and 1, or all 9 of the first color. Or… we could do similarly for any of the other colors. So, we iterate through our colors, and calculate the number of ways to draw exactly 5, 6, 7, 8, 9 of each color, with the rest being of any other color. Adding up the total number of ways this can happen gives us the numerator for our initial equation. Now we just need to divide. Note the initial multiplication by 1.0, which coerces the calculations to be done as a floating point rather than with integer division.


public double winningChance(int[] marbles) {
int count = 0;
for (int i = 0; i < marbles.length; i++) count += marbles[i];
long win = 0;
for (int i = 0; i < marbles.length; i++) {
win += nCr(marbles[i], 5) * nCr(count - marbles[i], 4);
win += nCr(marbles[i], 6) * nCr(count - marbles[i], 3);
win += nCr(marbles[i], 7) * nCr(count - marbles[i], 2);
win += nCr(marbles[i], 8) * nCr(count - marbles[i], 1);
win += nCr(marbles[i], 9) * nCr(count - marbles[i], 0);
}
long total = nCr(count, 9);
return 1.0 * win / total;
}