Reception

Room 1

Room 2

Room 3

Room 4

Final Round

Slide Show

Play-by-Play  |  Photos  |  Problem Analysis

Problem Set Analysis & Opinion

by schveiguy,
TopCoder Member
Thursday, December 4, 2003

MakeUnique
Used as: Division 1 - Level 1:

Given a string of characters, this problem asks you to remove characters from the string such that the remaining characters are unique in the string, are in alphabetical order, and represent all the characters from the original string. The removed characters are replaced with '.' characters. On top of that, there are a couple of tiebreaker rules which take this problem out of linear greedy algorithm range.

However, we can define a greedy algorithm which finds the best sequence of characters given the position of the character that it ends with. Such an algorithm requires O(n²) time, and runs just fine for 50 characters. The first step in any algorithm is to find out which characters need to be represented. This is done by either adding all the characters to a set, or by sorting the characters and removing duplicates.

For the greedy algorithm, we choose any character in the original string which contains the last character in the set. Then we work backwards through the string, picking the first instance of the next lowest character to find. The reason you know you can pick the first instance is because it satisfies the rule that you want the string which is most tightly packed, and finding later characters first also ensures that the string is lexicographically smallest. For example, in the string "ABBC", we want the second 'B' because "A.BC" is lexicographically smaller than "AB.C". Finally, once the best for each starting position is found, we can compare the sizes and pick the string with the smallest overall size. If we start picking the initial character from the end, and move towards the front, we don't even need to worry about lexicographically comparing them. Here is some C++ code which does the trick:

string eliminated(string original)
{
  set<char> sc(original.begin(), original.end());
  sc.insert('.') // sentinel
  vector<char> chars(sc.begin(), sc.end());
  int best = 1000;
  string bstring;
  for(int i = original.length() - 1; i >= 0; i--) // starting position
  {
    string ans(original.length() - i - 1, '.');
    int next = chars.size() - 1, last;
    for(int j = i; j >= 0; j--) // current position
      if(original[j] == chars[next])
      {
        last = j;
        ans = chars[next] + ans;
        next--;
      }
      else
        ans = '.' + ans;
    if(next == 0)
    {
      if(i - last < best)
      {
        bstring = ans;
        best = i - last;
      }
    }
  }
  return bstring;
}

In addition to greedy, there are some complicated memoization algorithms which also work (my first attempt used this), or you could even use DP.

NoMo
Used as: Division 1 - Level 2:

          m!(n-m)!S
Average = ---------
              N!

where S is the sum of all the m-factors from the unique patterns of A's and B's. If we remove m!(n-m)! from the top and bottom of the fraction, it now becomes:

                S
Average = --------------
                N!
             --------
             m!(n-m)!

Which we now recognize as the choice formula. What this means is that we only have to calculate the values for the C(n, m) patterns, and this is doable without any memoization or DP. The recursive function tries adding an A, and then tries adding a B, only if the number of A's or B's doesn't exceed the maximum. Given the last character added, it can determine whether to add or subtract one from the running total. A simple recursive solution follows (in Java):

long go(int na, int nb, int last, int f)
{
  if(na < 0 || nb < 0)
    return 0;
  if(na + nb == 0)
    return f;
  return
    go(na - 1, nb, 0, f + (last == 0 ? 1 : -1)) +
    go(na, nb - 1, 1, f + (last == 1 ? 1 : -1));
}

public double momentum(String game)
{
  int na = 0, nb = 0;
  int N = game.length();
  for(int i = 0; i < N; i++)
  {
    if(game.charAt(i) == 'A')
      na++;
    else
      nb++;
  }

  double den = 1; // den = C(N, na)
  for(long i = N; i > Math.max(na, nb); i--)
    den *= i;
  for(long i = Math.min(na, nb); i > 0; i--)
    den /= i;

  int f = 0;
  for(int i = 1; i < N; i++)
    if(game.charAt(i) == game.charAt(i - 1))
      f++;
    else
      f--;

  return f - go(na, nb, -1, 1) / den;
}

Equity
Used as: Division 1 - Level 3:

Another classic delimma, how do you fairly distribute candy. Many a mother has pondered this same riddle, and yet here we create a truly fair program which can solve it. It really scares me when I see such a short description for a level 3 problem, since usually it means there is more than meets the eye to solving it. Indeed, once you see the limits, you are likely to claim impossibility. Brute force cannot possibly solve this, as for a given set of n candy bars and p people, there are O(n^3) ways of dividing them, and O((n^3)^p) ways of distributing them. However, we have one saving grace which makes a greedy solution almost look trivial -- the ways you can divide candy are all relatively prime. You'll see why this is important later, but first, let's review the greedy solution.

Looking at it logically, we first can figure out the possible "lengths" of candy we could give a single person, given an infinite amount of candy. Of course, it is possible to give the person 0, 1/3, and 1/2. If we go from 1/3, we can add 1/2 to get 5/6, and 1/3 to get 2/3. If we do everything in terms of sixths, under one bar, we can have 0/6, 2/6, 3/6, 4/6, and 5/6. At this point, we could add a whole bar to each of these to get 6/6, 8/6, 9/6, 10/6, and 11/6. To get 7/6, we can add 1/3 (2/6) to 5/6. Basically, this means it is possible to get any multiple of 1/6 except 1/6. So trivially, the lowest non-zero inequity we can get is 1/6, unless some people get nothing, in which case it is 1/3. This doesn't prove that every person who gets a certain length gets the same makeup of bars, but let's assume this is true. This leaves us with two cases. The case where not everyone gets candy is trivial -- split all bars into thirds. The second case results in an inequity of either 1/6 or 0, and is not so trivial. To think about the problem eaiser, we divide all the bars into sixths. Then, we distribute them round-robin until we run out of sixths. At this point, some people may have 1/6 more than the others.

We can define a function f(x) which will return the way to give a person x/6 bars of candy in as few pieces as possible, using the cuts allowed. The way I wrote this method is to first give as many halves as possible. If the resulting value was 1/6 away from the target, remove one half. Now, for every set of 2 halves, we can replace this with a whole bar. finally, add enough thirds to make the final value.

So the final answer is to call f(x) for each of the people you gave x/6 bars, and add that to the result. Simple multiplication, division and the mod operator makes this solution run in constant time.

But how do we know that we did not end up illegally splitting a bar into sixths in order to get the final solution? The reason it works is because all of the divisions are relatively prime. We already know that the number of sixths used adds up to the number of bars needed, and we only ever used divisions that were approved to make up each portion. Because of the relative primeness, It's impossible to split the bar in unapproved ways. For example, we cannot take 1/2 out of a bar, and also 1/3 out of the same bar, because it would leave 1/6, which we didn't count as a piece anywhere. If the problem allowed splitting into quarters, then we would need to be more careful. You could illegally take two quarter bars and a half bar from the same bar, and end up with an incorrect answer.

The complete correct code which runs in constant time follows:

int f(int t)
{
  int npieces = t / 3; // count halves
  int total = npieces * 3;
  if(total + 1 == t)
  {
    total -= 3;
    npieces--;
  }
  npieces = npieces / 2 + npieces % 2; // convert to wholes
  while(total < t) // add thirds
  {
    total += 2;
    npieces++;
  }
  return npieces;
}

public int minPieces(int n, int k)
{
  k *= 6;
  if(n * 2 > k)
    return k / 2;

  int all = k / n;
  k %= n;

  return f(all + 1) * k + f(all) * (n - k);
}