JOIN
 Match Editorial
SRM 202
Wednesday, July 7, 2004

Match summary

The div 1 easy/div 2 medium proved to have a couple tricky cases that weren't in the examples, which caused many submissions (including the reference solution) to fail. The div 1 medium and div 2 easy were both more reasonable, as quite a few people got the div 1 medium, and almost everyone got the div 2 easy. In division 1, Eryx won handily, beating second place LunaticFringe by almost 250 points. In third place was Zis, doing well in only his 8th competition. In division 2, Mozg beat first timer joose by about 90 points, and sun_agr rounded out the top 3.

# The Problems

LetterStrings
Used as: Division Two - Level One:
 Value 250 Submission Rate 160 / 167 (95.81%) Success Rate 157 / 160 (98.12%) High Score eleusive for 249.53 points (1 mins 14 secs) Average Score 234.57 (for 157 correct submissions)

The most straightforward way to solve this problem is with two nested loops. The outer loop iterates over the elements of the input, and the inner loop iterates over the characters in the current element. If the letter is not a '-', then increment the return value.

Hyphenated
Used as: Division Two - Level Two:
 Value 500 Submission Rate 125 / 167 (74.85%) Success Rate 26 / 125 (20.80%) High Score mariusmuja for 380.08 points (17 mins 7 secs) Average Score 272.85 (for 26 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 159 / 164 (96.95%) Success Rate 58 / 159 (36.48%) High Score cnettel for 240.45 points (5 mins 42 secs) Average Score 193.70 (for 58 correct submissions)

This problem proved to be way more difficult that expected, as even the writer and testers missed some cases. The most common problems people had were with cases like {"A","-","B"} and {"A","B"}, considering one or the other to have only a single word.

There are a few ways to solve this problem. One way to solve it is to do everything with a couple of nested loops. In this approach, you keep a count of the number of words, and a count of the total number of letters. As you are iterating over all of the characters in the input, you should increment the number of words each time you get to the end of a word (alternatively, you can increment the word count each time you get to the beginning of a word). A word ends whenever you get to a letter (character j of element i) and the next character is not a letter and the special hyphen case does not occur.

```  boolean hyphen =
j + 2 == lines[i].length() &&
lines[i].charAt(j+1) == '-' &&
i + 1 < lines.length &&
isLetter(lines[i+1].charAt(0));
boolean nextLetter =
j + 1 < lines[i].length() &&
isLetter(lines[i].charAt(j+1));
if(!nextLetter && !hyphen){
words ++;
}
```
Another way to solve this is to concatenate everything into one long string and then use some library methods to count words. A fancy way to do this is with regular expressions:
```   String all = "";
for(int i = 0; i<lines.length; i++){
all = all+lines[i]+"\n";
}
int chars = all.replaceAll("[^a-zA-Z]","").length();
int words = ("A "+all).replaceAll("[a-zA-Z]\\-\n","A").
split("[^a-zA-Z]+").length-1;
return 1.0*chars/words;
```

SimplePath
Used as: Division Two - Level Three:
 Value 1000 Submission Rate 51 / 167 (30.54%) Success Rate 8 / 51 (15.69%) High Score sun_agr for 725.27 points (19 mins 4 secs) Average Score 514.42 (for 8 correct submissions)

There are a couple ways to do this. The brute force way to do it is to move one square at a time, and put all of the locations reached in some sort of a set as you go. If you ever get to a point already in the set, then return the index of the segment that first reached that point. However, this approach is a bit risky because it requires putting a lot of points in a set, which can be relatively slow, and you might time out.

A better solution is to look at all pairs of segments and check if they intersect. If the two segments are defined by (x1,y1)-(x2,y2) and (x3,y3)-(x4,y4), where x1 < x2, and x3 < x4, and similarly for y. A simple way to tell if two segments intersect is the following:
intersect = x1 < x3 && x2 < x4 && y1 < y3 && y2 < y4
The only special case to watch for is that two segments are allowed to touch at a single point if they are consecutive. The only case in which a pair of consecutive segments count is when they are going in opposite directions. We can do this all with something like this:

```for(int i = 0; i+1<segs.length; i++){
if(direction[i] is reverse of directions[i+1]){
return i;
}
for(int j = i+2; j<segs.length; j++){
if(segs[i].touches(segs[j])){
return i;
}
}
}
return -1;
```

Histogram
Used as: Division One - Level Two:
 Value 500 Submission Rate 138 / 164 (84.15%) Success Rate 106 / 138 (76.81%) High Score antimatter for 455.30 points (9 mins 4 secs) Average Score 290.82 (for 106 correct submissions)

The first step in this problem is to figure out how many spaces to put between columns. If you wanted to, you could iterate over all spacings, until you found one that worked. However, it isn't too hard to figure it out from the title input. Between titles i and i+1 there need to be
title[i].length()/2+(title[i+1].length()-1)/2 + 1
characters - the extra 1 is for the space, and we use integer division to deal with the fact that we can't center the columns when the number of characters in a title is even. The number of characters between columns is the maximum of the number of characters required between two adjacent titles.

Once we know how many characters go between each pair of columns, we can start placing the 'X's in each column. Since the first title goes at the beginning of the last String of the return, the first column of 'X's is in column (title[0].length()+1)/2. Starting from there, we can easily figure out the rest of the columns with 'X's in them, based on the number of columns between 'X's (which we calculated earlier).

Finally, the hard part is placing the titles. We already know where the centers of the titles go though, so we can figure out where the first character of each title should go based on that. If the center of a title, t, is at character i, then the first character of t should go at i - ((t.length()-1)/2). Once you have all of the 'X's and titles placed, make sure you trim the trailing spaces, and you're set.

```public String[] draw(String[] title, int[] value){
int l = 0,h = 0,first = (title[0].length()-1)/2;
for(int i = 0; i<value.length; i++)
h = Math.max(value[i]+1,h);
char[][] ch = new char[h][1000];
String[] ret = new String[h];

for(int i = 0; i<ch.length; i++)
for(int j = 0; j<1000; j++)
ch[i][j] = ' ';

for(int i = 0;i+1<title.length;i++)
l = Math.max(l,title[i].length()/2+(title[i+1].length()-1)/2+1);

for(int i = 0; i<value.length; i++){
for(int j = 0; j<value[i]; j++){
ch[h-j-2][first+(l+1)*i] = 'X';
}
int idx = (first+(l+1)*i) - ((title[i].length()-1)/2);
for(int j = 0; j<title[i].length(); j++){
ch[h-1][idx+j] = title[i].charAt(j);
}
}

for(int i = 0; i<ret.length; i++)
ret[i] = ("A"+new String(ch[i])).trim().substring(1);
return ret;
}

```

StockSales
Used as: Division One - Level Three:
 Value 1000 Submission Rate 25 / 164 (15.24%) Success Rate 6 / 25 (24.00%) High Score Eryx for 840.24 points (12 mins 54 secs) Average Score 640.36 (for 6 correct submissions)

A bit of background in number theory was important for this one. The key to solving this was to know (or figure out) that given two integer, a and b, any multiple of gcd(a,b) can be realized by adding and subtracting some multiples of a and b. From this, it follows that given integers n1,...,nk any multiple of gcd(n1,...,nk) can be realized. So, we'll start be setting a target sum of this gcd.

Due to the tiebreaker rules, we start with the first element of the input, call this a. We then calculate the gcd of the remaining elements, call this b. We want to find the smallest integer x such that x*a+y*b == target or -x*a+y*b == target. This amounts to finding x such that (target-x*a)%b == 0 or (target+x*a)%b == 0. There is a fast way to do this, but simply starting at 0 and counting up until we find an x that works is fast enough. Once we find this x, we set the first element of the return value to x or -x. Now, we adjust the target to target + x*a or target - x*a and move on to the second element. In the next iteration, we set a to the second element of the input, and b to the gcd of the third through last elements. We continue in this way until we get to the last element of the input. When we get to the last element, we are guaranteed that target%a will be 0, so we can just set the last element of the return to target/a, and return the result.

By lbackstrom
TopCoder Member