
Match Editorial 
SRM 161Thursday, August 28, 2003
Match summary
SRM 161 had a familiar script. Division 1 coders rushed through the easy and
medium problems to be faced with a ferocious hard. SnapDragon, the first coder
to finish, entered the challenge round in first, only a few points ahead of
second place Tomek. In the closing minutes of the challenge round, SnapDragon
successfully challenged Tomek pushing him well into first. He had sighted a
nasty precision error that claimed most of the Division 1 submissions. Once
systests had completed all but one submission of the Division 1 hard failed. As
a result, SnapDragon beat all competitors by a large margin, solidifying his
position as the highest rated coder ever. In Division 2, Javaholic finished all
of the problems well before anyone else, but his medium failed systests allowing
Chaotica to take the top spot.
The Problems
CardCount
Used as: Division Two  Level One:
Value 
250 
Submission Rate 
152 / 162 (93.83%) 
Success Rate 
125 / 152 (82.24%) 
High Score 
duner for 246.67
points (3 mins 18 secs) 
Average Score 
206.61 (for 125 correct
submissions) 
When possible, it's nice to have the solution's structure mimic what's
actually occurring in the problem. Here we have that luxury. First set up the
variable you will be returning (String[], vector<STRING>,...). Then loop through
the deck, as a dealer would, and deal one to each player. The only extra bit of
information, is to check whether to deal another round. Java code follows:
public String[] dealHands(int numPlayers, String deck) {
String[] players = new String[numPlayers];
java.util.Arrays.fill(players,""); //null Strings are annoying
for (int left = deck.length(); left >= numPlayers; )
for (int i = 0; i < numPlayers; i++, left)
players[i]+=deck.charAt(deck.length()left);
return players;
}
An alternate way would use modulus:
public String[] dealHands(int numPlayers, String deck) {
String[] players = new String[numPlayers];
java.util.Arrays.fill(players,""); //null Strings are still annoying
for (int i = 0; i < deck.length(); i++) {
if (i%numPlayers==0 && deck.length()i<numPlayers) break;
players[i%numPlayers]+=deck.charAt(i);
}
return players;
}
StringTrain
Used as: Division Two  Level
Two:
Value 
500 
Submission Rate 
106 / 162 (65.43%) 
Success Rate 
70 / 106 (66.04%) 
High Score 
isv for 428.34 points
(12 mins 2 secs) 
Average Score 
272.22 (for 70 correct
submissions) 
In this problem, we basically just follow directions. Initially we setup a
string Train, upon which our processing will occur. Then we loop through the
remaining strings, and look for matches. The big gotcha is that all matched
prefixes/suffixes must be proper (not empty, not everything). At the end, we
remove all but the last occurrence of each letter with a single loop. Java code
follows:
public String buildTrain(String[] cars) {
String Train = cars[0]; //Setup Train
for (int index = 1; index < cars.length; index++) {
for (int startSuffix = 1; startSuffix < Train.length(); startSuffix++) {
String suffix = Train.substring(startSuffix);
if (cars[index].startsWith(suffix) && suffix.length() != cars[index].length()) {
Train += cars[index].substring(suffix.length());
break; //stop looking for suffix
}
}
}
String ret = ""; //For returning
for (int charPos = Train.length()1; charPos >= 0; charPos) {
char current = Train.charAt(charPos);
if (ret.indexOf(current)==1) ret = current+ret;
}
return Train.length()+" "+ret;
}
TennisRallies
Used as: Division Two 
Level Three:
Value 
1000 
Submission Rate 
29 / 162 (17.90%) 
Success Rate 
19 / 29 (65.52%) 
High Score 
Javaholic for 881.15
points (10 mins 44 secs) 
Average Score 
628.18 (for 19 correct
submissions) 
Used as: Division One 
Level Two:
Value

500

Submission Rate

103 / 124 (83.06%)

Success Rate

88 / 103 (85.44%)

High Score

tomek for 464.13 points (8 mins 1 secs)

Average Score

317.94 (for 88 correct submissions)

This is a classic brute force problem. We have a space of possible solutions,
namely all strings of 'c's and 'd's of a given length. We have to count all
those that satisfy certain conditions. The method I advocate, due to its
simplicity, is called generateandtest. As it sounds, we will generate all
potential strings, and test each for viability. To help explain the details of
this process, I will illustrate two distinct methods that produce the correct
results. In the first method, we use binary strings to represent possible stroke
sequences. 1 will represent 'c', and 0 will represent 'd'. This works, since
every sequence corresponds to exactly one binary string. For example,
"cdcdcccddd" will correspond to "1010111000". The reason we introduce binary
strings in the first place, is since we can loop through them in a very natural
manner. Java code follows:
public int howMany(int numLength, String[] forbidden, int allowed) {
int ret = 0; //to be returned
for (int gen = 0; gen < (1<<numLength); gen++) { //Generate 000... through 111...
char[] buffer = new char[numLength];
for (int digitMask = 1,j=0; digitMask < (1<<numLength); digitMask *= 2,j++) { //loop through bits
if ( (digitMask & gen) != 0 ) buffer[j]= 'c'; //test mask against binary string
else buffer[j]= 'd';
}
String correspond = new String(buffer);
int countForb = 0; //counts forbidden sequences
for (int charPos = 0; charPos < correspond.length(); charPos++)
for (int forbIndex = 0; forbIndex < forbidden.length; forbIndex++)
if (correspond.startsWith(forbidden[forbIndex],charPos)) countForb++;
if (countForb < allowed) ret++;
}
return ret;
}
Notice how digitMask will assume the values 1,10,100,1000,... in sequence.
Using the bitwiseand operation, digitMask allows me to test whether a given bit
is 1 in gen. After correspond has been built, I loop through looking for
substrings that match elements of forbidden. My final if statement tests for
whether the string has few enough forbidden sequences. Also, the char[] buffer
was used to avoid building a lot of Strings. Even with that slight optimization,
this method just barely runs in time (approx. 6 seconds on some test cases).
In the second method, we search through the possible strings in a
recursive fashion. Among other things, this allows us to eliminate groups of bad
strings early on. Java code follows:
public int howMany(int numLength, String[] forbidden, int allowed) {
return rec(0,numLength,"",allowed, forbidden);
}
int rec(int index, int numLength, String curr, int allowed, String[] forbidden) {
if (index == numLength) return 1; //Base case
int ret = 0; //to be returned
for (char stroke = 'c'; stroke<='d'; stroke++) {
int newAllowed = allowed;
String newCurr = curr+stroke;
for (int forbIndex = 0; forbIndex < forbidden.length; forbIndex++) {
if (newCurr.endsWith(forbidden[forbIndex])) newAllowed++;
}
if (newAllowed <= 0) continue;
ret+=rec(index+1, numLength, newCurr, newAllowed, forbidden);
}
return ret;
}
The recursive function rec tries each possible character ('c' or 'd') for
each position. It is also optimized to look for forbidden sequences at each
recursion level. This way a generated string with a bad prefix will be ignored
early on, thus accelerating the process. Understanding the recursive method may
require more thought for some. When I think about how this function works, I
consider how it behaves on a given index. Basically, when rec is called and
index is k, it considers strings that have either 'c' or 'd' in position k. The
concept lurking between the lines of code states that all strings can be divided
in to 2 groups. Strings with 'c' in position k, and strings with 'd' in position
k.
IsHomomorphism
Used as: Division One 
Level One:
Value

300

Submission Rate

119 / 124 (95.97%)

Success Rate

117 / 119 (98.32%)

High Score

tomek for 294.29 points (3 mins 58 secs)

Average Score

244.68 (for 117 correct submissions)

Once you figure out what the problem is asking, this one is really quick.
When you want to compute the results of @, the first operation, use the source
matrix. When you want to compute the results of ~, the second operation, use the
target matrix. Java code follows:
public String[] numBad(String[] source, String[] target, int[] mapping) {
ArrayList al = new ArrayList();
for (int a = 0; a < source.length; a++)
for (int b = 0; b < source.length; b++)
if (mapping[source[a].charAt(b)'0'] != target[mapping[a]].charAt(mapping[b])'0')
al.add("("+a+","+b+")");
return (String[])al.toArray(new String[0]);
}
PermutationValues
Used as: Division One 
Level Three:
Value

1000

Submission Rate

6 / 124 (4.84%)

Success Rate

1 / 6 (16.67%)

High Score

SnapDragon for 545.81 points (32 mins 14 secs)

Average Score

545.81 (for 1 correct submission)

The key to this problem is that 64bit data types really aren't that big. 20!
is the largest factorial you can fit in a signed 64bit integral type. The moral
of the story is, you only need to look at the last 20 set of numbers when
considering the permutation, all others are fixed. The first thing we do is
check whether lexPos is greater than the total number of permutations. This can
only occur if the total quantity of numbers is at most 20, and lexPos is large.
If this is the case, we compute its remainder mod (total quantity)!. Next we
factorially decompose lexPos. I'll show you an example. Let's say lexPos is 47.
We can represent it as 1321, where the place values are 4!,3!,2!, and 1!
respectively. In other words, 1321 would be evaluated as 1*4!+3*3!+2*2!+1*1!=47.
Once we have such a decomposition, we can quickly evaluate the lexPosth
permutation. For example, lets say we have the set of numbers 1,2,3,4,5. Every
time we change the first value to be one higher, we advance the lexicographic
position by 4!. This is clear when we realize that 2,1,3,4,5 will come after any
permutation that begins with 1. There are exactly 4! of these. Continuing on
with each digit, we can calculate the entire set of permuted values. If we
wanted the permutation corresponding to a lexPos of 47 we would get 2, 5, 3, 4,
1. More explicitly, we started with 1,2,3,4,5. Then:
 Took 2. We are now left with 1,3,4,5.
 Took 5. We are now left with 1,3,4.
 Took 4. We are now left with 1,4.
 Took 3. We are now left with 1.
 Took 1.
Notice how the values we took correspond to the factorial
decomposition of 47. Had the numbers been split across multiple ranges, we could
just think of them as (1,2,3,4,5...) and then convert back to their actual
values at the end. The only other trick to this problem was working with 64bit
values. Since lows[] and highs[] were 32bit values, it was easy to make a
mistake calculating a range size. For example, 'long a = highs[i]lows[i]+1'
would fail due to 32bit overflow if highs[i] and lows[i] were far enough apart.
By
brett1479
TopCoder Member