
Match Editorial 
SRM 202Wednesday, 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("[^azAZ]","").length();
int words = ("A "+all).replaceAll("[azAZ]\\\n","A").
split("[^azAZ]+").length1;
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[hj2][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[h1][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 n_{1},...,n_{k} any multiple of gcd(n_{1},...,n_{k}) 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 (targetx*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