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 BigInteger in Jav...

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.

Election time is slowly approaching - which means voting. Democratic voting seems an ok way to do things, but it does have a few side-effects. While I know there's no perfect voting system , and I'm not suggesting any changes, my thoughts on why elections aren't that interesting: My vote counts for too much: I'm a debt-less uni student, not renting, working for a US company, and most likely will be not in this country in a few years, it'd be nice if I could somehow optionally weight my vote downwards, but that's not (legally) allowed. Actually, my vote doesn't matter: My local MP is Alexander Downer - it's not like he's not going to win by many votes, so who I vote for doesn't really make much difference at all. Now, the usual response from people when I say this is: " But what if everyone thought this way? ". To which my response is always that they'll think that way whether I do or not, it still doesn't make any difference. Th...

Challenge: Next time you're waiting, listening to music, near someone doing the same - set both your players to random, then swap headphones. Share the fun; do the iPod Shuffle Shuffle.

Las Vegas was Hot, Hotham was Cool! {gotta love the english language}. Anyway, something worth watching:

I'll be in LV for the next week (competing, see here for info, and there'll even be a live webcast of the final here ) then Skiing for the week after. If you want to reach me (for some strange reason) I should be checking phone / email occasionally, but apologies in advance for any delays. I'm taking a camera (odd for me, I know) so hopefully will have some pictures to put here later. Adios, until then.

Vocabulary changes with the each generation. Credit used to be something given when it was due - a reward, bestowed on those who worked hard for it. Inventors were given credit for their findings, artists recognised 'to their credit'. Times have changed however - the age of Credit is upon us, though this is not nearly as appealing as its previous meaning. No, this Credit is the opposite - 'money borrowed with the understanding that it will be repaid'. Often value given before it has been earned, the popularity behind credit cards has led to a generation who spends before earning. While making sense for once-offs (single payments with a definite deadline, slightly before the payer is guaranteed to have enough), a more common practice is to use these cards to buy everything in advance. For some reason, Credit is often treated as ' free money ' - a card with $5000 limit is seen as free $5000 that can be spent at will. Never mind the ludicrously high interest rate (...

Do you follow this religion? - Followers meet up often, many groups who follow it meet once per week, usually Friday, Saturday or Sunday. Devotees sometimes confirm their faith before sleeping each night. Friends can meet for whole weekends, wanting to practise this religion. It has spawned many songs, even dances. If your parents follow it, you're more likely to. When it's introduced into new cultures, it's believed to usually have a negative impact, and sometimes warps the minds of younger followers until they're fanatic believers. No, this isn't Christianity, or any standard belief system. It's followers are also more likely to crash a car, smoke, and take illegal drugs. It's often tied to aggressive behaviour, mindless behaviour, loss of control, yet it's still widely popular. Welcome to being drunk, the new religion. It's your choice to believe, just don't try to convert me.

Originally, I was skeptical about cameras in phones. Now I'm still skeptical, just slightly less: Hilton Sydney does everything, even swipe-card instructions From the same elevator, but a much nicer usage of physics Big Brother game - each word is an anagram of the one above, plus one letter, apparently.... Look familiar? 'tis Adelaide Uni's unique seating arrangements Finally, can you guess the animal? "Cute" doesn't count

So, recently I've been doing some work reviewing program designs, i.e. finding bugs, recommending areas for improvement. I think someone should do that to MSN: I must admit, at least they have the irony of putting them for the thinking smiley and the eyes-rolling smiley.

One of the ideas behind Survival of the fittest is that the 'stronger' members of a species will reproduce more, so their stronger genes will appear more and help assist the survival of a species. The problem is however, what happens when you reach a point that the 'strong' properties aren't useful any more. Who needs a spear thrower these days? The importance of a fit, baby-carrying body is reduced substantially when modern medicine helps you stay alive. Either way, one would think that this could then lead to development of mental, rather than physical, abilities. Unfortunately, this is not the case - while it is socially expected that people will try to look their best (c.f: Shows like the Biggest Loser), it is not expected that people will think their best. In fact - thanks to our friends drugs and alcohol, it is socially expected that people will become LESS intelligent when interacting with others. Anyway, here's a maths interpretation of some possible...

Google adsense banner at blogwatcher ::

And now for something completely different: We bring you to the apartment of Rob Stongetti, a man who claims to have created the world's first good looking myspace profile. To tell us about his acheivement, we__ Hold on a second! That's not completely different. I BEG your pardon?! You just then said that something completely different would appear. Yes? You've just witnessed a segue from a lady attacking a Starbucks with a novelty pencil, to you, a man with a command of web-page constitution, I'm sorry if my non-sequitur meter is broken. Can't you see? Both plot the tale of an eccentric protagonist, relying on the viewer's humour to provide a strange commentary on modern day capitalsim....and neither featured a red porcupine named Roger. ...Who are you? The King of comparative literature? *whooosh* DID SOMEONE CALL???? What noooooooow? You shall bow in my presence, for I, Hunter Codswallop, am the King of comparative literature. Oh my, I don't believe th...

It has happened - proof of the world's slump into mediocrity. Our university's concert has its own myspace . That's right, a concert is "in my extended network". Unfortunately, in a web like that there is no room for this blog - Sayōnara, Adios, Cya! The codemonkey will keep thinking, but no longer blog. ...and, somewhere in the distance, one of the three readers of this blog said "oh". Edit: I'll still might occasionally post poems/lyrics/short stories, as CS isn't the best subject in terms of creative output....

In the unlikely event that an observer to this blog has remained a reader after the last few entries, and the long gaps between them, I present to you the blogvella "The Tale of Thuc, the first Wraith Dragon to ever talk to herself". Prologue: In a time not unlike our own, in a land not unlike present day earth, there lived a colony much unlike our own kind. Their kind flew. Their kind are exceptionally skilled in martial warfare and live by sucking the life from their prey. Their kind are Wraith Dragons , much feared for their telepathic communication and abilities in regeneration. Among this settlement however, there is one who has recently distinguished themselves from the others - one who has a talent unknown to the others, and who because of this evades their elders, instead spending time training themselves for battles among assassins, sourcerer and other rogues in far off lands. All of this because this Wraith Dragon - born to the name Thuc but feared by her enemies...