A couple of weekends back, we held a team programming contest for students of Scottish Universities. I had a great time taking part in contests like this back at school, and it was no less fun being on the organising side! This was an unusually light-hearted event, with each team of 5 sharing a single computer (adding a bit of time-management strategy on top) – and a USB-key submission process which added some mayhem on top of everything!!
There are a number of people to thank for making this successful: from Realtime, Alex, Andrew, Riccardo, Mathew and Gorkem helped prepare and select questions, produce test data, and write software to mark the solutions. Special thanks are due to Mathew and Gorkem for coming along and helping on the day. Michael in HR did a great job of penetrating the defences of universities and actually finding students to take part. Finally, Abertay provided a great venue, and their Information Officer David Grayland helped set up and make the whole thing run smoothly.
The questions and a short write-up are on our website, here; if you read on below, there are some solution hints – you’ve been warned!
Question 1 was supposedly there to ensure nobody got zero. Alex told me we’d chosen something too hard, and I didn’t believe him, but he was so right. Not only that, but nobody managed a full score, and even the winning team seemed to spend quite a large proportion of the time limit on this one. I think the point is that it was frustratingly fiddly to implement, even though it was trivial from a problem-solving point of view.
Question 2 was intended to be our ‘medium difficulty’ question, and being a videogame developer, we really wanted to get in some kind of spatial or geometric algorithm. There were actually quite a few possible solutions here. Firstly, you could try a naive brute-force solution:
1 for i: 0 to n - 1 2 for j: i + 1 to n - 1 3 overlap? C[i], C[j]
Clearly, that’s not going to cope with the larger allowed values of N in the time limit. There were actually a few points available for this solution, but everybody got either 0 or 100 so I guess nobody did this, at least not correctly! The next solution I expected was to sort all the circles on their X coordinate first, and then make a small modification to the previous algorithm:
1 for i: 0 to n - 1 2 for j: i + 1 to n - 1 3 if C[j].X > C[i].X + 2R 4 break 5 overlap? C[i], C[j]
This would actually have scored 75 points, because for typical input, the break statement ensures the inner loop runs few enough times. Algorithms of this type are actually pretty good for real usage in a game collision system, particularly because they are easily extended to take advantage of frame coherence: in other words, the set of potentially colliding entities in one game frame tends to be nearly the same as the set of colliding entities the next frame, and you can use algorithms that benefit from the work done last frame. Check out Sweep and Prune, for example.
So why just 75 points? Well, the problem with the previous method is that if all the circles had the same X coordinate, you’d be back to quadratic performance. So we had a test case worth 25 points like this. You could sort on Y instead, of course, but our test case was actually a cross shape, so either way you’d fail. I guess you could rotate them all a bit and then sort, but that’d be turning into slightly more work. I like the simplicity of this code; even though you’d have lost some points, I think this solution would have been a good choice given how trivial it is to implement. Of course, contestants didn’t know how many points they’d have lost in advance.
So, how to get full marks? I know of at least 2 solutions that would work. Firstly, for any kind of spatial question, it’s worth asking whether a simple spatial partitioning data structure can help – for example, a simple quadtree. You only really need two operations on the quadtree: a recursive overlap test that counts all overlaps of a given circle with existing circles in the tree, and an insertion operation:
1 t := Quadtree 2 total := 0 3 for i: 0 to n - 1 4 total += t.overlaps(C[i]) 5 t.insert(C[i])
I’m not sure of the precise running time characteristics of this, but it would have scored full points in practice. For a guaranteed O(N log N) method, there’s a divide-and-conquer solution. This is a recursive method that finds all overlaps within a set S of circles as follows:
1 find-overlaps(S): 2 if size(S) < 4 3 use brute force 4 else 5 L,R = partition(S) 6 find-overlaps(L) 7 find-overlaps(R) 8 find overlaps between L and R
We partition S in half, based on X coordinate, and recurse onto the left and right subsets. We then have to find the overlaps crossing the partition line, which involves sorting on the Y coordinate and using something similar to our brute-force-loop-with-break solution. To get the true O(N log N) performance, you have to implement in a way that involves sorting on X and Y just once, up front. It’s similar to one of the standard closest pair of points solutions, which is discussed in quite a few algorithms books.
I’m sure there are many more ways to do this question. Leave a comment at the end if you have any interesting ideas 🙂
This was the really interesting question of the lot, and definitely the difficult one! It’s a shame that the overall time limit meant nobody really had a chance to get into it. Alex did point out that a cheeky “always-print-Bob-wins” submission would have picked up 10 points, but nobody tried it!
Part 1 was actually not too hard. Since each square has 0 or 1 pebbles, viewing boards as integers via their binary representation is an obvious step. Now suppose we apply a brute-force recursive solution: to see if board position ‘b’ is winning, try all possible moves (i, j, k), and recursively ask if the resulting position is winning or not. If you can put the board in a losing position, you’re in a winning position, and if you can’t, you’re not! The recursion bottoms out when there are no moves left. Provided you memoize the results of board positions, this solution only needs to look at 2^20 board positions at most, and easily meets the time limit.
Part 2 was trivial to implement: the solution to part 1 still works! The key is that the actual number of pebbles on a square doesn’t really matter. All that matters is whether it is odd or even 😉
Part 3 was just plain mean. I won’t go into all the details, but the verification routine provided gives some big clues. You’ll want to read about the Sprague-Grundy theorem to understand it 😉
The final part of the contest consisted of this interactive question. We firstly ran all entries through a verification routine, which checked that programmes performed their I/O correctly and could run at a reasonable sustained speed over a period of time. We then ran the entries head to head on the big projector screen (the source code for the game is here – all based on this project). This was hugely entertaining, perhaps the best part of the day. Two of the programmes crashed at the end of level 1 (I’m still not sure how they passed the verifier and yet did this – to be investigated!!) leaving two teams to battle it out. One of them seemed to be shooting fairly randomly but moving quite sensibly, while the other one more or less stayed still but aimed at rocks. There were a few hilarious moments where one ship was about to be destroyed by a massive rock, and was inadvertently saved by the other team’s ship 🙂
Organising a programming contest for the first time, we were always going to make some mistakes. Hopefully we’ll get to do this again next year and improve. The biggest lessons I’m aware of were:
- Organising the venue took much, much longer than I expected. This left us really squeezed for time, because we couldn’t even advertise the event until we had this, so we didn’t have any applicants, which in turn meant I didn’t feel it was worthwhile spending time creating questions.
- Our easy question clearly should have been easier. Even though there wasn’t really any problem-solving involved, it was quite slow and fiddly to implement so it took clock time away from even the best team.
- I’d like to expand the feedback on submission to tell candidates whether or not they passed the sample test case given with the question (on the day, we just told teams whether their solution compiled or not). A number of teams were obviously new to this type of contest and struggled with the mechanics of getting the I/O correct, which wasn’t the point of the contest at all. Alternatively, we could perhaps have helped out with some sample code.
- The USB key submission process was clearly rubbish. We didn’t expect it to be good (it was all we could do with limited preparation time), but it was worse than I thought. Versioning of submissions was a nightmare (we had to get out ‘diff’ at one point and ask the team to point out which of 2 USB keys contained the latest one). We lost some of the source code afterwards and were unable to send it to that team when they asked for it. And I ended up with some malware on my laptop somehow.
- The code we used to mark the solutions was actually very good considering the time we spent on it. The main thing it lacked was the ability to archive the output of the solution, which would have been useful for auditing the results. Luckily everyone enjoyed the day and entered into the (slightly amateurish!) spirit of things, so there weren’t any disputes, although a couple of teams did express surprise at getting zero on certain questions.
- Our timetable for the day didn’t work out quite right. The contestants clearly needed a break between part 1 and part 2, and we hadn’t allowed enough time for that (we spent that time scrambling to make up for the USB key submission process). Then the time allowance for part 2 was too short. We ended up extending this a fair bit, but it would have been nice to have that arranged properly in advance so we didn’t have to call security and check that we could stay in the building!!
- We had a lot of technical problems with the interactive problem. If you look at the source code for that, you can see we used an XNA app that started up the submissions by creating child processes and redirecting their standard input and output. I thought this would be a nice way to do things: it kept the I/O consistent with part 1 of the contest, it ensured that a buggy submission couldn’t play havoc with the main game or the other entries by trampling on their memory, and it let us support multiple programming languages with no extra effort. It turned out to create its own problems though: firstly, it’s fiddly to debug code that way (having to attach the debugger after the process was started); secondly, C++ entrants using cin were able to cause an I/O deadlock when their code expected a different data type to that given (and this took a long, long time to spot!); and finally, the winning team were unable to submit a working solution of any kind because the process creation call failed every time saying their exe was a bad image (recompiling it on a variety of machines didn’t seem to help … we never got to the bottom of this).
- Having said all that, the interactive question was clearly a massive success. Watching the entries battle it out directly on the big screen was a definite high point. We’ll have to keep this for next year but leave more time for it and fix the technical issues. It would also be nice to have some kind of recording or replay so we could save off a video of the final.
- Pizza: good.
If you were there, and have any other thoughts on what was good or bad about the day, do please leave a comment below 🙂