### 632A - Grandma Laura and Apples

The problem was suggested by unprost.

Consider the process from the end. The last buyer will always buy a half of an apple and get a half for free (so the last string always is *halfplus*). After that each buyer increases the number of apples twice and also maybe by one. So we simply have the binary presentation of the number of apples from the end. To calculate the answer we should simply restore that value from the end and also calculate the total money grandma should have.

С++ solution by me.

С++ solution by unprost.

Complexity: *O*(*p*).

### 632B - Alice, Bob, Two Teams

The problem was suggested by Lewin Gan Lewin.

Let's calculate the prefix sums for all numbers (and store it in array *s*1) and for numbers with letter B (and store it in array *s*2). Now we can find the sum of all numbers in any segment in *O*(1) time and the sum of numbers with letter B.

Let's iterate over prefix or suffix to flip and calculate the sum in that case by formulas: *sum*(*s*1, 0, *n* - 1) + *sum*(*s*2, 0, *i*) - 2·*sum*(*s*1, 0, *i*) for prefixes and *sum*(*s*1, 0, *n* - 1) + *sum*(*s*2, *i*, *n* - 1) - 2·*sum*(*s*1, *i*, *n* - 1) for suffixes.

C++ solution by me.

Python solution by Lewin.

Complexity: *O*(*n*).

### 632F - Magic Matrix

The problem was suggested by Lewin Gan Lewin. The solution and proof also belongs to him.

Consider the undirected complete graph with *n* nodes, with an edge between nodes *i*, *j* with cost *a*_{ij}. Let *B*_{ij} denote the minimum possible value of the max edge of a path from *i* to *j*. We know that *a*_{ij} ≥ *B*_{ij} by definition.

If the matrix is magic, we can choose arbitrary *k*_{1}, *k*_{2}, ..., *k*_{m} such that *a*_{ij} ≤ *max*(*a*_{i, k1}, *a*_{k1, k2}, ..., *a*_{km, j}) by repeating invocations of the inequality given. Also, you can show that if this inequality is satisfied, then the matrix is magic (by choosing an *m* = 1 and *k*_{1} arbitrary).

So, this shows that the matrix is magic if and only if *a*_{ij} ≤ *B*_{ij}. Thus, combining with *a*_{ij} ≥ *B*_{ij}, we have *a*_{ij} = *B*_{ij}.

We need a fast way to compute *B*_{ij} for all pairs *i*, *j*. This can be computed as the MST, as the path in the MST minimizes the max edge between all pairs of nodes. So, the algorithm works as follows. First, find the MST on the complete graph. Then, the matrix is magic if and only if the max edge on the path between *i*, *j* in the MST is exactly equal to *a*_{i, j}. Also you shouldn't forget to check symmetry of the matrix and diagonal for zeros.

P.S.: Unfortunately we couldn't increase the value *n* in this problem: the tests already had the size about 67MB and they couldn't be given with generator. So most of the users who solved this problem uses *bitset*-s. The complexity of their solution is , where *b* = 32 or *b* = 64.

C++ solution, binary lifts by me.

Java solution by Lewin.

Complexity: *O*(*n*^{2}*logn*) or *O*(*n*^{2}).