ZeptoLab Code Rush 2014

436A - Feed with Candy

Tutorial author: Fefer_Ivan

In this problem types of eaten candies must alternate. It means that the type of first eaten candy dictated the types of all the following candies. There are only two possible types so we should consider each type as a type of first eaten candy separatelly and then pick the most optimal. So, what if Om Nom wants to eat a candy of type t and can jump up to h? It is obvious that best option is to eat a candy with maximal mass among all the candies he can eat at this time.

436B - Om Nom and Spiders

Tutorial author: Fefer_Ivan

Let us number columns with integers from 0 from left to right and rows from 0 from top to bottom. In the cell (x, y) at the time t only four spiders can be at this cell:

Spider, which is moving left and started at (x, y + t).
Spider, which is moving right and started at (x, y - t).
Spider, which is moving up and started at (x + t, y).
Spider, which is moving down and started at (x - t, y).

Let iterate through all possible starting positions of Om Nom. Consider that he starts at column y. At time 0 all spiders are on their initial positions and Om Nom is at (0, y). There is no spiders at row 0, so at time 0 Om Nom can not meet any spiders. When Om Nom is at cell (x, y), it means that x units of time passed after the start. So to calculate the number of spiders, that Om Nom meets it is enought to check only 4 cells stated above.

436C - Dungeons and Candies

Tutorial author: Fefer_Ivan

Let's consider a weighted undirected graph with k + 1 vertex. Label the vertices with numbers from 0 to k. Vertices from 1 to k correspond to levels. For each pair of levels i and j add an edge between vertices i and j with weight equal to the cost of transferring one level as a difference from the other level. For each level i add an edge from vertex 0 to vertex i with weight equal to n·m, i.e. cost of transmitting the whole level. Each way to transmit levels defined an spanning tree of this graph. So to solve the problem, we must find a minimal spanning tree of this graph.

436D - Pudding Monsters

Tutorial author: Fefer_Ivan

This problem can be solved using dynamic programming. Let's introduce some designations: sum(l, r) — number of special cells on the segment [l, r], z_i — maximal number of covered special cells using only first i monsters, d_i — maximal number of covered special cells using only first i monsters and with i-th monster not moving.

How to calculate d_i. Let's denote i-th monster position as r. Let's iterate through all special cells to the left of i-th monster. Let's denote current special cell position as l. Let's consider the situation when this cell is the leftmost special cell in the block of monsters with i-th monster in it. So we need r - l additional monsters to get to this cell from monster i. So the value of d_i can be updated with z_{i - (r - l)} + sum(l, r).

Now, after we computed new value of d_i, we need to update some values of z_j. Let's denote i-th monster position as l. Let's iterate through all special cells to the right of i-th monster. Let's denote current special cell position as r. Let's consider the situation when this cell is the rightmost special cell in the block of monsters with i-th monster in it. So we need r - l additional monsters to get to this cell from monster i. So we can update the value z_{i + (r - l)} with d_i + sum(l + 1, r). Also, z_i should be updated with z_i - 1.

So the solution works in O(n·m) because for each of n monsters we iterate through all m special cells and for a fixed monster-cell pair all computing is done in O(1).

There are some details about monsters, that are merged at the initial state, but they are pretty easy to figure out.

436E - Cardboard Box

Tutorial author: Gerald, Nerevar

In this task you have to come with the proper greedy algorithms. Several algorithms will fit, let's describe one of them:

From that point we will consider that the levels are sorted by increasing value of b.
Let's look at some optimal solution (a set of completed levels). From levels that we completed for two stars, select the level k with the largest b[k]. It turns out that all levels that stand before k (remember, the levels are sorted) should be completed for at least one star. Otherwise, we could complete some of the previous levels instead of the level k. This won't increase the cost.
Let's fix a prefix of the first L levels and solve the problem with the assumption that each of the selected levels should be completed. Additionally, we will assume that all levels that are completed for two stars are within this prefix (as was shown before, such prefix of L levels always exists for some optimal solution).
As we will surely complete this L levels, we can imagine that we have initially completed all of the for just one star. So, we have w - L more stars to get. We can get these stars either by completing some of the levels that are outside our prefix for one star, or by completing some of the first L levels for two stars instead of one star.
It's clear that we just have to choose w - L cheapest options, which correspond to w - L smallest numbers among the following: b[i] - a[i] for i ≤ L and a[i] for i > L. Computing the sum of these smallest values can be done with a data structure like Cartesian tree or BIT.

The described solution has time completixy of O(n log n).

436F - Banners

Tutorial author: Gerald, Nerevar

Task F was the hardest one in the problemset. To better understand the solution, let's look at the task from the geometrical point of view. Imagine that people are point in the Opc plane (value of p and q are points' coordinates). Then for each line horizontal c = i we have to find such vertical line p = j that maximizes some target function. The function is computed as follows: (number of points not below c = i, multiplied by w·i) plus (number of points below c = i and not to the left of p = j, multiplied by j).

Let's move scanning line upwards (consider values c = 0, then c = 1, etc). For each value of p we will store the value d[p] — the value of the target function with the current value of c and this value of p. The problem is: if we have such array d[] for the value c, how to recompute it for the value c + 1?

Let's look at all people that will be affected by the increase of c: these are the people with b[i] = c. With the current c they are still using free version, after the increase they won't. Each of these people makes the following effect to the array: d[1] + = 1, d[2] + = 2, ..., d[b[i]] + = b[i]

Now the task can be reduced to the problem related with data structures. There are two types of queries: add the increasing arithmetical progression to the prefix of the array and retrieve the maximum value of the array. One of the way to solve it is to use sqrt-decomposition.

Let's divide all queries into groups of size sqrt(q). Let's denote the queries from the group as a sequence: p₁, p₂, ..., p_k (k = sqrt(q)). For query p_i we should perform assignments d[1] + = 1, d[2] + = 2, ..., d[p_i] + = p_i. Imagine we already preformed all the queries. Each value of new array d[] can be represented as d[i] = oldD[i] + i·coef[i], where coef[i] is the number of p_j (p_j > i).

One can notice that array coef contains at most sqrt(q) distinct values, additionally this array can be splitted into O(sqrt(q)) parts such that all elements from the same part will be the same. This is the key observation. We will divide array coef into parts. And for each part will maintain lower envelope of the lines y = d[i] + i·x. So, we will have O(sqrt(q)) lower envelopes. Each envelope will help us to get maximum value among the segment of array d[i](oldD[i] + i·coef[i]). As for each i from some segment factor coef[i] is containt we can just pick y-coordinate with x = coef[i] of corresponding lower envelope.

Described solution has time complexity of O(MAXX·sqrt(MAXX)), where MAXX is the maximum value among a[i] and b[i]. With best regards, Ivan.

Full text and comments »