A. Spreadsheets

Let us subtract 1 from k, now the columns are numbered from 0.

Let us first find out how many characters are there in the name of the column. To do it let us subtract powers of 26 from k, one by one, until the current power is greater than the remaining number k'.

Now the name of the column is k' in 26-based notation where characters A–Z are used as digits, prepended with leading A-s to the required length. You can either convert it using standard library function (in this case you must replace digits 0–9, A–P that will be used by the required digits), or implement a textbook algorithm of conversion to another base.

Final note: a day before the round one of the testers pointed out that CF Beta 1 Round problem B was similar to this one. After a discussion, taking into account that CF1 round was long ago, the problem is actually easier than CF1B problem, and we had no well prepared and easy enough replacement problem, we decided to keep the problem.

B. Mortal Combat

Let us count how many hit points the boss loses if attacked by the i-th hero: p_i = a_i·⌈ h_i / A⌉. Sort heroes by non-increasing of p_i and send them to attack the boss in this order.

C. A Bit Palindromic Numbers

Let us find out how to count a bit palindromic numbers among the first n positive integers. Now to solve the problem for the range from l to r we count the number of a bit palindromic numbers among first r, among the first l - 1, and subtract the latter from the former.

All numbers from 1 to 9 are a bit palindromic, so if n ≤ 9 the answer is n. Otherwise let us add 9 to the answer and count a bit palindromic numbers from 10 to n. Let us consider ten integers from 10k to 10k + 9, where k ≠ 0. Only one of them is a bit palindromic, the one that has the same first digit as k. So there is one a bit palindromic number from 10 to 19, one from 20 to 29, and so on.

Let n = 10k + d, where 0 ≤ d ≤ 9. So if d is greater or equal to the first digit of k, there are k a bit palindromic numbers from 10 to n, if it is less then the first digit of k, there are k - 1 such numbers.

D. Tree and Polynomials

Let us walk through the key ideas of the solution.

First, notice that6 you can solve problem independently for the two types of the queries. That is because operations don't depend on the values in the vertices.

Second idea is the following. Instead of storing particular values in the vertices, let us store polynomial that must be evaluated from it depth to get the value.

We cannot process queries directly, considering all vertices affected by a query, and adding the query polynomial to the polynomial in the vertex: that would take O(n²·k) which is too slow. Let us use lazy propagation then.

For the queries of the first type we need to add a polynomial q(t) to each vertex in a subtree of v. Let us just store information about that: for each vertex v let us store push1[v] that has the sum of all polynomials that affected the vertex v in queries of the first type.

Simultaneously let us store the sum of all affecting queries of the second type as a polynomial push2[v] for each vertex v.

Now denote as sum1[u] the sum of all polynomials that affect vertex u in queries of the first type.

To calculate sum1[u] let us run DFS from the root, and keep track of a polynomial cur. Entering the vertex v add push1[v] to cur, leaving v subtract it back. When we have entered the vertex u, assign sum1[u] = cur.

Similarly, denote as sum2[u] the sum of all polynomials that affect the vertex u in queries of the second type.

To calculate sum2[u] also use DFS, sum2[u] is equal to the sum of values sum2[v] for all children of u, and the value push2[u].

After we have calculated polynomials sum1[u] and sum2[u] for each vertex, evaluate them on d[u] and add the results, that is the answer for that vertex.

Time and memory are both O(nk).

E. Nice Report

Let's solve one additional problem before proceeding to the main one. You are given a sequence (a₁, a₂, ..., a_n) of some objects and somebody asks you to find out how many different objects are presented in this sequence. However, some restrictions apply to the ways you are allowed to process given data:

1. once the object a_i is read, it's lost forever: the next read will return a_i + 1 and there is no way to obtain a_i again;
2. you can only use O(1) additional memory

To solve this subproblem we will use the fact that expected value of minimum of m value uniformly distributed over segment [0;1] is 1 / (m + 1).

Consider a hash function h: A → [0;1] which transforms objects a_i to some number from [0;1]. Define M as M = min {h(a₁), h(a₂), ..., h(a_n)}. This value can be transformed to the problem solution as 1 / M - 1. However, we could run out of luck and end up in the situation where some h(a_i) is too small and spoils the answer too much. To deal with it, we can average the answer over several runs with different hash functions h₁, h₂, ..., h_k for some fixed k.

First, let's solve the case of acyclic graph. Any acyclic graph has topological sort: vertices order that respects edge directions: only edges from latter vertices to earlier ones exist. Let's label each vertex with some random number uniformly distributed over [0;1]. Topological sort existence allows us to calculate the minimal reachable label M_i for each vertex by some kind of dynamic programming. After this calculation, we can approximate the number of reachable vertices from i as 1 / M_i - 1. Again, we need to average results from several iterations to improve answer precision.

But given graph can contain cycles. To create an acyclic graph we can build the graph condensation by compressing strongly connectivity components. In the condensed graph each vertex i corresponds to w_i vertices in the original graph. To finally solve the problem we'll change vertex labeling phase a bit: a simple random label becames minimal value from w_i random value from [0;1] rolls.

A curious reader can find more information related to this problem by reading an article "Size-Estimation Framework with Applications to Transitive Closure and Reachability" located at http://cohenwang.com/edith/Papers/tcest.pdf.