Codeforces Round #456 (Div. 2) Editorial

Note that the crystals of each color are bought independently.

One needs 2·x + y yellow and 3·z + y blue crystals. The answer therefore is max(0, 2·x + y - A) + max(0, 3·z + y - B).

If k = 1, the answer is n.

Otherwise, let's take a look at the most significant bit of answer and denote it by p (with the 0-th bit being the least possible). It must be the same as the most significant bit of n. This means the answer cannot exceed 2p + 1 - 1.

Consider the numbers 2p and 2p - 1. Obviously, they both do not exceed n. At the same time, their xor is 2p + 1 - 1. Hence, the maximum answer can always be obtained if k > 1.

The statement almost directly states the formula for the answer — it is calculated as , where f(t) is amount of enemies we can kill at t-th second. Thus, we need to learn how to calculate f(t) and find such values of t that are potential candidates for the point the maximum is achieved at.

First, let's consider the case we have no enemies with maximum health exceeding . Additionally, let .

So, how we can calculate f(t)? Let's model the process. There are three kinds of events that affect its value:

1. Some enemy has his health updated, it is now less than or equal to , thus we can kill the enemy;
2. Some enemy has his health updated, it is now greater than , thus we can't kill the enemy;
3. The enemy has regenerated enough health to become invincible again.

One can observe that the optimal answer is reached at the second exactly preceeding the events of the second and the third kind. Indeed, otherwise we can move on to the next second: the bounty is increased and f(t) doesn't decrease, thus providing us with a better answer.

What remains for us is to calculate the time when the aforementioned events occur to run scanline. The first two kinds correspond directly to the updates (and initial values — we can treat them as updates occuring at zeroth second). Let's calculate when the events of third kind would occur. Let the second t be the moment when one of the enemies' health became equal to h. Let r be the regeneration rate of the enemy. At the second he will regenerate enough health to become invincible again. One also needs take care of the case when r = 0: if there are no health updates after the enemy became killable, one can kill him at any moment and earn infinitely large amount of money. Note that one should need when did the last event of the first kind happen as updates cancel the potentially planned events of the third kind.

Now, consider the case when some enemy has maximum health less than or equal to . In that case, there is always an enemy to kill, and, since the bounty increases over time, the answer can be infinitely large.

Finally, if , the bounty stays constant and we cannot obtain the infinitely large answer. Since the bounty is constant, we are to find the maximum value of f(t) and multiply it by bounty. This is a simple task and is left as an excersise :)

Time complexity — .

Let's solve a simplified problem first. Assume we know all fishes' positions (xi, yi) (1-indexed). Denote as g(x, y) the amount of fish that is inside a scoop with lower-left angle located at (x, y). Then the expected value is equal to:

It's quite obvious that straightforward computation will result into O(n·m) time. However, we can invert the problem and calculate for each fish f(xi, yi) — how many scoops it is covered by. f is given by the following formula:

Let's get back to and transform it into:

In other words, in order to maximize the expected value we have to choose k best values among n·m possibilities.

From now on there are several approaches.

• Solution I.

  Imagine we're considering f(x0, y), i.e. with a fixed coordinate x0. Note that in this case f is y-convex, i.e. it's non-decreasing until some point, and after — non-increasing. Moreover, it always reaches its maximum at . Denote the points to the left of this one D, and to the right (inclusive) — I.

  The rest of the solution looks as follows: initially we put 2·n points into the set, two per each x-coordinate, one for D and one for I. On each step we take the point with maximum value of f and replace it with its left or right neighbour (depending on which part it was from: D means that the substitute will be to the left, I — to the right).

  Complexity: .

• Solution II.

  Let's enhance the contemplations from the previous paragraph. Notice that f is convex by both values. Then we can take ) as the starting point and launch a breadth-first search with a priority queue, erasing the most significant point according to f from the queue and checking all of its yet unvisited neighbours in a 4-connected area.

  Complexity: with a greater constant compared with solution one.

The initial idea that emerges in such kind of problems is to use binary search to determine the k-th element. Still we have to somehow answer the following query: "how many elements no greater than x satisfy the conditions?"

It's easy to see that all such numbers can be represented as p1a1·...·pnan. Denote D(G) as a set of numbers not exceeding 1018 such that all their prime divisors lie inside G.

Let N be our initial set. Sadly we cannot just generate D(N) since its size might be of the order of 8·108. Actually, the goal is to invent a way to obtain information about all elements without having to generate them explicitly.

Imagine we split N into two such sets A and B that and . According to the fact that each element of D(N) can be represented as product of some element of D(A) and some element of D(B), we can explicitly generate D(A) and D(B), then sort them and find out how many pairwise products do not exceed x in O(|D(A)| + |D(B)|) using two pointers approach. This gives in total.

The main part is to find the optimal partition. The first thought is to send the first elements to A and the rest to B. However, this is not enough; in this case the approximate size of D(A) might reach 7·106 which is way too much to pass. To speed it up we can, for example, comprise A of elements with even indexes (i.e p0, p2, ...) so that sizes of both D(A) and D(B) do not exceed 106 and the solution runs swiftly.