Блог пользователя jzzhu

Автор jzzhu, 10 лет назад, По-английски

450A - Jzzhu and Children

You can simply simulate it or find the last maximum ceil(ai / 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).

  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 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 Ai&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 fk(x) be the count of number i where Y0&X0 = X0 and X1 = Y1 (they are defined below).

We divide x and Ai into two parts, the first k binary bits and the other 20 - k binary bits. Let X0 be the first part of x and X1 be the second part of x. Let Y0 be the first part of Ai and Y1 be the second part of Ai.

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

The problem can be solved in O(n * 2n) 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 + 2[i(L - i) - L + gcd(i, L)] = L2 - 2iL + 2i2 - 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).

Полный текст и комментарии »

Разбор задач Codeforces Round 257 (Div. 1)
Разбор задач Codeforces Round 257 (Div. 2)
  • Проголосовать: нравится
  • +25
  • Проголосовать: не нравится

Автор jzzhu, 10 лет назад, перевод, По-русски

Всем привет! Совсем скоро начнется Codeforces Round #257.

Главный герой задач раунда Jzzhu. Несмотря на то, что мой никнейм jzzhu, Jzzhu — это не я. Сегодня Jzzhu столкнется с самыми разными задачами. Сможете ли вы ему помочь?

Задачи раунда готовили gagaga5-gagaga и я. Мы благодарим ydc, jzc, fanhqme за тестирование задач раунда. Большое спасибо Gerald за помощь в подготовке раунда, а также MikeMirzayanov за создание платформы для проведения соревнований.

Недеюсь, что вам понравится проводить время с Jzzhu!

UPD

Разбалловка для первого дивизиона: 500-1000-1500-2000-2500.

Разбалловка для второго дивизиона: 500-1000-1500-2000-2500.

UPD

Соревнование завершено, всем спасибо заучастие!

Поздравляем победителей!

Победители Div. 1:

1.semiexp

2.kutengine

3.rowdark

4.YuukaKazami

5.mruxim

Победители Div. 2:

1.swenyoo

2.chm517

3.Shinka

4.TBH

5.silly_girl

Разбор задач уже опубликован.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +225
  • Проголосовать: не нравится