# Russian Code Cup 2017 — 3d qualification Round — Short Editorial

## 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.

## 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 10*k* to 10*k* + 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* = 10*k* + *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*^{2}·*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 *push*1[*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 *push*2[*v*] for each vertex *v*.

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

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

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

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

After we have calculated polynomials *sum*1[*u*] and *sum*2[*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*_{1}, *a*_{2}, ..., *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:

- 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; - 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*_{1}), *h*(*a*_{2}), ..., *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*_{1}, *h*_{2}, ..., *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.

## More news

- Elimination round 2017 - short editorial 11.05.2017
- Russian Code Cup — Eliminataion Round, Some News 11.05.2017