Facebook Hacker Cup 2016: Round 2 problem analysis

Door Soultaker op zondag 24 januari 2016 20:40 - Reacties (1)
Categorie: -, Views: 2.329

Yesterday Round 2 of the Facebook Hacker Cup was held. This round lasted only 3 hours, and competition was fierce. Only 200 of over 2000 competitors would advance. In the end, over 177 competitors solved all problems. To advance without a perfect score, you could only fail on the easiest problem, and you'd have to submit the other solutions pretty quickly, too.

Unfortunately, under time pressure, I made a small mistake in my solution to the fourth problem, and so I won't be participating in Round 3 this year. :'( On the bright side, at least I'll get a nice T-shirt for my troubles. And you get to read another one of my write-ups!

Lees verder »

Facebook Hacker Cup 2016: Round 1 problem analysis en

By Soultaker on Sunday 17 January 2016 19:00 - Comments are closed
Category: -, Views: 3.101

The first round of the Facebook Hacker Cup has just concluded! As of writing, there are over 600 competitors that have submitted solutions for all four problems. Since only the top 500 advance (including anyone tied for 500th place) a perfect score may be a requirement, though it's also possible that a significant fraction of those solutions turns out to be wrong, as the final results have not yet been announced.

The scoreboard has been updated. 395 people scored 100 points. The minimum score necessary to advance is 85 points, and that covers the top 560.

In the context of the entire contest, Round 1 is quite unique, because it's the only round where accuracy is of critical importance and solution speed does not matter (that is, as long as you manage to solve the problems within 24 hours). Last year, my accuracy was less than perfect and I failed to advance. Hopefully, I did better this year!

Fortunally, the problems were not too difficult. Let's have a look!

Read more »

Facebook Hacker Cup 2016: Qualification Round problem analysis en

By Soultaker on Tuesday 12 January 2016 01:00 - Comments (1)
Category: Programming Contests, Views: 3.856

As I'm writing this, the Qualification Round of the Facebook Hacker Cup 2016 is about to finish. For those not in the know: the Hacker Cup is an annual algorithmic programming contest, where contestants solve mathematical puzzles by writing some code (no "hacking" in the contemporary sense involved).

Over the past few years I've been posting my analysis of the problems on my blog, and I thought I might as well continue the tradition. As usual, there are major spoilers ahead, as well as code, and some bonus questions for those that managed to solve all the problems already. So let's begin!

Read more »

Facebook Hacker Cup 2015: Qualification Round problem analysis en

By Soultaker on Monday 12 January 2015 09:50 - Comments (5)
Category: Programming Contests, Views: 7.717

Another year, another Facebook Hacker Cup, and another opportunity for smart people who know at least one programming language to put their problem solving skills to the test. As in earlier years, I will post a short analysis along with my solution for each problem, and I'll add some follow-up questions that people who have already solved the problems might find interesting.

A. Cooking the Books

Problem Statement (official link).

The qualification round starts off easily. For the first problem, we're given a number, and we're supposed to turn it into the highest/lowest value possible, by swapping just two digits. Warning: spoilers ahead!

Read more »

Fenwick trees demystified en

By Soultaker on Thursday 23 January 2014 06:00 - Comments (5)
Category: Algorithms & Data Structures, Views: 16.892

A Fenwick tree is a clever way to represent a list of numbers in an array, which allows arbitrary-length prefix sums to be calculated efficiently. (For example, the list [1,2,3,4,5] has a length-3 prefix [1,2,3] with sum 1+2+3 = 6.) This is useful in various scenarios, most notably to implement arithmetic coding, which requires dynamic tracking of cumulative frequencies of previously encountered symbols.

The data structure was introduced by Peter Fenwick in 1994, in a report titled “A new data structure for cumulative frequency tables”. Fenwick called it a Binary Indexed Tree, after the observation that the binary representation of indices determines the implicit tree structure, but the term Fenwick tree seems to be more popular today. Many articles are already available online that explain how a Fenwick tree may be implemented. Unfortunately, these articles invariably fail to explain how it was derived.

Fenwick himself shares the responsibility for the confusion, since he did not bother to discuss the history of the data structure in his publication. This has lead readers to believe there is something magical about the particular layout that is used, and caused programmers to blindly copy the source code from Fenwick's report or another source, instead of trying to understand the underlying principle first and then deriving the necessary code themselves. That's a pity, since proper understanding of a solution is necessary to extend, adapt or reconstruct it.

In this article I will try to fill this gap in public knowledge by explaining how the Fenwick tree structure and the algorithms that operate on it can be derived from scratch.

Read more »