COCI in on Saturday, Bayan is on Sunday. No overlap actually.

now :D

It is weird. If using Evince on Linux it is unreadable, and if using Adobe Reader on Windows all is ok.

Personal results will be in like 30 minutes or even earlier. final standing of all contestants will be in a week or two (and solutions as well).

For problem Kamp:

It is simple to solve if there is only 1 house.

The total distance we travel is equal to twice the sum of all edges we travel minus the distance between the headquarter and the last house. Hence, for each node i, denote h_i as the furthest house from i (it will be the last house we travel to). Let u, v be 2 houses whose distance is largest among all pairs of houses. It can be proved that either h_i = u or h_i = v. At a result, we can find the maximal distance from each node i to an arbitrary house by computing the distances from u and v to all other nodes.

The remaining part is to compute the sum of all edges we use. We can first generate a set of edges and nodes that that are necessary to connect all the houses. After that, do an extra computation part for nodes which do not belong to this set.

Piramida:

First, note that the zig-zag change in direction of the letters is irrelevant. Now, the thing you need to know for a requested row of the structure is which index in the string it starts with. It should be clear that the starting index (with indexing from zero) of the n-th row is , where is the length of the string. Now that you know the start position and the length of the sequence (which is equal to the row's index) — hence you can first add up all the appearances of the desired letter in the whole string a few times, and then possibly have some more letters left over to check. These can be added up using partial sums (summed for each letter individually). A trick to consider here, which cost me 30pts, is that all partial sums won't fit in the memory requirement, hence you need to first calculate all queries containing the letter A, then all the queries containing B, and so on, reusing the same 1D array as you go.

Hope that was clear.

Oh you lucky boy :)

Here you go. Hint: the order of the students is irrelevant. We only need to know the final count of the students for each building. Let's say building i has a_i students at the end and the people want to clean up the houses for a fixed number of times k. To minimize this value use the same technique as 478B - Случайные команды.