Match Editorial

		MATCH EDITORIAL LINKS:
	Room 1 Review Archive   Rookie Review Discuss this match   Problem Set Want to write a feature?   Lessons Learned

SRM 88 was the first match of the new "multiple submissions" era. This was discussed at length in the lobby prior to the match. The sense seemed to be that multiple submissions were a double edged sword, adding to the coding phase, but possibly taking away from the challenge phase.

Statistics on multiple submissions in Div-II would be most interesting to see. Perhaps a staff member could post some data to the round tables? My feeling was that the problem slate was too demanding to allow much time for resubmission.

The problem slate in Div-II was probably more mathematical or algorithmic than we've seen recently. (Many Div-II problems have had size limits of 100-1000 on integers, for instance. The 500 in SRM 88 went up to a billion.) Recently, Div-II has had a lot of simulation problems, so some clean algorithmic problems were a refreshing change.

On the other hand, the socre seems to have been pretty low (particularly on the 250, where many rooms had > 50% systest failure.

300 (BadSpanish)

A simple problem: input is a String, output is a String, translate according to the following rules:

1. yes -> si
2. the -> el
3. words in the input which end in a consonant get an 'o' appended.
4. If the input ends with '!' or '?', then the output must start with the same character.

This problem is make for java.util.StringTokenizer. The constructor StringTokenizer(String input, String delims, boolean returnDelimiters) saves a considerable amount of coding. Once split into tokens, the rest of the problem is much less tricky.

I'm not sufficiently familiar with the C# or C++ apis to comment on the best solution there.

Problems:

1. ArrayIndexOutOfBoundsException thrown on the empty string.
2. Apparent reading error, where the 'o' is appended when the word ends in a vowel rather than a consonant.
3. Some people implemented their own tokenizer, and failed to copy data into variables when there was only one word in the input.
4. Failing to add an 'o' to the last word of input.
5. Not replaceing "the" right at the start of the input.
6. Adding an 'o' to more than one consecutive spaces.
7. Adding an 'o' to "el" after a replacement.

500 (Divisors)

The task was to take an array of up to 50 integers between 1 and 1,000,000,000 and count (once) each integer which was a factor of at least one of the inputs. Unusually for Div-II, this problem require attention to be paid to efficiency.

It turned out that the problem could be brute forced, provided some care was taken. An outline of the solution:

for val in input {
for (i=1; i<=sqrt(val); i++) {
if (val % i == 0) {
factors.add(i);
factors.add(val/i);
}
}
}
return uniqueCount( values in factors);

The java.util.HashSet class or STL hash_set was ideal for this.

The critical issue here is to only scroll up to sqrt val. (sqrt(1,000,000,000) is roughly 33,000 times 50 interations is pretty comfortable in 8 secs on a modern box.)

Problems:

1. Overcomplicating the algorithm. I messed about with prime numbers, then regenerated the factors. Why? Sunspots or brain damage: you choose...
2. Failing to pay attention to bounds. Several solutions timed out because the loop did not stop at the square root. The impact on running time is obvious after the challenge is over.
3. Failing on the test case with a single input of "1"
4. Failing on the first test case of the input. I know that many people wonder "How much testing makes sense?". Testing at least one example is a good idea, I reckon...
5. Not knowing about the Topcoder memory limits. One solution starts: "boolean facts = new boolean[500000000];"

1000 (Farmers)

Three farmers want to fence off and mark the land they own in a field. Count the amount of fencing, and the number of signs required to mark each area. The input is a String[], return is an int.

The problem also saw service as the 500 in Div-I. I believe this problem fits in a category called "flood/fill". In outline, the solution is as follows:

// setup :
int xmax, ymax, count = 0;
int areaCount = 0, areaCost = 10;
char[][] data = input;
// This is used to ensure that we don't count a boundary twice.
// An alternative is to only count internal boundaries, divide by 2
// and then add the perimeter
setFalse(boolean[][] visited);

// check each square to see if it has been visited
for (i = 0; i<xmax; i++) {
for (j = 0; j< ymax; j++) {
if (! visited[i][j]) {
// Recursively check the fences
check(data, visited, i, j, data[i][j]);
areaCount++;
}
}
return count + areaCount * areaCost;

int check(char[][] data, int x, int y, char val) {
if (x < 0 || y < 0 ||x >= xmax || y >= ymax) {
return 1;
}
if (visited[x][y]) return 0;
if (data[x][y] != val) return 1;
visited[x][y] = true;
return check(data, x+1, y, val) + check(data, x-1, y, val) +
check(data, x, y+1, val) + check(data, x, y-1, val);
}

That is far shorter than average Div-II solution. (I took inspiration from the Div-I coders, after the contest.) It's also the sort of problem which is quite easy once you've seen a solution, but is hard to find in textbooks. Note that a little global data is very useful.

I noticed that the test cases on which the problems failed tended to involve large amounts of input. This means that I may have failed to spot errors in some of the problems.

Problems:

1. Segmentation faulting
2. Not search for continuous areas correctly. This included adding to the area count every time there was a fence, or only adding to it if the square was an island of size 1x1.

Member Comments

In "Lessons Learned the Hard Way" for "Single Round Match 88" slowjoe states for the algorithm of the hard problem: "[...] but is hard to find in textbooks."

I believe that depth first search (DFS), what this basically is, can be found in about *every* textbook. The only part you have to do yourself is to see the graph in the matrix.

pochmann

sloejoe, I think you have a problem in your 1000 pt div2 answer.

You say

// Recursively check the fences
check(data, visited, i, j, data[i][j]);
areaCount++;

I say

// Recursively check the fences
count += check(data, visited, i, j, data[i][j]);
areaCount++;
}
:0 !

Shammah