Match Editorial

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

This is the first of what hopefully will develop into a regular review of division 2. The focus will be on "what went wrong". We hope to provide a statistical breakdown in the future, but this has not been finalised yet.

SRM 85 had 660 entrants. In the end, there were enough coders to create some 43 rooms in Division 2. As a landmark, it was the first match to allow submission in C#.

The first 2 problems on the division 2 problem slate were straightforward: if you could do the problem, there was a very high likelihood that it was correct. My room had only 2 challenges, some others had none. The top 2 rooms of the division each had only 1 solution fail. The third problem was trickier, but the problem complexity seems to have stopped submission of weak solutions.

Level One - 250:
This problem involved doing a parity check on the bits of an array of ints. The return value was a String with the character '0' representing odd parity and '1' representing even parity. Bear in mind that failures were quite rare.

Issues:
1. Failure to extract a bit!
2. Adding the wrong character! (Mea culpa)
3. Returning the string in reverse order...

Level Two - 500:
This problem was based on error correction, where each character of message was sent 3 times to increase reliability. The problem was to then extract the original message. A '*' represented a garbled input character. The rules within a block of 3 characters were (a, b and c each represent one of block[i], block[i+!] and block[i+2] at random:

1. a == b == c: return a;
2. a == b && a == '*': return c;
3. a == b && a != '*': return a;
4. a != b && a != c && b != c: return '*';

The solution was simple: search each block of 3 in each position. A variant on this was to keep a "starcount" of the number of '*' characters, to help in identifying cases. A third variant counted the number of pairs of equal characters.

It was noticeable that the solutions which failed were distinctly "uglier" than average. The counting methods were fairly unreliable.

Issues:
1. Not checking all combinations of rules 2 & 3 correctly. This tended to arise from long conditionals.
2. In problems which kept a "starcount", failure to deal with the case where only one star is found.
3. Correct checks, but in the wrong order...

Level Two - 100:
The 1000 problem doubled as the 450 in division 1. The problem was to score a multiplayer, roshambo-like game with a bunch of random rules. Valid choices were 0-5, with i+1%6 beating i+2%6. Among these were bonuses for choosing the lowest entry. Another rule said that the cumulative score for each player at the end of each round reset to 0 if it was negative.

It's hard to analyse where a lot of these problems went wrong, because of the complexity of the rules. Probably, only getting out a debugger.

Issues:
Many of the issues involved either failing to deal with the negative reset, or resetting the round score rather than the cumulative score.

Member Comments

In the article on Div2 there is a case in the Rules for level two that fails. '*aa" would drop out of the ifs. I can't figure out if these 4 rules are meant to be complete, but at the least it is confusing, and probably not the most readable way of doing the problem.

The two variants I would choose would be

1. a == '*' && b == '*'; return c;
2. a == '*' && c == '*'; return b;
3. b == '*' && c == '*'; return a;
4. a == b; return a;
5. a == c; return a;
6. b == c; return b;
return '*';

this separates the two aspects of the problem hence increasing readability or

1. a != '*' && (a==b || a==c || (b == '*' && c == '*')); return a;
2. b != '*' && (b==c || (a == '*' && c == '*')); return b;
3. b == '*' && a == '*'; return c;
4. return '*';

this gives a fall through on what will produce each result. As a more instructive way of solving the problem I would make:

3. c != '*' && (b == '*' && a == '*'); return c;

as this shows a trend of the equalities decreasing, and improves coder's ability to see patterns and analyse problems.

Other than that an excellent article that should be continued.

Shammah

He also forgot to mention the approach to sort each triple first (I've also put this into practice room 109):

string handle ( string t ) {
string r;
for( int i=0; i<t.size(); i+=3 ){
sort( &t[i], &t[i]+3 );
if( t[i+1]=='*' ) r += t[i+2];
else if( t[i+1]==t[i] || t[i+1]==t[i+2] ) r += t[i+1];
else r += '*';
}
return r;
}

Problem Set Analysis & Opinion

Div. 2 - Easy: Evil

Would be nice to also mention these two variants to count the number of bits:

int bitCount ( int n ) {
return (n>0) ? 1+bitCount( n&(n-1) ) : 0;
}

int bitCount ( int n ) {
return (n>0) ? (n&1) + bitCount( n/2 ) : 0;
}

I got the first variant from the book "The C Programming Language" by Brian Kernighan and Dennis Ritchie.