The contest was well balanced — scores for tasks were very close to standard scores. I hope you will find this editorial useful.

A :: k-String

Count the occurrences of each character. If any character appears a number of times not divisible by K, obviously, there is no solution. Otherwise, form the solution by first making the string B. The string B can be any string with the following property: if some character ch appears q times in the string B, the same character appears q***K** times in the given string. Now, just print that string K times.

B :: Special Offer! Super Price 999 Bourles!

The following observation will help you code the solution:

The largest number smaller than p ending with at least k nines is p - p MOD 10^k - 1 If the result turns out to be -1 , you can not reach a positive number with k or more nines. I will not explain the solution in detail — be careful when coding and have all the task statements in mind.

C :: Color Stripe

There are two cases to consider , when K=2 and when K>2. For K=2 there are only two possible solutions: the string "ABABAB..." and "BABABA..."

For both strings, simply count the number of differences between it and the given string and print a string with fewer differences.

For K>2 , decompose the string into contiguous single-colored sequences. Observe one such sequence. If it has an odd number of characters, say 2m+1, replace m characters with some other character in the following fashion:

AAAAA

becomes

ABABA

It can be observed that by changing less than m characters doesn't remove all pairs of adjacent identical characters. Similarly, for sequences of even length, say 2m characters, observe a character in the original string right after the last character of the observed sequence, and choose a character different from both. Example:

AAAAAAB

becomes

ACACACB

Again, it is sufficient and necessary to change m characters.

D :: Choosing Capital for Treeland

Arbitrarily root the tree at some vertex, say vertex 1. Now, all the edges are oriented either up (towards the root) or down (away from it). We will call upwards oriented edges red, and downwards oriented edges green. Now, with a single depth-first search, for each vertex, calculate its distance from the root (in number of edges) and the number of red edges along the path to the root. Also, count the number of red edges in the entire tree.

Now comes the interesting part: Observe that all edges outside the path from the root to vert should turn green, and those on the path should turn red.

The number of edges that need to be flipped if vert is chosen as a capital is given by:

RedEntireTree - 2*RedOnPath[vert] + RootDistance[vert]

E :: Parking Lot

Use a heap to maintain sequences of empty parking spaces as intervals. The comparison function for such intervals should return an interval which could store a car farthest from any other car, and if there is a tie, it should return the leftmost such interval. When inserting a car, pop the heap, look at the interval, place a car in the corresponding space and push two new intervals onto the heap. When removing a car, you should be able to find the two intervals which end at that car, remove them from the heap and push a new interval which forms when the two merge.