IT Enthusiast — My solutions of qualification round for Facebook...

My solutions of qualification round for Facebook Hackercup 2015

Facebook Hackercup is a popular annual challenge for programmers. You need to solve some abstract programming problems (e.g. process data from input file and write them to output), advance to the next round etc. If you are lucky (and skilled in competitive programming) enough - you may eventually get a cool t-shirt or even money prize of up to $10000 (read more).

It starts with qualification round - during 3 days you should solve at least one of 3 problems to advance further. Today was the last day of 3 and I collected enough moral powers to try. I spend about a hour to solve 2 problems and here is my report in brief.

1-st problem

Speaking shortly, it was like following:

You are given a number of up to 9 digits. You are allowed to swap two digits. Print the largest and the smallest values which could be obtained by this operation.

I’ve created similar problem at my site for those who want to practice it.

With given limits - about 100 numbers - it became obvious at once that I can simply try to swap every pair of digits (which will take less than 100 iterations) and simply find minimum and maximum. So this problem is of “for implementation” kind - it requires no special algorithmic knowledge but only careful coding.

2-nd problem

It was about a person who has N items of food and for each item we know amount of carbohydrates, proteins and fats it will produce (Ci, Pi, Fi). The goal was to find out whether we can choose some items so that their total will yield exactly required amount of all three components (Cs, Ps, Fs).

I also created similar problem at my site so you can get better idea.

I.e. it was like a knapsack, but with three values for each item instead of one.

I have no idea how to solve it in general form, but I at once realized that limits are very low - no more than 20 items of food are supposed. So it became evident that I can simply try every subset of items - there are only about 2^20 i.e. one million of them. Modern computers process from 1 to 10 million iterations per second - so I have plenty of time to process data and submit solution in allowed time (6 minutes).

Conclusion

I haven’t even read the third problem since only one is required to advance to the next round. We’ll see if my solutions were correct very soon.

Now you know that at least at qualification round this challenge is very simple, so I dare to recommend you give it a try next year! I hope that my “clones” of hackercup problems will help those wanting to practice and prepare for future challenges.