Thoughts of a Psych/Code Monkey/Guitarist

Problem D - Challenging "Butts" Despite the interesting name, and somewhat tedious flavourtext, the actual underlying question was, to me, the best of the set (close to problem C). So, ignoring the darts stuff, we're given a circular track which is split radially into N >= 3 sectors, and also halved along the centre of the track, giving us 2N zones in total. We then are given numbers, and have to place them one per zone, such that the sum of differences across all zones sharing a border is a maximum. It turns out that one greedy assignment will work - start in one sector, place the highest on the outside and the lowest on the inside, move to the next sector, place the next highest on the inside and the next lowest on the outside, etc... However, why this works is not immediately obvious. From what I've heard many groups submitted this without proof of correctness - while it's an ok strategy if the proof would take some time, doing this could be costly, and ext

Problem G - DNA Chopper Ok, getting past the added flavourtext, what it turns out you have to do is this: Given a list of n numbers, continuously remove two numbers from the list and put their sum back into the list, and add the sum to your total cost - stopping once you only have one number in the list. Find the minimum cost of doing this. [Unfortunately?] It just so happens that this is a well-known and solved problem, helping in the area of compression (to see how, I'd recommend reading about Huffman Coding ). It also so happens that it's used in numerous contests (e.g. TopCoder problem ' DiskCut ' and various other ACM contests ) so anyone who's done many matches is likely to have seen this. The algorithm for solving it is pretty much the greedy approach to that mentioned above - in the 'remove two numbers step', you simply remove the two lowest numbers. This can be done quickly, and in very little code, using a priority queue (set up to remove the lowe

Problem C - Self-divisible Numbers Personally, I'd rate this as the 2nd best problem of the set [and not just because I know who wrote it =p] - why? Well, firstly, it's original, approacable, easy to understand, and not heavy on textbook algorithms. Secondly, because it seems so easy..... You're given two numbers (call them lower and upper), and instructions on how to tell if a number has a certain property ('self-divisible'), and have to output the number of self-divisible numbers between lower and upper [inclusive]. The property is easy to test, so all you do is read in lower, upper, do a for-loop between them, count the self-divisible numbers and you're done - ... Except this is the first question where bounds are important. Each of the numbers 'consists of K digits, 0 <> - so your numbers are as big as 10 400 . This means: You cannot read them as ints. No, you can't even read them in as long long (or long in Java). Yes, you can use a BigIntege

Problem B - Rating Points Exchange Apologies in advance to anyone new to programming contests, who just happened to have this problem as the second ever programming problem they see. Not that it's a bad problem - every contest seems to need at least one messy, fiddly, floating-point-error-prone problem to show that not everything is nice and discrete. Like many other of its type, the problem was basically: using floating point ratings, apply a formula we give you to them, and output the result after doing it many times. Oh, and the formula has about 10 rules. Don't worry, even the World finals has questions like this (although slightly more tricky), in a way it's a good test to see how familiar you are with your language, and pedantic you can be testing. As the algorithm is given in the problem statement, I can't say much, except re-iterate the important point: Don't use floating point numbers when you can avoid them. You'll notice that all calculations in this

Problem F - The Zits Code Kudos to the writer for merging a comic reference [even including a pic of Jeremy at the start] - with a dig at Dan Brown. Anyway, after question A this seemed the second most popular question, possibly as it tells you exactly what to do, the difficulty lies in finding a nice code-able way of doing it. The exact encryption scheme is given to you - use a square grid, spiral the message through it, pad the rest with '$', and return the grid read one row at a time. Finding the size of the grid is simple - ceil(sqrt(size of input)) for those mathematically inclined, however it's safer and easier to calculate that with a loop - as is passing with '$' and forming the output, the tricky part left then is spiralling. To see how it's done, look at the the sample 6x6 grid they give, and the path we take around it: [using (0, 0) as the top left, and (5, 5) as the bottom right, as this is where they'd go in an array) At (0, 0), facing east, t

Question A - Text Formatting The first question of the ACM is usually the warmup, and it was no exception this year. The problem's title pretty much sums up what it's about - given lots of lines, tokenize, word wrap, output the number of lines. Which also describes how to solve it: Parse the input cases, one at a time, by reading each line and splitting into tokens (good for this is Scanner in Java or stringstream in C++). Count the number of lines and the #characters on the current line. For each word, either add it to the current line (plus the two spaces) if it fits, or put it at the start of the next line. And that's it - (untested) code can be found here . Personally, I had thought more teams should have been able to solve this, however it's possibly due to some of the tricks (e.g. not adding extra two spaces at the start of a new line) and maybe because string input is usually seen as nastier to handle than numbers [it seems, anyway]. Still, an ok warmup nonethe

This weekend the South Pacific ACM regional contest was held - this is a yearly programming contest for university teams of three throughout Australia and New Zealand. Unfortunately, my having come top of Australia for the last two years, there was a rule saying we couldn't compete this year (or ever again) however instead we helped out with the submission judging. There were many teams competing, though the number of successes per team was low (as expected - this is a hard contest!), partially due to a number of regretable errors in the testing data given to us [*sigh*, it always happens, don't ask]. Also, no official solutions or data is ever made public, so instead I thought I'd present an analysis of solutions here over the next week, with explanation and code for each question starting tomorrow. For now, the problems aren't yet up, but eventually will be available here.