
Match Editorial 
SRM 128Monday, January 6, 2003
The Problems
CommonDigits
Used as: DivisionII, Level 1:
Value

250 
Submission Rate

180 / 219 (82.19%) 
Success Rate

132 / 180 (73.33%) 
High Score

konsept for 245.66 points

Reference implementation: brett1479 (practice room)
Implementation
As the statistics show, most people found this problem pretty doable. Coders were asked to return the digit value that occurred most frequently, breaking ties by favoring higher order digits. Java users could use code like this:
String temp = ""+inputInt;
immediately gaining access to the digits of the input integer.
C++ users could use sprintf:
char temp[20];
sprintf(temp,"%d",inputInt);
or stringstreams:
stringstream ss;
ss<<inputInt;
string temp = ss.str();
to the same effect. Once all the digits were in a stringlike structure, a simple loop construct that tallied digit counts, and broke ties based on leftmost position would suffice.
PermutationCycles
Used as: DivisionII, Level 2:
Value

550 
Submission Rate

107 / 219 (48.86%) 
Success Rate

86 / 107 (80.37%) 
High Score

gali for 529.64 points

Reference implementation: brett1479 (practice room)
Implementation
Although slightly harder than the Easy problem, many quickly figured out what was necessary to solve the Medium.
Coders were given n distinct integers between 1 and n inclusive, jumbled up in an arbitrary order.
This ordering represented a permutation of the given integers. For example:
int inputArray[] = {3,5,4,1,2}; ,
means if you had the integers {1,2,3,4,5} after applying the
given permutation you would have the
integers {3,5,4,1,2}. In other words, 1 maps to 3, 2 maps to 5, 3 maps to 4,
4 maps to 1, and 5 maps to 2.
The problem asked for how many disjoint cycles were required to represent the given permutation.
The definition of a disjoint cycle comes out of Abstract Algebra, specifically from the theory of
Permutation Groups. Basically, start with a number between 1 and n. Then figure out what it maps to.
Then figure out what that number maps to. Continue this process until you reach the number you began with.
For example, say we start with 1 in the example above. Then 1 maps to 3, 3 maps to 4, and 4 maps to 1.
This means there is a cycle denoted by (1, 3, 4). Another disjoint cycle (disjoint meaning, it doesn't
share any numbers with the previous cycle) is (2, 5). Since we have accounted for all of the 5 numbers
there is a total of 2 disjoint cycles. Java code to implement this reasoning works as follows:
int count = 0;
boolean[] marked = new boolean[inputArray.length]; //for marking used numbers
for (int i = 0; i < marked.length; i++) { //make sure to account for all numbers
if (marked[i]) continue; //we already accounted for this number
int j = i; //temp used to store the value we are starting at
count++;
while (mark[j]) {
mark[j] = true;
j = inputArray[i] 1; // '1' needed since array values are 1based
// and we need 0based indexing
}
}
return count;
In my opinion Abstract Algebra is one of the most entertaining fields in math. If you want to take
an interesting course in a university setting, or acquire a challenging hobby Algebra may be just what
you are looking for (unless you cringe at the sight of anything math related).
Indentation
Used as: DivisionII, Level 3:
Value

1100 
Submission Rate

31 / 219 (14.16%) 
Success Rate

5 / 31 (16.13%) 
High Score

coshx for 571.10 points

Used as: DivisionI, Level 2:
Value

550 
Submission Rate

93 / 119 (78.15%) 
Success Rate

35 / 93 (37.63%) 
High Score

venco for 448.47 points

Reference implementation: brett1479 (practice room)
Implementation
This problem, purely in terms of coding time, was arguably the hardest problem of the round.
Coders were asked to determine how many blocks were present in a given piece of code. To make
things harder comments denoted by '#' symbols, and linejoining operations denoted by '##' symbols
could appear just about anywhere in the input. The basic plan is to first rid the code of the annoying
comments and linejoins, and then worry about the block structuring. The former is performed by
condensing the input into one huge string (lines delimited by some unused character) and looping
through it, or looping through the characters each element of the input one at a time.
With the input void of comments and linejoins you can now check the block structure. The
important facts to realize are: 1) Blank lines should be ignored, 2) The only thing that matters on
each line is where the first significant character is located, 3) Further indented lines start new
blocks, and 4) Less indented lines close all open further indented blocks and must match the
indentation of a previously open block. A simple way to implement this "blockcounter" is to
use a stack that holds the indentations of each line, and a counter to hold the number of blocks
encountered. Process each line as follows: If the indentation value of the current line is greater
than the top of the stack, push its value on the stack and increment your totalNumBlock counter.
If it is less than the top of the stack, keep popping values off the stack until you find a value
equal to the current indentation. If you never find such a value return 1. When you are done
processing all of the lines return the value of totalNumBlock
Scytale
Used as: DivisionI, Level 1:
Value

250 
Submission Rate

117 / 119 (98.32%) 
Success Rate

114 / 117 (97.44%)

High Score

antimatter for 248.92 points

Reference implementation: brett1479 (practice room)
Implementation
Most division 1 coders raced through this problem, a number of whom submitted solutions before 3 minutes had elapsed. The gist of the problem is, n strings have been concatenated together one character at a time. To get the ith string out of the scrambled mess you simply extract all characters whose position mod n is 0. The problem gave you the scrambled string and the number of original strings (circumference in the problem) and asked for all the original strings. Java code that implements this logic is:
String[] ret = new String[n]; //Decoded strings to be returned
java.util.Arrays.fill(ret,""); //Initialize array to contain empty strings
for (int i = 0; i < codedMessage.length(); i++) //Loop over encoded string
ret[i%n]+=codedMessage.charAt(i); //Place char on the appropriate string
return ret; //Return the decoded strings
SkewDecimal
Used as: DivisionI, Level 3
:
Value

950 
Submission Rate

27 / 119 (22.69%) 
Success Rate

17 / 27 (62.96%) 
High Score

WishingBone for 694.52 points

Reference implementation: brett1479 (practice room)
Implementation
This problem didn't require a lot of code, but its underlying concept was less than obvious.
Participants were asked to implement skewdecimal multiplication. A positive number written
in skewdecimal format is composed of the digits '0''9' and 'X' such that: 1) There are no
leading zeros, and 2) Once an 'X' occurs in the number all following digits (if any) must be
zeros. The problem also stated the recurrence relation that correlates the positive integers
with the skewdecimal numbers:
Integer 1 corresponds to Skew 1
Integer N corresponds to (Skew N1) + 1
Incrementing a skewdecimal number is slightly weird. If the number contains an 'X',
incrementing the number means changing the 'X' to a '0' and incrementing the number to
its left (noting the special case that '9'+1 = 'X'). If the number doesn't contain an 'X'
increment its rightmost digit. For example, (Skew 1X0)+1=Skew 200 and (Skew 99)+1=9X .
The trick to this problem is realizing how much each digit in the skewdecimal number is worth.
Notice that you must increment a particular digit 10 times to get it to change from 0 to 'X'.
Then you must increment the entire number once to change the newly created 'X' to '0' thus
incrementing the next higher digit. Consider the following examples:
Skew Number 
Integer Value 
X 
10 
10 
11 
1X 
21 
20 
22 
X0 
110 
100 
111 
200 
222 
X00 
1110 
1000 
1111 
Noticing a pattern in the above table we can see that the digit values from right to left
(least order to highest order) are thus: 1,11,111,1111,11111,... Using this fact it is then easy to
convert each skewdecimal number to a long, multiply the longs together, and convert
the long back to a skewdecimal value.
By
brett1479
TopCoder Member