Hello! As the tasks are not uploaded on the official website of BOI2013 and I couldn't find them around the web (sorry if they are already posted), i decided to post them myself, as i was a participant in the competition itself. Unfortunately I lost the English papers for day 1 and had to translate the Bulgarian versions, please excuse my English in the day 1 statements. Also I have no scanner so i had to type myself the whole tasks in word, so I hope there aren't any mistakes :).

Day 1 tasks:

Mastermind

Old computer

Resting residence

Day 2 tasks:

Ancient cryptography [10s time limit, around 2GB memory limit]

The codebook [around 1.5s-2s time limit]

The Kebab eating contest [around 0.5~1s time limit]

Here are my solutions/ideas to the problems, do not read if you plan to solve them yourself.

Mastermind

To anyone who has played Bulls and Cows as a kid that shouldn't be a very difficult task. It is with relative scoring so you can pretty much play greedily. The solution is to keep all currently possible codes. Once you get a question, you iterate over all possible answers you can give, and check what codes actually correspond to those answers, then you give the answer that will result in the most codes remaining. The algorithm is good enough to get full score.

Old computer

The idea is simple, we want to choose a maximum set P of those pairs a[i],b[i], in some order such that a[p1]<a[p2]<a[p3]... and b[p1]<b[p2]<b[p3]. Well the simplest way to do that would be to sort the pairs in increasing order of a, and then get the Longest Increasing Subsequence in b. However we must sort them in increasing order of a AND decreasing order of b secondary, to avoid taking a few pairs with the same a.

Complexity of the algorithm is O(m*LOGm). If (as it happened for some people), this time limits in subtask 3, where m<=4,000,000 , then you can write a separate O(n^2) solution for it.

Resting residence

Biggest problem in this task is understanding the statement perfectly. So well, we can assume that every time you move through an edge, you receive "one magic point", that you can later use to rotate a pentagon without using energy (because it will be equivalent to rotating it while you were taking those "magic points"). Also you are able to do a "combo move" by rotating a neighbour and immediately moving to it. Such moves take only 1 energy and don't give you a magic point. Now how to solve the problem? Well we can "expand" our graph, creating a state [current vertex][rotation of current vertex][magic points left]. With some thinking we can realize what edges would come out of each vertex and actually construct such graph of size around N*5*N. After that we can simply use Djikstra to compute the path to N, note that it will be a good optimization to break as soon as we find the best path to N and not wait until Djikstra finishes, since the optimal path will hardly ever be too long.

Ancient cryptography

Now if you have heard of Aho–Corasick, then probably that was the first thing in your head. I had only heard the algorithm at the time of the competition and didn't know how to implement it, so I panicked a little bit thinking it might be the only solution, however fast enough I came up with a good idea that the constraints allowed.

We can observe, that in the largest subtask 5, w<=15 and in the others w is usually a relatively small number too. So we don't have many different lengths. So how to use that? Well what we can do is actually use a hash on all words in the dictionary, and put them in sets separated by their length. Then what we can do is we can iterate from w to 1 and check for every possible length if there is word with that length. We can do that by simply doing a "rolling hash" over our large string and checking if the current hash is the same as some word from the dictionary with the corresponding length after every roll.

The total complexity is O(w*x*logm). 10s should be enough.

Note: Of course, if you can implement Aho-Corasick, that would be a way better solution :)

The codebook

Now obvious solution is O(N!), however that would work only on the first two subtasks. First, note that basically what you have to find is (P-1)*B+Q-th lexicographical correct(according to their rules) permutation. Let's create a graph. The nodes will be the values of A and there will be an edge between vertices i and j, if and only if GCD(A[i],A[j])>=K. So, one can easily notice that every correct permutation corresponds to a Hamiltonian Path in our graph. Well, finding such a path is NP-complete problem which can be solved in O(2^N*N). We can do exactly that here, we will use DP with state [bitmask of used vertices][current vertex] that will give us the amount of Hamiltonian Paths that can be created from that state. It is now not that difficult to get the (P-1)*B+Q-th lexicographical path, which would be the answer to the problem.

The total complexity is O(2^N*N). Surprisingly there is a chance that recursive implementation is too slow, so iterative would be the safest way.

The Kebab eating competition

Well, as every experienced contestant would guess, we will process everything chronologically. So what we need is a structure that supports the following 2 queries :

1. Add a restaurant that serves sandwiches with A kebabs (called when restaurant is opened)
2. Return the sum of the B largest numbers (obviously optimal buying, called when a competitor can buy)

Well, it turns out that those queries aren't difficult at all. One competitor from my team solved it using AVL trees, another solved it using Treap, and i solved it using Segment Tree (simplest in my opinion). My idea was that simply a node in my Segment Tree would hold the amount of restaurants in its segment, and their sum. I process the queries the following way:

1. I increase the A-th leaf's restaurants with 1, and its sum with A, and update the path to the root.
2. I start from the root, if the right child has more restaurants than money i have, i go there recursively. Else i get the sum of the right child's tree (i buy all the sandwiches there), remove the money i had to pay (the amount of restaurants) and go recursively to the left child.

The total complexity of the algorithm is O( (n+m)*LOGmax_size ), and since size[i]<=20,000, then max_size=20,000 and the algorithm is obviously fast enough to solve the problem :)

Sorry if my solutions are unclear or there is a mistake in some of the statements, i tried my best :)