
Match Editorial 
SRM 168Tuesday, October 21, 2003
Match summary
The points flew fast and furious... Until coders ran up against some very
difficult problems, which made this set one of the harder ones in recent times.
I had at least two people curse me for writing a difficult set and two people
praise me for it, so I don't know what the real verdict is, but here's what
happened anyways. For the most part, many of the Division 1 and Division 2
coders noticed a trick which made the Division 1 Easy/Division 2 Medium
trivial. However, the set was packed with two 1100 point problems, which
successfully stumped all but a handful of coders.
Going into the challenge phase, the top 4 coders, separated by only 1
point apiece, were WishingBone, snewman, radeye, and
SnapDragon. Following with just 11 points less than SnapDragon
was dgarthur. radeye removed himself from his position by
unsuccessfully challenging a faulty level 2 solution, and SnapDragon
propelled himself to the lead with a successful challenge. However, the
systests were unkind to most of the level 3 solutions, as only 3 out of 8
passed, leaving SnapDragon, snewman, and WishingBone as
the top 3. In Division 2, newcomer BEHiker57W dominated, getting and
keeping a raw score of 1622.77. Four of the top five were newcomers, the only
exception being bchanged, who regained a seat in division 1 for the next
SRM.
The Problems
StairClimb
Used as: Division Two  Level One:
Value

250

Submission Rate

280 / 302 (92.72%)

Success Rate

260 / 280 (92.86%)

High Score

kromm for 247.97 points (2 mins 34 secs)

Average Score

220.37 (for 260 correct submissions)

Ever jump 2 stairs at a time? How about 5? Well, if you're the person in this
problem, it is possible. The easiest way to solve this problem is to run a
simulation, taking your strides one at a time until you get to the top. Some
code which does this looks like this:
int fastest(vector<int> flights, int stridesPerStep)
{
int ret = 0;
for(int i = 0; i < flights.size(); i++)
{
while(flights[i] > 0)
{
flights[i] = stridesPerStep;
ret++;
}
ret += 2; // 2 strides to turn at the landing
}
return ret  2; // subtract 2 because no need to turn at the upper landing
}
NumberGuesser
Used as: Division Two  Level Two:
Value

500

Submission Rate

116 / 302 (38.41%)

Success Rate

88 / 116 (75.86%)

High Score

BjarkeDahlEbert for 484.37 points (5 mins 8 secs)

Average Score

304.50 (for 88 correct submissions)

Used as: Division One  Level One:
Value

250

Submission Rate

165 / 202 (81.68%)

Success Rate

144 / 165 (87.27%)

High Score

connect4 for 248.74 points (2 mins 1 secs)

Average Score

191.58 (for 144 correct submissions)

When I first encountered this trick, I immediately thought of a nontrivial
solution to this problem. I later was shown a somewhat trivial solution to
this problem, but the math to prove it is difficult, so I'll go over the
nontrivial solution first. The easiest way to think about this problem is to
do it backwards. There are two numbers x and y which have the same group of
nonzero digits. When you subtract them you get z. If you remove a digit from
z, you get the input. So if we think about getting back to z from the input,
you insert a digit. If we try all digits 1  9 at all 4 locations, there are
only 4 * 9 or 36 different possible values for z. Now, we can modify the
formula from:
y  x = z
to
y = x + z
If we loop through all the possibilities for z, and all the possibilities for
x, we can calculate the answer for y. When we have x and y, we just check to
see if they have the same group of digits. Here is some C++ code which does
the trick:
bool digitsMatch(int x, int y)
{
vector<int> ndigits(10);
while(x)
{
if(x % 10)
ndigits[x % 10]++;
x /= 10;
}
while(y)
{
if(y % 10)
ndigits[y % 10];
y /= 10;
}
for(int i = 0; i < ndigits.size(); i++)
if(ndigits[i] != 0)
return false;
return true;
}
Now, the trivial solution. If we assume there is a function DS, which calculates the digit sum of an integer, the answer is simply 9  DS(leftOver) % 9.
However, the math to prove this is certainly nontrivial. Despite this fact,
many coders either already knew this solution, guessed it correctly, or proved
it out during the challenge (BEHiker57W is one of the provers), which
lead to a lot of very quick solutions. In any case, here is a proof, compiled
from notes from BEHiker57W, AdminBrett, and lars2520
(Forgive me for the informal proof, but math proofs are not my thing):
First, we prove that any number subtracted from another number with the same
group of digits is divisible by 9. To do this we break up a number x into
its digits and powers of 10. For example, abcd becomes a*1000 + b*100 + c*10
+ d*1. If we now swap two digits, like a and b, we can achieve this by
subtracting the current terms for a and b, and adding back new terms with the
correct multipliers. So our number would now be abcd  1000a + 100a  100b +
1000b. Now, we note that any time you subtract 10^n from 10^m, you get a
multiple of 9. For example 1000  1 = 999, 1000  10 == 990, etc. So
basically, the difference between the two numbers is a multiple of 9. If you
move around all the digits, you get some number d as the difference between
the two numbers, where d is a multiple of 9.
Most people remember from early math that any number that is a multiple of 9
has digits that add up to be a multiple of 9. For those who need proof, here
it is:
We must prove that DS(n + 1) % 9 is the same as (DS(n) + 1) % 9. In order to
do this, we prove that the digit sum goes up by 1 (mod 9) every time you add 1
to a number. In the cases where the least significant digit of n is not 9,
this is trivially true, since the digit sum always goes up by 1. However, when
the least significant digit in n IS 9, then the least significant digit goes
down by 9, and the next digit goes up by 1. If we are looking for the mod 9
result, however, this is a net change of 1, since the 9 does not affect the DS
(mod 9). This is true no matter how many digits are wrapped from 9 to 0. So
for any number n, we now can prove DS(n) % 9 == n % 9. We can prove this by
reducing DS(n) to DS(n  1) + 1, DS(n  2) + 2, etc. until we get DS(n  n) +
n. Since DS(n  n) is 0, the only thing that is left is the n on the outside.
Now, to apply that to a multiple of 9, DS(9*x) % 9 == (9*x) % 9 = 0.
Therefore, the digits in a multiple of 9 must add up to a multiple of 9.
To summarize, for the trivial solution, all you need to realize is that the
difference between the two numbers is a multiple of 9, and therefore its digits
add up to a multiple of 9. To fix the 3 remaining digits into a 4 digit
multiple of 9, you just add a digit which makes the digit sum a multiple of 9.
Hence the solution 9  DS(leftOver) % 9. The reason you can't remove a 0 from
the number is because then it is unclear whether a 9 or a 0 was removed, since
the digit sum of the remaining number is still 0 % 9 in either case. That is
why 0 was not allowed to be removed when running the algorithm.
WindowWasher
Used as: Division Two  Level Three:
Value

1100

Submission Rate

46 / 302 (15.23%)

Success Rate

16 / 46 (34.78%)

High Score

BEHiker57W for 894.79 points (14 mins 18 secs)

Average Score

657.07 (for 16 correct submissions)

WindowWasher was solvable with two methods: greedy or dynamic programming.
I'll outline the greedy solution, and leave the DP solution as an exercise to
the reader. For the simple greedy solution, we can increment the time by 1
until all the windows could have been washed by the team (note that the initial
placement of the workers can be determined after the best time is determined so
that everyone in the team washes the appropriate number of columns). For
example, the following loop would work:
for(int i = 0; ; i++)
{
int columnsWashed = 0;
for(int j = 0; j < washTimes.length; j++)
columnsWashed += i / (washTimes[j] * height);
if (columnsWashed >= width)
return i;
}
However, the maximum return value is 1 billion, which is too many iterations to
run such a solution. To fix this, we note that there are many times during the
loop where the columnsWashed from one value of i is the same as
the value from the previous i. Therefore, we realize that we only need
to worry about times where a column is just barely finished. For this, we keep
a list of when each worker is going to finish his next column. Then, we only
check times where the next column gets finished. In this manner, we reduce the
outer loop to at most width iterations. The code now becomes:
int[] next = new int[washTimes.length];
int i = 0;
while(true)
{
int columnsWashed = 0;
int nexti = Integer.MAX_VALUE;
for(int j = 0; j < washTimes.length; j++)
{
columnsWashed += i / (washTimes[j] * height);
if(next[j] == i)
next[j] += washTimes[j] * height;
nexti = Math.min(nexti, next[j]);
}
if (columnsWashed >= width)
return i;
i = nexti;
}
DirectoryTree
Used as: Division One  Level Two:
Value

500

Submission Rate

107 / 202 (52.97%)

Success Rate

85 / 107 (79.44%)

High Score

snewman for 436.88 points (11 mins 7 secs)

Average Score

269.98 (for 85 correct submissions)

This was a bear for most people, but still a very straightforward problem to
solve. There were essentially 2 ways to solve it. The first is an iterative
solution which outputs the lines, and then goes back to draw the vertical bar
characters afterwards. In this solution, you first sort the strings
alphabetically. Luckily, slash comes before the alphabet in ASCII, so the sort
basically sorts the files in the order you want to output them. Then for each
element in the array, you compare the directory of the current element to the
directory of the previous element. You find out how many parent directories
they have in common, and add that many double spaces to a string. Then you add
the "+", and the directory/file name they do not have in common. Then, you
add the rest of the string by splitting it into nonslash names and adding two
more spaces for each successive name. Finally, after all is done, we work our
way backwards up the result to add the vertical bars. To do this, for each
space character in the current string, if the character below it is a vertical
bar or a '+', then change the character to a vertical bar. For a somewhat more
complex version of this, see the writer's code in the practice room.
For the more straightforward and less errorprone solution, we actually
replicate the directory structure in a tree. So each tree node has two
members: a name, and a list of nodes which are its children. To add each file
to the tree is pretty trivial, simply split the string into it's nonslash
names, and traverse the tree in the order of the names, adding directories when
necessary. A file is represented as a directory with no children. Finally, we
can either sort the names after adding them, or sort the entire string list
from the beginning as in the iterative solution. Then, outputting can be done
in order, with no need to fix up the strings afterwards with vertical bars.
Since we know which files/directories are the last in a directory, we know when
to stop printing the vertical bars for each column. See SnapDragon's
contest solution for a good example of this type.
ParkingLot
Used as: Division One  Level Three:
Value

1100

Submission Rate

8 / 202 (3.96%)

Success Rate

3 / 8 (37.50%)

High Score

WishingBone for 493.56 points (45 mins 40 secs)

Average Score

470.77 (for 3 correct submissions)

Only 3 people got this problem, and it is not hard to see why. It almost seems
impossible for each car to know where every other car is going to go, and to
only go to the spot where it knows it will take. However, there are a few
subtle nuances which make the problem solvable. First, yours is the only car
which picks a spot with the walk ahead in mind. Second, if two cars get to a
spot simultaneously, there is a well defined ordering which would not exist in
the real world. Many people fretted over how the other cars know where your
car goes since it doesn't follow the standard pattern, but we shall see that
this doesn't really matter. We solve the problem in three steps:
Step 1, figure out which spots are achievable from each car, saving how long it
took to get there, and ignoring the fact that the spots could already be taken.
In this step, we save a list of parking spots and distances for each car, and
sort them in order first by distance, then by Y position, then by X position.
This step takes at most 2500 iterations per car, since you can use a simple BFS
to find the spots. Sorting the list can take at most n lg(n), where n is the
number of spots achievable. We also do this with your car, since at this
point, there is no difference between your car and the others.
Step 2, we figure out who gets what spot. If we iterate over the cars in
increasing assigned numbers, then we do not have to worry about ties because
they will work themselves out naturally. First, we find the minimum time of
all the cars which have not yet parked at which any car will reach a parking
spot. Now, for all cars whose next spot is achieved at the minimum time who
haven't parked, see if they get that spot. We do this by iterating over the
cars in the prioritized order, and if a spot isn't taken, take it. If the car
got to a spot at the minimum time, then remove that spot from the front of its
list. The only exception is your car. For your car, you may eventually take
another spot because it is better. So we just save that location and the
distance to get to it into another list and do not mark the spot as taken. If
that spot turns out to be the best, then you will take that spot, and it
doesn't matter where another car who wanted that spot will go. If it is not
the best spot, that car will take the spot (because we didn't mark it as
taken), and we continue the search.
Step 3, we have marked all spots that your car can take with the minimum time
it takes to get there. To get the fastest distance to the entrance, we do a
BFS, but this time, we do it backwards, starting at the entrance. When a BFS
frontier node hits a parking spot that you could get to, you add the BFS
distance to the saved distance and minimize that value. Note that in this BFS,
we can travel through all squares except for the obstacle squares.
At the end, you either can or cannot get to the entrance, and if you can, you
have the minimum time it took to get there.
By
schveiguy
TopCoder Member