Tuesday, October 20, 2015

BirthdayOdds

Problem:

TopCoder Problem Statement - BirthdayOdds
Single Round Match 174 Round 1 - Division I, Level One
Single Round Match 174 Round 1 - Division II, Level Two

Overview:

Calculate the mininum number of people required to assure that the probability of two people sharing a birthday meets the given threshold. The number of days in a year may vary.

Java Source:
     1
     2
     3 public class BirthdayOdds {
     4
     5  public int minPeople(int minOdds, int daysInYear) {
     6
     7   double pA = 1.0;
     8   double days = (double) daysInYear;
     9   double cutOff = 1.0 - (minOdds / 100.0);
    10
    11   int numPeople = 1;
    12
    13   while (pA > cutOff)  {
    14    pA *= ((double) (daysInYear - numPeople) / days);
    15    numPeople++;
    16   }
    17
    18   return numPeople;
    19
    20  }
    21 }
Notes:

For a detailed discussion of the Birthday Problem, see the wikipedia entry here. This solution is based on the formula given in the "Calculating the probability" section.

Essentially we're calculating the probability that there is not a match, and then adding more and more people thus reducing that probability until a certain threshold is met. That threshold is (1 - minOdds) since we're calculating the probability of not matching whereas minOdds is the probability of a match.

pA begins at 1 (i.e. daysInYear / daysInYear), then is multiplied by (daysInYear - 1 / daysInYear), (daysInYear - 2 / daysInYear), (daysInYear - 3 / daysInYear), ... With each multiplication pA gets smaller until it falls under the cutoff.

RGBColor

Problem:

TopCoder Problem Statement - RGBColor
Single Round Match 176 Round 1 - Division II, Level One

Overview:

Compute the compliment of the given RGB color.

Java Source:
     1 import java.util.*;
     2 import java.math.*;
     3 import static java.lang.Math.*;
     4
     5 public class RGBColor {
     6
     7     private static final int RGB_MAX = 255;
     8     private static final int GREY_TOLERANCE = 32;
     9
    10  public int[] getComplement(int[] rgb) {
    11
    12   int[] compliment = new int[rgb.length];
    13
    14         boolean isGrey = true;
    15
    16         for (int i = 0; i < rgb.length; i++)  {
    17             compliment[i] = RGB_MAX - rgb[i];
    18             if (Math.abs(rgb[i] - compliment[i]) > GREY_TOLERANCE) isGrey = false;
    19         }
    20
    21         if (isGrey)  {
    22             for (int i = 0; i < rgb.length; i++)  {
    23                 compliment[i] = (rgb[i] >= 128) ? rgb[i] - 128 : rgb[i] + 128;
    24             }
    25         }
    26
    27         return compliment;
    28
    29  }
    30 }
Notes:

We need to deal with two separate cases here: the color may meet the given definition of grey, or it may not. The trouble is, we won't know if it's considered grey or not until we've examined all three colors. We'll start by assuming that the color is grey, and then flip the isGrey flag to false if we find a red, green, or blue value whose compliment exceeds GREY_TOLERANCE.

We start by creating the output array named compliment. Then for each value in rgb, we calculate the corresponding compliment by subtracting the color in the current position of rgb from RGB_MAX. If the difference between a color and its compliment exceeds GREY_TOLERANCE, then we'll set isGrey to false.

After red, green, and blue have all been evaluated, if isGrey is still true then we need to handle it according to the instructions for a grey color. For each position in rgb, if the value is greater than or equal to 128, we subtract 128, otherwise add 128. This value will overwrite the value in compliment[] that was stored earlier.

Saturday, October 10, 2015

Removal

Problem:

TopCoder Problem Statement - Removal
Single Round Match 177 Round 1 - Division I, Level Two
Single Round Match 177 Round 1 - Division II, Level Three

Overview:

Remove items from a list filling in the space by shifting all following elements up one. Return the item at the given position after all the removals.

Java Source:
     1 public class Removal {
     2
     3  public int finalPos(int n, int k, String[] remove) {
     4
     5   for (int i = remove.length - 1; i >= 0; i--)  {
     6
     7    String[] hilo = remove[i].split("-");
     8    int lo = Integer.parseInt(hilo[0]);
     9    int hi = Integer.parseInt(hilo[1]);
    10
    11    if (k >= lo)  {
    12     k += (hi - lo + 1);
    13    }
    14
    15    // If k < 0, then we've overflowed, return a -1.
    16    if ((k > n) || (k < 0)) return -1;
    17   }
    18
    19   return k;
    20  }
    21
    22 }
Notes:

You might assume that you could use a built-in data structure, such as a linked list to solve the problem. Just initialize the list, and then let it do the removals for you. However, it pays to take a look at the constraints first. The number of elements can be up to 2,000,000,000 which is way too much to fit into the allotted 64MB.

The solution is to think about how k's position changes as elements in front of it are removed. Elements that are greater than k don't matter when they're removed since these won't affect k's position.

We start at the end work backwards through each String in remove. First, parse out the lo and hi elements of the string. Then, if lo is less than k, we'll adjust k's position accordingly. The number of elements removed is given by (hi - lo + 1). So, we increase k's value by that amount to get it's position before the removals.

After working backward through all the elements in remove, the value of k will be it's original starting position which is the value we want to return.

Be careful to check the value of k after each addition. If it's ever greater than n, we'll return -1. The addition could also cause an overflow. You could convert k to a long to prevent this, or just check the value to see if it becomes negative. Since the value of hi will be 2 billion or less, it will fit into an int. Adding 2 billion to a positive int and causing an overflow will always result in a negative number.

Thursday, October 8, 2015

Matching

Problem:

TopCoder Problem Statement - Matching
Single Round Match 176 Round 1 - Division I, Level One
Single Round Match 176 Round 1 - Division II, Level Two

Overview:

Find the card which completes the pattern. For each group of characteristics, the matching card must either share the trait with the other two cards, or all three cards must have a different value.

Java Source:
     1 public class Matching {
     2
     3  private static final String[][] TRAITS = {
     4    {"CIRCLE", "SQUIGGLE", "DIAMOND"},
     5    {"BLUE", "RED", "GREEN"},
     6    {"SOLID", "STRIPED", "EMPTY"},
     7    {"ONE", "TWO", "THREE"}
     8  };
     9
    10  public String[] findMatch(String[] first, String[] second) {
    11
    12   String[] result = new String[4];
    13
    14   for (int i = 0; i < TRAITS.length; i++)  {
    15    result[i] = getMatch(first[i], second[i], TRAITS[i]);
    16   }
    17
    18   return result;
    19
    20  }
    21
    22  private static String getMatch(String s1, String s2, String[] traits)  {
    23
    24   /*
    25   * If the two strings are equal, then return that string.
    26   */
    27   if (s1.equals(s2)) return s1;
    28
    29   /*
    30   * Otherwise, return the string that is not s1 or s2
    31   */
    32   for (int i = 0; i < traits.length; i++)  {
    33    if (!traits[i].equals(s1) && !traits[i].equals(s2))
    34     return traits[i];
    35   }
    36
    37   return null;
    38
    39  }
    40 }
Notes:

This is one of those problems where reading the description makes you think it's going to be much more difficult than the problem actually is. All we need to do is for each of the four traits (shape, color, fill pattern, and count) give the value of the string if the first and second card have the same value. Or, if the first and second cards have different values, then we give the third (or odd man out) value.

The for loop in the findMatch() method just walks through each of the four traits, and calls getMatch() to insert the correct value into the result array.

getMatch() compares the two strings, and if they're equal returns that value. Otherwise, it looks through the values given in traits for a string that does not match s1 and does not match s2. Note that we should never reach the return null statement on line 37, but it needs to be there to satisfy the compiler.

Nothing difficult here. Getting through the description actually took longer than writing the code.

Tuesday, October 6, 2015

Stairs

Problem:

TopCoder Problem Statement - Stairs
Single Round Match 177 Round 1 - Division II, Level One>

Overview:

Count the number of combinations of risers and treads that can lead to a staircase of the given dimensions.

Java Source:
     1 public class Stairs {
     2
     3     public int designs(int maxHeight, int minWidth, int totalHeight, int totalWidth) {
     4
     5         int count = 0;
     6
     7         for (int riserHeight = 1; (riserHeight <= maxHeight); riserHeight++) {
     8             if ((totalHeight % riserHeight) != 0) continue;
     9
    10             int numTreads = (totalHeight / riserHeight) - 1;
    11
    12             if ((numTreads == 0) ||
    13                     ((totalWidth % numTreads) != 0) ||
    14                     ((totalWidth / numTreads) < minWidth)) continue;
    15             count++;
    16         }
    17
    18         return count;
    19     }
    20 }
Notes:

Note that the size of both the risers and treads must be integers, and that they are at most 1,000. This means that a brute force search is certainly possible. We'll loop through all possible heights and count the number of configurations that are possible.

For each riser height, we first check to see if it evenly divides the total height. If not, then we can continue on with the next height. If so, then we'll look at the treads.

The number of treads will be one less than the number of risers. We can compute the number of risers with (totalHeight / riserHeight). Then just subtract one from that result to get the number of treads.

Next, we look for ways to discount the current number of risers and treads. The problem statement says that their must be at least one tread (and riser), so we can throw out any cases where the number of treads is 0. Again, just like with the risers, the total width must be evenly divided by the number of treads, so we can skip any case where that isn't true. And finally, any case where the width of each tread (totalWidth / numTreads) is smaller than the minimum allowed can also be skipped.

Passing each of those tests, leaves us with a valid configuration, so increment the counter. After looping throug all possibilities, return the value in the counter.