On Thursday afternoon I took part in my first SRM for a while. The first problem UniqueDigits had me stumped for quite some time. My initial solution look like this, but took too long, and then I couldn’t figure out how to do it in a fast way. I finally chose to use four loops for each digit and reduce the loop case when duplication was found. So my solution looked like this. Havening taken 34:29 I earned 131.17/250 points for this problem.
The second problem CompletingBrackets I understood straight away. A simple traverse the input and count the brackets, +1 for a [ and -1 for a ]. After a ] if the count is -1, add a [ to the output string, and set count to 0. At the end add the required number of ] to bring the count back to 0. So my solution was this, in a time of 5:02 for 484.83/500 points.
The third problem GroupingNumbers spent ages decided how to track the information. I decided to use a simple recursion method as the max dataset was 9 numbers. And I submitted my soultion with 1 minutes to spare. It passed all the test datasets, but felt too long on my work PC. With only one minute to spend I didn’t have the time to speed it up. It ended up failing in system test, on the fourth test case. So for 31:22 worth of work I didn’t get my 554.55 points.
One of the things that puzzles my was in the system test results it showed FAILED - Result: “” when the function returned a double. Later in the practise room I found that test runs will tell you that your solution timed out, but the system test doesn’t. While in the practice room I reviewed misof’s practice solution. It used the same block of code to calc the best (all though much more compact) but he used a lookup table to manage the group allocation. At the end of his while loop he had the lookup table iteration code. At first it looked like a permutation mixer, but when I single step through the code, it was a simple accumulator but it stop the first time the last digit was altered. This was one of the ideas I had of speeding up my code. It did not remove all duplication, but it turn the code from a n^2 to a (n-1)^2 size problem, which was enough.
<Edited 17 Jan 2006 to removed unwanted <TD> tag that messed up the formatting>