jzzhu's blog

By jzzhu, 5 years ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it
  • +25
  • Vote: I do not like it

By jzzhu, 5 years ago, In English,

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

2.kutengine

3.rowdark

4.WJMZBMR

5.mruxim

Division 2:

1.swenyoo

2.chm517

3.iMmOrTaL1996

4.TBH

5.silly_girl

You can find editorial here.

Read more »

 
 
 
 
  • Vote: I like it
  • +225
  • Vote: I do not like it