|
Match Editorial |
Algorithm Round 1B
Tuesday, April 10, 2007
Match summary
Round 1B of the TCO07 was characterized by three very approachable problems, but all of them had pitfalls that were very easy to stumble into. With pass rates of 41%, 21% and 29%, this round was about careful coding, thinking through your algorithms, and massive opportunities during the challenge phase.tomek took the win with quick times on all 3 problems, followed by kia, who submitted the fastest 1000 pointer. Both of these leaders had a solid 5 challenges to give them a comfortable lead. However, neither could have anticipated the scare they got from gevak, whose astounding 14 successful challenges compensated for a low score on the 1000 to catapult him into 3rd place. This places him in joint 4th place on the all-time list of Challenge Success for a Single Match, a list he also holds the 1st and joint 7th place on. What is notable about his performance is that he managed to earn points from challenges on all 3 problems. Normally the great challenge phase performances are based on a corner case on a single problem, but gevak managed to break submissions of all 3 problems, and avoided too many failed challenges while he was it. krijgertje grabbed 4th spot, defying the trend by actually losing 25 points on a generally profitable challenge phase. Zhukov_Dmitry got 5th with solid submissions and 200 from challenges.
The huge number of failed solutions and successful challenges meant that only 275 people achieved a positive score and advanced to Round 2. On the flip side, 63 contestants managed to qualify on the basis of challenges alone.
The Problems
AntiPalindrome
Used as: Division One - Level One:
This problem was solvable by a very simple greedy algorithm. The difficulty lay in trying to prove to yourself that the technique would always work. I'm going to state the algorithm (which is very straightforward), and then work through the observations that convince us that such a simple process will work.
Value 250 Submission Rate 478 / 532 (89.85%) Success Rate 195 / 478 (40.79%) High Score gevak for 245.63 points (3 mins 48 secs) Average Score 179.05 (for 195 correct submissions)
To construct an anti-palindrome using the letters in s, sort s alphabetically. Then start with an empty string, and repeatedly remove the first possible letter from s and add it to the end of the new string. Always use the first letter in s, unless it would directly break our new string being an anti-palindrome. In this case, use the next available letter. If there are no alternative letters left in s, return "".
So simple! Here's the code:
for (int i = 0; i < N; i++) aCount[s[i] - 'a']++; // Count the letters
char[] cRet = new char[N];
for (int i = 0; i < N; i++) {
// Find the next available character j, which does not conflict with N-i-1
int j = 0;
while (j < 26 && (aCount[j] == 0 || cRet[N - i - 1] - 'a' == j)) j++;
if (j == 26) return "";
// Add the letter j to position i, and remove one j from our count of letters
cRet[i] = (char)('a' + j);
aCount[j]--;
}
return new string(cRet);
But why does this work? In order to prove it works, we need to evaluate 2 properties. Does it always return the alphabetically earliest anti-palindrome? And does it only return an empty string when no solution at all is possible?
The algorithm always uses the alphabetically first letter in each position, unless doing so would immediately prevent our result from being an anti-palindrome. So our return will always be alphabetically first.
The second property is harder to prove. What if our algorithm leads us into a "dead end" that could have been avoided by choosing a different letter earlier in the process? Let's look closer at the conditions under which the algorithm will return a blank string. Divide the word (of N letters long) into (N+1)/2 slots. The first slot would be indices 0 and N-1. The next slot would be indices 1 and N-2 etc, until we reach the middle slot which comprises either the middle letter or the middle 2 letters, depending if N is odd or even. Each of the (N+1)/2 slots can only hold 1 copy of a given letter, otherwise the resulting word will not be an anti-palindrome, due to a matching pair of letters existing in opposite locations. Therefore, if there are more than (N+1)/2 instances of a single letter, there won't be enough slots to distribute the letters into, and it is impossible to form an anti-palindrome.
Also, observe that the algorithm will simply add the alphabetically first (N+1)/2 characters to our new word - there are no letters in corresponding opposite positions yet - so we just add the letters alphabetically without restriction.
If our algorithm returns a blank string, the follow criteria have to be met:
- We must be attempting to add a character at index i, where i≥(N+1)/2, because the first half of our new word is unconstrained and cannot trigger the condition to return a blank string.
- We must have only 1 letter, character c left to add to our new word.
- Since we're trying to add at index i, and cannot add c, then index N-i-1 must also contain character c.
- Since the first (N+1)/2 letters of our new word are simply the alphabetically first (N+1)/2 characters of our original word, and we still have some of character c left, every position from N-i-1 to (N+1)/2-1 inclusive must be character c.
- In the first half of the word, character c occurs from indices N-i-1 to (N+1)/2-1 inclusive.
- We only have character c left, and still need to fill indices i to N-1 inclusive.
That's quite a lot of proof to go through for a 250pt problem! However, as has been discussed in many editorials already, one of the skills of a good TopCoder contestant is being able to quickly convince yourself whether a given algorithm will work without the need for formal proofs.
NavalBattle
Used as: Division One - Level Two:
The heart of this problem was trying to identify whether or not a configuration of battleships exist that is consistent with the results that Alice has given Bob. Trying to identify precisely which response from Alice was invalid was something of a distraction. Once you've written an algorithm to determine whether or not a set of responses is plausible, you can merely rerun that algorithm on the first 1,2,3...,N of Alice's responses until you find an invalid set.
Value 500 Submission Rate 214 / 532 (40.23%) Success Rate 45 / 214 (21.03%) High Score tmyklebu for 428.52 points (12 mins 1 secs) Average Score 295.40 (for 45 correct submissions)
for (int i = 0; i < shots.Length; i++) {
int[] someShots = new int[i+1];
Array.Copy(shots, someShots, i+1);
if (!bLegal(someShots, answers.Substring(0, i+1))) return i - 1;
}
return -1;
How do we determine if a set of responses is legal?
First, iterate through Alice's responses and map them to an array indexed by location, marking hits and misses. If Alice is queried about the same location twice, and gives 2 different responses, we know that her results are inconsistent, and can return immediately.
We also need to remember the restriction that at least one battleship must exist on the board. If her results do not leave shipLength connected cells that could contain a ship, she must have lied and we are done.
At this point we need to actually delve into the details of how the battleships could possibly be arranged. There's a nice recursive relationship that helps us solve this problem very easily.
The cells from i to j inclusive can be legal if either:
- i>j (we are looking at 0 cells)
or - Cell i can be empty, and the cells from i+1 to j can be legal.
or - A battleship can be placed from i to i+shipLength-1, i+shipLength can be empty, and the cells from i+shipLength+1 to j can be legal
Seven lines of code for a recursive solution with short circuit boolean logic (it returns as soon as ONE condition is true):
private bool bLegalCells(int i, int j) {
// Are there 0 cells?
if (j < i) return true;
// Can i be empty, and i+1..j is legal?
if (!bHit[i] && bLegalCells(i + 1, j)) return true;
// Can we have a ship at i, a space at i+shipLength, and the rest is legal?
if (i+shipLength-1<=j) {
for (int k = i; k < i+shipLength; k++) if (bMiss[k]) return false;
if (i + shipLength <= j && bHit[i + shipLength]) return false;
return bLegalCells(i + shipLength + 1, j);
}
// None of the conditions were satisfied
return false;
}
So, if it was such a straightforward problem, why only a 21% success rate? More than half of the competitors didn't take into account that if Alice gave contradictory information about a single square (reporting a hit and miss on the same square), then she must have lied. Many failed implementations stored an array of Alice's responses per cell, but simply overwrote her old response with her new one, losing the crucial information that Alice had cheated.
AmbiguousWatch
Used as: Division One - Level Three:
This 1000pt problem required no advanced algorithm knowledge to solve - just some logic and high school algebra. To make things clearer, whenever I refer to a clock's hand position, I will refer to it base 60, in the same way that a minute hands works. 0 is vertical upwards, 15 is horizontal to the right etc.
Value 1000 Submission Rate 112 / 532 (21.05%) Success Rate 33 / 112 (29.46%) High Score kia for 920.24 points (8 mins 30 secs) Average Score 639.36 (for 33 correct submissions)
Let's do a bit of analysis on what constitutes an "ambiguous time". Defining some terms:
H is the hour hand's position. 0≤H<60
M is the minute hand's position. 0≤H<60
If the hour hand is at position H, the minute hand's position M will be (H*12)-60k, where k is an integer, 0≤k≤11
M=12*H-60k
For an ambiguous time, since either hand could be the minute hand or the hour hand, this constraint has to hold true regardless of how we label the minute hand and hour hand M and H.
Let's call the hands' positions a and b. We know that both of the above relationships are true. So:
b=12*a-60*k a=12*b-60*n b=12*(12*b-60*n)-60*k b=144*b-60*(12*n+k) (Replace 12*n+k with just k for convenience) 143*b=60*k b=(60/143)*kWe now have a generating function to generate all hand positions which lead to ambiguous times. We can just loop from k=0 to k=143, calculate the hour and minute values for each k, and determine if it falls into the range specified by startTime and finishTime. Right?
If it's that straightforward, why a meager 29% success rate? Once again, there was one little catch on this problem that threw out the majority of competitors. There is a second condition to determine if a clock is ambiguous: The hands have to be interchangeable, and changing the hands around has to alter the time. When the hands are in the precise same location, only the first condition has been met, not the second. The hands are interchangeable, but changing them does not alter the time, hence the clock doesn't give an ambiguous time. Removing these values from the return could be done either by comparing the calculated values of hour and minute (with an epsilon, we are dealing with doubles...), or by removing every 13th generated value (you could see this pattern if you observed the generated series or did a bit more algebra).
Code follows (iStart and iEnd are ints representing the start and end times in minutes)
int iRet = 0;
for (double k = 0; k < 143; k++) {
double dHour = (k * 60 / 143) % 60;
double dMin = (dHour * 12) % 60;
if (Math.Abs(dHour - dMin) > 0.001 && dHour * 12 > iStart
&& dHour * 12 < iEnd) iRet++;
}
return iRet;
