Image 01 Image 02

Fwnies’ solutions from NCPC 2013

Posted on 6th October 2013 by Sebastian
0

Yesterday the 2013 Nordic Collegiate Programming Contest took place. I have taken part in this contest the last 4 years, my two first years winning the Danish sub-contest called “DM i Programmering”.

This year I participated with Kristoffer Søholm and Morten Brøns-Pedersen, two of the members of the DIKU hacker-group Pwnies. We chose to call ourselves Fwnies, and managed to secure ourselves a 4th place in the Danish rankings, and a 20th place overall.

In connection with hacking competitions, the different teams often do write-ups explaining their solutions after the contest is over. I quite like that concept, so I thought I’d share our solutions for the NCPC problems.

Problem A: Planting Trees

This problem is rather simple, so I don’t think the code needs much explanation.

Problem B: Boiling Vegetables

It is optimal to have each vegetable cut into even-sized chunks, since this minimizes the maximal weight (and maximizes the minimal weight) of all the chunks from that vegetable. Our solution keeps a priority queue consisting of one triple (w, ow, c) for each vegetable. w is the weight of each chunk, ow is the original weight of the vegetable, and c is the number of cuts made. (So w = ow/c). We then proceed to take the heaviest chunk and add another cut to the vegetable until we achieve the desired ratio.

Problem D: Robert Hood

Our first observation was, that a straight-forward solution would be O(n2) in the number of points. At a problem size of 105, that seemed a bit high. We then observed, that the two points that are the furthest from each other must be on the convex hull of the points.[1] While this still would give a O(n2) worst-case[2], it seemed a much more reasonable set of points to compare against each other.

Problem E: Virus Replication

The gist of our solution to this problem is to find the length of the longest common prefix and suffix of the two strings. Once we have these, the minimal DNA inserted is whatever lies between the longest common prefix and suffix.

Problem F: Timebomb

This is a rather straight-forward parsing problem.

Problem G: Erase Securely

Another simple problem. The key insight here is, that you only really need to know if the number is even or odd, since two bit-flips cancel each other out.

Problem J: Dartboard

This problem basically reduces to the problem of integrating f. We integrate f on each of the rings, multiplying by the expected value for landing in that ring.[3] We spent a lot of time trying to get enough precision out of our numerical integration, which we finally managed to do on our 7th submission.

  1. [1]Implementation of the convex hull algorithm shamelessly taken from the Stanford ACM Team notebook
  2. [2]If they had decided to place all the points on a circle, the convex hull would be formed by all the original points. This, however, seemed unlikely to us.
  3. [3]Easily computed by taking the average of the scores in each square on the ring, since they have equal size.



Leave a reply...