### jzzhu's blog

By jzzhu, 6 years ago, , #### 450A - Jzzhu и дети

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

#### 450B - Jzzhu и последовательности

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 и шоколад / 450C - Jzzhu и шоколад

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

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

2. floor(n / x) has at most values, so we can enum it and choose the maximum x for each value.

#### 449B - Jzzhu и города / 450D - Jzzhu и города

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 и яблоки / 450E - Jzzhu и яблоки

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 и числа

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 .

Now the task is to calculate f(x) for every integer x between 0 and 220. Let f k(x) be the count of number i where Y 0&X0 = X 0 and X 1 = Y 1 (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 0 be the first part of x and X 1 be the second part of x. Let Y 0 be the first part of A i and Y 1 be the second part of A i.

We can calculate f k(x) in O(1): The problem can be solved in O(n * 2 n) now ( n = 20 in this problem).

#### 449E - Jzzhu и квадраты

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 + 2[i(L - i) - L + gcd(i, L)] = L 2 - 2iL + 2i 2 - 2L + 2gcd(i, L)

Firstly, we enum L from 1 to min(N, M). Then the task is to calculate . can be calculated by the following steps:

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

2. The count of i where gcd(i, L) = k equals to φ(L / k).

Finally, .

If there are multiple queries, we can calculate the prefix sum of , and , then we can answer each query in O(1). Tutorial of Codeforces Round #257 (Div. 1) Tutorial of Codeforces Round #257 (Div. 2)
By jzzhu, 6 years ago, , Hello everyone! Codeforces Round #257 is coming soon.

In this round, you are going to meet our friend Jzzhu. Though my id is jzzhu, the real Jzzhu isn't me, and he is a very cute boy. Now he is facing some challenges. Can you help him to solve the problems?

The problem setters are yc5-yc and me, and thank ydc, jzc, fanhqme for testing.

Many thanks to Gerald for helping to prepare the round. Also I'd like to thank MikeMirzayanov for creating such a good platform.

Have a good time with Jzzhu!

UPD

In Div. 1, scores for each problem will be 500-1000-1500-2000-2500.

In Div. 2, scores for each problem will be 500-1000-1500-2000-2500.

UPD

The contest is over. Thanks for participating.

Congrats the winners.

Division 1:

1.semiexp

3.rowdark

4.WJMZBMR

5.mruxim

Division 2:

1.swenyoo

2.chm517

4.TBH

You can find editorial here. Announcement of Codeforces Round #257 (Div. 1) Announcement of Codeforces Round #257 (Div. 2) 