JOIN
 Match Editorial
SRM 128
Monday, January 6, 2003

# The Problems

CommonDigits
Used as: Division-II, 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;
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 string-like structure, a simple loop construct that tallied digit counts, and broke ties based on left-most position would suffice.

PermutationCycles
Used as: Division-II, 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 1-based
//  and we need 0-based 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: Division-II, 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: Division-I, 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 line-joining 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 line-joins, 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 line-joins 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 "block-counter" 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: Division-I, 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: Division-I, 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 skew-decimal multiplication. A positive number written in skew-decimal 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 skew-decimal numbers:

```Integer 1 corresponds to Skew 1
Integer N corresponds to (Skew N-1) + 1
```

Incrementing a skew-decimal 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 skew-decimal 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 skew-decimal number to a long, multiply the longs together, and convert the long back to a skew-decimal value.

By brett1479
TopCoder Member