Blog entries - Codeforces

450A - Jzzhu and Children

You can simply simulate it or find the last maximum ceil(a_i / m).

450B - Jzzhu and Sequences

We can easily find that every 6 numbers are the same. It's like {x, y, y - x, - x, - y, x - y, x, y, y - x, ...}.

449A - Jzzhu and Chocolate / 450C - Jzzhu and Chocolate

We assume that n ≤ m (if n > m, we can simply swap n and m).

If we finally cut the chocolate into x rows and y columns (1 ≤ x ≤ n, 1 ≤ y ≤ m, x + y = k + 2), we should maximize the narrowest row and maximize the narrowest column, so the answer will be floor(n / x) * floor(m / y).

There are two algorithms to find the optimal (x, y).

Notice that if x * y is smaller, the answer usually will be better. Then we can find that if k < n, the optimal (x, y) can only be {x = 1, y = k + 1} or {x = k + 1, y = 1}. If n ≤ k < m, the optimal (x, y) can only be {x = 1, y = k + 1}. If m ≤ k ≤ n + m - 2, the optimal (x, y) can only be {x = k + 2 - m, y = m}, because let t = m - n, n / (k + 2 - m) ≥ (n + t) / (k + 2 - m + t) ≥ 1.
floor(n / x) has at most $\text{[math]}$ values, so we can enum it and choose the maximum x for each value.

449B - Jzzhu and Cities / 450D - Jzzhu and Cities

We consider a train route (1, v) as an undirected deletable edge (1, v).

Let dist(u) be the shortest path between 1 and u. We add all of the edges (u, v) weighted w where dist(u) + w = dist(v) into a new directed graph.

A deletable edge (1, v) can be deleted only if it isn't in the new graph or the in-degree of v in the new graph is more than 1, because the connectivity of the new graph won't be changed after deleting these edges. Notice that you should subtract one from the in-degree of v after you delete an edge (1, v).

449C - Jzzhu and Apples / 450E - Jzzhu and Apples

Firstly, we should notice that 1 and the primes larger than N / 2 can not be matched anyway, so we ignore these numbers.

Let's consider each prime P where 2 < P ≤ N / 2. For each prime P, we find all of the numbers which are unmatched and have a divisor P. Let M be the count of those numbers we found. If M is even, then we can match those numbers perfectly. Otherwise, we throw the number 2P and the remaining numbers can be matched perfectly.

Finally, only even numbers may be unmatched and we can match them in any way.

449D - Jzzhu and Numbers

Firstly, we can use inclusion-exclusion principle in this problem. Let f(x) be the count of number i where A_i&x = x. Let g(x) be the number of 1 in the binary respresentation of x. Then the answer equals to $\text{[math]}$ .

Now the task is to calculate f(x) for every integer x between 0 and 2²⁰. Let f_k(x) be the count of number i where Y₀&X₀ = X₀ and X₁ = Y₁ (they are defined below).

We divide x and A_i into two parts, the first k binary bits and the other 20 - k binary bits. Let X₀ be the first part of x and X₁ be the second part of x. Let Y₀ be the first part of A_i and Y₁ be the second part of A_i.

We can calculate f_k(x) in O(1):

$\text{[math]}$

The problem can be solved in O(n * 2ⁿ) now (n = 20 in this problem).

449E - Jzzhu and Squares

Consider there is only one query.

Let me descripe the picture above.

A grid-square can be exactly contained by a bigger square which coincide with grid lines. Let L be the length of a side of the bigger square. Let i be the minimum distance between a vertice of the grid-square and a vertice of the bigger square. Let f(L, i) be the number of cells which are fully contained by the grid-square.

We can divide a grid-square into four right triangles and a center square. For each right triangle, the number of cells which are crossed by an edge of the triangle is L - gcd(i, L). Then, the number of cells which are fully contained by the triangle is [i(L - i) - L + gcd(i, L)] / 2.

f(L, i) = (L - 2i)² + 2[i(L - i) - L + gcd(i, L)] = L² - 2iL + 2i² - 2L + 2gcd(i, L)

Firstly, we enum L from 1 to min(N, M). Then the task is to calculate $\text{[math]}$ . $\text{[math]}$ can be calculated by the following steps:

Enum all of the divisor k of L and the task is to calculate the count of i where gcd(i, L) = k.
The count of i where gcd(i, L) = k equals to φ(L / k).

Finally, $\text{[math]}$ .

If there are multiple queries, we can calculate the prefix sum of $\text{[math]}$ , $\text{[math]}$ and $\text{[math]}$ , then we can answer each query in O(1).