TopCoder SRM 280

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>

TopCoder – Single Round Match 263

Today’s SRM was interesting. It was at 1pm so the time was fine, except I was finding it really hard to not be distracted by the goings on at work (the clock was off).

The first problem was a simple set logic worth 250 points. I completed that in 10m39s for 220.59 points.

The second problem was also simple, but involved tracking DVDs and there cases. I spent ages muddling on paper what to track in my SortedList. After much time wastage, I settled for tracking the DVD’s and what case they where in, as the final output was to be sorted by the DVDs title. It took a while to get it working for the first two test cases. The output was arrays of string, so I did visual inspection. Mistake, as I did not cover the third example correctly. The third case covered the clause “You should return a String[] where each element describes a movie that is in a different movie’s case after all DVDs have been viewed.”

So after 42m49s I submitted my solution for 232.15 points, and once again I lost the points due to not reading the problems correctly. It least it was system test that found the problem, not other competitors. But gosh I’m getting sick of it.

I read the new article Competing tomek-style afterwards, and I think I need to note down the constraints, as this seems to be what’s letting me down.

The third problem was about optimal deque sorting and was worth 900 points. With only 20 minutes left on the clock, I thought about the problem, but did not make any progress on it. I agree with the article that solving the problem on paper first is the best idea. In the past I’ve started coding before having worked out what I’m doing, and then you have to recode things to use different containers or the likes.

Fathers Day

Well while I enjoyed my fathers day sleep-in this morning, I worked through why the example Sieve of Eratosthenes works. When for example the outer loop is at 4, you can start at 16 (4*4) due to the 2, 3 times of 4 been taken care of when the outer loop was 2 and 3. So now I’m feeling a bit silly for not seeing it at the time. But at least I can now use it, with confidence.

I also walked through how to solve the first part of the 550 point problem. Now I going to sit down and work through the string building part.

TopCoder – Single Round Match 261

Well yesterday I took 2 hours off work in the middle of the day to compete. The end result was a “why did I bother”.

The first problem was a really simple prime number search problem. You had to search a range of numbers, and for those numbers that were primes, modulo the prime with a given number. Return the lowest remainder with the highest frequency. Well I wrote the fancy Sieve of Eratosthenes and stuffed it up. Another coder in my room noticed my mistake and found an example case that it failed. At lest it took him three attempts to find it, so he got no gain of points from it.

After some investigation there appears to be a couple of ways of doing the inner loop in the sieve. (Using the same variable naming as in the linked example)

The most obvious is

for( int k = i*2; k <= n; k+= i )

and how the above example code does it, which is faster

for( int k = i*i; k <= n; k+=i )

Which computes from the square up, but when tested they give the same results (tested up to 100,000,000). But my mistake was the loop termination ended at k < n and I initlised the inner loop as int k = i; thus it looked like this.

for( int k = i; k < n; k+=i )

So now at Greig‘s recommendation I’ve written it up the correct way, and I’ll keep it handy for future competitions. Of note is that I wrote my incorrect code faster than
Mark‘s correct code, in a time of 11:21 vs. 14:44. But that’s not much of a victory.

The second problem was about binary trees and was worth 550 points. I really did not know how to solve it, and after reading the post match write-up I still do not understand it, so I’ll have to try the example code, and see how it works. So in the competition I tried implementing a permutations based solution (as this looked like what was happening) but I couldn’t get it to work in time. I even went and found a C++ example, but couldn’t get it to work ether.

To add insult to injury, I challenged another person’s 550 point solution in the challenge phase, and failed.

Final competition result, a score of -25. This put me in 298th equal out of 308 instead of 215th equal if I’d not challenged. So now I’m back in Division II with a ranking score of 1009.

TopCoder – Open Qualification Round

Well I’m not going to get into the Elimination Rounds.
I was assigned VideoEncode and GridGame.

I spent ~30 minutes of my 60 solving a problem that was really just a bit of algebra. I solved it using binary search, when I just need to rearrange the variables to get a single line piece of code. I had the feeling this was the case, but the stress of the situation I was not trusting myself to solve the algebra faster than getting the binary search working. Net time I’ll have a better indicator. The binary search was required in the AutoLoan problem due to the value been search for had a compounding affect on the result. Whereas here there was no complex relationship.

The second problem was a simple min/max tree problem. Given a 4×4 board how many of the available moves will “win” if I only play perfectly. I had missed the guarantee you win and assuming you play perfectly bits. Not that I know how to solve this. But I went down the path of how many of the moves could I win.

So now I’ll stop trying the path of logic I had been working on after the event, and workout how to solve the problem correctly.

[Some time later]

Oh my, it really was quite simple once I stopped and thought about that at each turn the two players are trying to achieve different things. For our turn we just need to find one move that we win. For the opposition move they win if they find a path we don’t win. So simple now I understand what I was trying to achieve. Other the feeling silly for not know how to program this I now feel relax I worked out how to-do it.

I’ll be ready for next time.

[Just before publishing]

Well the results are in. I came 300th out of 374 in my problem set. Most those people came 317th equal for no score. This hammered my ranking, and I’m now down to 1050. Oh well, I surely can’t get much worse than this.