PlaybyPlay  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^{2}) 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:
Ahh, the age old question  how much can the momentum of a football game
affect the outcome. Given the ordering of scores in a game, we can easily
calculate an mfactor for that game. The mfactor is determined by number of
sequential scores by the same team minus the number of times the scoring
shifted sides. However, we are given the difficult task of calculating the
mfactor for all permutations of the scorings. The problem claims that you
must count each individual scoring as a unique event, which means there are n!
permutations. Given that the worst case has 25 characters, that becomes 25!
permutations  way too many to count them all. However, with some
combinatorical math, we can prove that we only have to worry about C(n, m)
scoring patterns, where m is the number of scores by team A. Observe that for
any pattern of length n, which has m scores by team A, there are exactly m A
characters, and exactly (n  m) B characters. If we treat each of these scores
as unique scores, then there are exactly m! ways to arrange the A characters to
get this pattern, and exactly (n  m)! ways to arrange the B characters to get
this pattern. Therefore, we are going to form every possible pattern of A's
and B's exactly m!(nm)! times. If we factor this out of the numerator of the
average equation, we get:
m!(nm)!S
Average = 
N!
where S is the sum of all the mfactors from the unique patterns of A's and B's. If we remove m!(nm)! from the top and bottom of the fraction, it now becomes:
S
Average = 
N!

m!(nm)!
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 nonzero 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 roundrobin 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);
}
