ashmelev's blog

By ashmelev, 2 years ago, In Russian,

Всем привет! Может быть, эта тема уже обсуждалась, но по запросу "random" ничего похожего на Codeforces не нашел.

Предыстория. Хотели с Сашей (adrozdova) изучить декартово дерево. Для инициализации приоритетов рекомендуется использовать случайные числа, чтобы высота дерева не была очень большой. Соответственно, надо эти числа как-то получить. Я совсем не разбираюсь в структурах данных, поэтому не задумывался, насколько плохо будет дереву (и будет ли), если приоритеты нескольких вершин будут одинаковыми. Поэтому на всякий случай хотелось сделать их попарно различными (чего не гарантирует простое использование rand() при создании очередной вершины). Предложил следующий, "надежный" и "проверенный" метод — создать массив из N чисел, инициализировать его числами от 0 до (N-1) соответственно, применить к нему random_shuffle — и мы получим N различных ключей в случайном порядке.

История. Саша стала сдавать задачи и на практике оказалось, что в нескольких задачах такой подход достаточно стабильно приводит к вердикту Time Limit Exceeded, в то время как простейшая инициализация pr=rand() получала Accepted. Стало очень интересно, почему так происходит, да и вообще STL не склонен быть причиной каких-либо ошибок. После несложных исследований оказалось, что (возможно, не это причина TLE, но тем не менее) random_shuffle перемешивает массив не совсем случайным образом.

Read more »

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

By ashmelev, 5 years ago, translation, In English,

Problem 175F - Gnomes of Might and Magic

Construct the graph with vertices corresponding to castles and edges to roads. Note, that a degree of each graph vertex does not exceed 4, so the amount of edges does not exceed E <= 2 * N.

In order to solve the problem let's find out how we can handle each query with time O(_log_(_N_)). Consider the query to find amount of gnomes destroyed by the Mission of Death. Assume that the edge weight is the amount of gnomes on the appropriate road. We must find the shortest path between two vertices and among them the path with the smallest amount of edges. So, the way is described by two numbers — G and R — amount of gnomes and edges (for now we do not consider lexicographical minimality). One edge between vertex u and v is described by (_C_(_u_,_v_), 1), where C(_u_,_v_) — amount of gnomes on the edge (_u_,_v_). Consider two vertices s and t. We want to find the path between them. The shortest path between them can be one of the following :

  • the path along the Evil Shortcut, if both vertices are on the same Shortcut
  • the path s -> g1 -> g2 -> t, where g1 и g2 — vertices on the Good Path and g1 and s are on the same Shortcut, g2 and t are on the same Shortcut (some of these 4 vertices can be identical).

So, it is necessary to determine quickly the shortest path between vertices e1 and e2 along the Evil Shortcut and between vertices g1 and g2 along the Good Path. In order to find distance between vertices along the Evil Shortcut construct for each Evil Shortcut the segment tree etree[i], which can be used to update and get the sum on the segment. For each vertex let's store the number of Evil Shortcut it belongs to and it index number on that Shortcut (it is necessary to consider cases with vertices of the Good Path, because they belong to two Shortcuts). So, the distance between two vertices of one Shortcut is the sum of edges weights of the approproate segment tree with boundaries equal to indexes of considered vertices. Similarly, construct the segment tree gtree for Good Path, by cutting it in the first vertex (for paths where it was inner vertex we will do two queries). For each pair of adjacent vertices of the Good Path we will store the minimum of two distances: distance along the edge of the Good Path or the distance along the Evil Shortcut. So for each two vertices of the Good Path the corresponding query to the segment tree returns the length (a pair of numbers) of the shortest path between two arbitrary vertices. Such a data structure allows to find the shortest path between two arbitrary vertices of the Good Path or one Evil Shortcut in time O(_log_(_N_)). It is necessary to update appropriate element of the tree with value (_0_, 1) for each pair of adjacent vertices of the Good Path initially.

Now consider the query for addition of one gnome to the edge. In order to handle this query quickly it is necessary to store amount of gnomes gsum[i] along each road of the Good Path and total number of gnomes esum[i] along each Evil Shortcut. If the gnome stands on the edge i of the Good Path, then increase gsum[i] by 1. Similarly if the gnome stands on the edge i of the Evil Shortcut, then increase esum[i] by 1 and update the appropriate value in the segment tree etree[i]. It is necessary to put new shortest path between corresponding adjacent vertices into the segment tree gtree after any of these actions because it may have changed. Note, that after removal of gnomes from the edge we can do opposite operations with the same asymptotics. So, the query for updating amount of gnomes on the edge can be handled in time O(_log_(_N_)).

Now let's figure out how we can find the shortest path between two arbitrary vertices s and t. Construct the vector of the Good Path vertices sg those we can reach from s along the edges of the Evil Shortcut which it belongs to (there will be one or two vertices in the sg ). Similarly, the vector tg contains the vertices of the Good Path those we can reach from t along the edges of the Evil Shortcut. Consider the union of vectors tsg = sg + tg. For each vertex u of the uninon let's find the vertex v1 which is the first one among vertices tsg on the path from u if we move along the edges of Good Path in the order of indexes increasing (i.e. in the order the vertices are given in the input data). Similarly, v2 is the first vertex on the opposite direction. Add to the adjacenty list of the vertex u vertices v1 and v2 with distances to them. Also, find edges (distances along the Evil Shortcuts) from s to the vertices of vector sg, and from vertices of the tg to the vertex t. If vertices s and t are on the same Evil Shortcut (and none of them is on the Good Path), then add one more direct edge from s to t, corresponding to the path along the Evil Shortcut. So we have constructed the graph which consists of not more than 6 vertices and no more than 13 edges. Start the Deijkstra algorithm on that graph to find shortest path from s to t. Note, that paths of the initial graph corresponding to edges of the new graph do not intersect in inner vertices (except, probably, a direct edge from s to t). In order to find lexicographically minimal path it is necessary to know the first inner vertex on the path corresponding to one of the edges. So we can, for example, add one more option to each path of the new graph — the vector of indexes of first vertices of the initial graph when moving along edges of a new graph. In this case 3 options (amount of gnomes, amount of edges and the vector of indexes) uniquely determines the optimal path of the Death Mission.

Now it is necessary to print the answer and find out how to handle gnome destruction on the path. Restore vertices on the optimal path. The edge between each pair of adjacent vertices is the path along the Evil Shortcut or the path between two vertices of the Good Path. In order to find gnomes on the Evil Shortcut consider the multiset eset[i] containing indexes of edges with gnomes of that Shortcut for each Evil Shortcut. Then after adding a gnome to the edge it is necessary to add the gnome index to the multiset of the Shortcut. Now all destructions of gnomes from the Evil Shortcut i, between edges l and r, can be handled by searching of iterator of the first gnome, using eset[i]._lower_bound_(_l_) and iteration, saving obtained indexes of gnomes into the list, until the value will not exceed r. After that it is necessary to remove all gnomes in the list using the algorithm described above (similarly to addition). In order to handle paths between two vertices of the Good Path, consider set gset with indexes of vertices of the Good Path that there is no path without gnomes between two adjacent vertices corresponding to indexes. After each set updating (adding/removal of the gnome) it is necessary to add the check: if the minimum distance (corresponding to the value in the segment tree gtree) is 0 (by the amount of gnomes), then it is necessary to remove appropriate index in the gset, in the opposite case it is necessary to add the index. After invocation of similar procedure (invoke gset._lower_bound_ and iterate required amount of times) we will get the list of vertices indexes going through each one we will have to destroy at least one gnome to the path to the next vertex of the Good Path (obvious, that pairs of vertices between those exists a path without gnomes should not be considered because the Death Mission will go along it without destruction of gnomes). Consider index i from this list. If for the correspondent vertex the optimal path to the next vertex of the Good Path is on the Evil Shortcut, i.e. esum[i] < gsum[i], then it is necessary to destroy all gnomes from that Shortcut using the algorithm described above. In the opposite case it is necessary to set gsum[i] = 0 and update corresponding value in the segment tree of the Shortcut gtree.

So one gnome can be removed from the path of Death Mission in O(_log_(_N_)). The amount of gnome removals does not exceed amount of added gnomes (i.e. it is not more than Q), so the complexity of one Death Mission handling is also O(_log_(_N_)). The total complexity is O(_log_(_N_) * Q).

Read more »

Tutorial of Codeforces Round #115
 
 
 
 
  • Vote: I like it  
  • +46
  • Vote: I do not like it  

By ashmelev, 5 years ago, translation, In English,

Problem 175A - Robot Bicorn Attack

Go over all possible partitions of the given string into 3 substrings (for example, go over a pair of indexes — the ends of the first and the second substrings). If all three substrings of the partition satisfy constraints (there are no leading zeroes and the corresponding number does not exceed 1000000), then update the current answer with the sum of obtained numbers (if it is necessary). The total amount of partitions is O(N^2), where N is the length of the string. The check of one partition takes O(N).

Problem 175B - Plane of Tanks: Pro

The solution is to simulate actions described in the statement. Find the best result for each player and count total amount of players N. Then find a number of players C for each player , those results are not better than best result of the considering player (this can be done by going over all players). Then it is necessary to determine players category using numbers C and N. In order to avoid rounding error use the following approach:

  • if C * 100 >= N * 99, then the player belongs to category "pro"
  • if C * 100 >= N * 90, then the player is "hardcore"
  • if C * 100 >= N * 80, then the player is "average"
  • if C * 100 >= N * 50, then the player is "random"

In other case the player is "noob".

Problem 175C - Geometry Horse

Obvious, that figures should be destroyed in the cost increasing order. Sort figures type in ascending order of their costs. Consider two pointers – position i in the array P (current factor) and position j in the array of figures type. Consider the current answer and the number of figures G, those need to be destroyed to move to the next value of factor. If the number of figures F of the current type does not exceed G, then add F * (i + 1) * Сj to the answer and reduce G by F and increase pointer j by 1. In other case add G * (i + 1) * Cj to the answer, reduce F by G, increase i by 1 and set G = Pi – P(i-1). Continue iteration until all figure types are considered.

Problem 175D - Plane of Tanks: Duel

First consider case when at least one probability of not-piercing is equal to 100%. If Vasya does not pierce the enemy tank with probability 100%, then the answer is 0. If the enemy tank cannot pierce Vasya's tank with probability 100% then the answer is 1. Then consider that the probability of shot does not pierce tank does not exceed 99%. It can be checked that the probability that tank will stay alive after D = 5000 shots is less than 10^-6 (for any damage value, probability of not-piercing and amount of hit points). For each tank calculate the following table dp[i][j] — probability that tank will have j hit points after i shots to him. dp[0][hp] = 1, where hp – is the initial amount of hit points. In order to calculate the line dp[i+1] it is necessary to go over all possible damages for each value of j in the line dp[i], which shot (i+1)-th damages (considering cases when the shot does not pierce the tank armour) and update appropriate values of the line (i+1):

dp[i + 1][max(0, j – x)] += dp[i][j] * (1 – p) / (r – l + 1)

where p – is the probability of not-piercing, x – possible shot damage. Let's dpv – calculcated table for Vasya's tank and dpe is the table for enemy's tank. Now it is necessary to find probability that enemy's tank will be destroyed after i shots of Vasya's tank: pk[i] = dpe[i][0] – dpe[i-1][0]. Vasya wins the following way: Vasya fired (K — 1) shots and do not destroy enemy tank and is still alive also. After that Vasya fires K-th shot and destroy the enemy. Go over K and calculate the probability of Vasya's victory with the K-th shot. In order to do this find how many shots T can fire the enemy before Vasya makes K-th shot (here is the only place in the solution where we must use the gun recharge speed):

T = ((K – 1) * dtv + dte - 1) / dte

where dtv is the time required to recharge the gun, dte is the time of enemy gun recharge. Then the probability of victory is (1 – dpv[T][0]) * pk[K]. The answer for the problem is the sum all these probabilities for each K from 1 to D. The algorithmic complexity of the algorithm is O(D * hp * (r – l)).

Задача 175E - Power Defence

If we reflect the position of towers alogn the line OX then the interval where towers will affect the Villain will not change. So, we can consider that towers can be built in the points (_x_, 1), not more than two towers in the same point. If there exists point X that there are towers to the left and to the right from X but in the point X there is no tower, then abscissas of all towers "to the right" can be reduced by 1 and the answer will not become worse. The same way, we can prove that there are no adjacent points with exactly one tower in each one. Now it is easy to check that in order to construct the optimal solution it is enough to check 13 successive points.

Go over positions of freezing towers. In the worst case there are approximately 200000 cases to put freezing towers into 13 points. Consider the case when we fixed positions of several freezing towers. Let's calculate how much damage can hit fire-tower or electric-tower in the point for each empty points (points where we can put two towers are splitted into two) and save numbers into the array d (_d_[k].f and d[k].e – damage by fire and electricity in the point k correspondingly). Sort the array d in the order of decreasing of the value d[k].f. Then optimal position of the rest towers can be found using dynamic programming. Designate dp[i][j] – the maximum possible damage, which can be hitted if we have i fire-towers and j electric-towers. Designate p — the amount of towers have been set already: p = cf – i + ce – j. If i = 0 then we used first p values of array d and the answer is the sum of j maximum elemets of d[k].e, starting from index p. Otherwise we put one fire-tower or one electric tower in the position p. It is necessary to put the tower into position p because in the opposite case the d[p].f will decrease. Then:

dp[i][j] += max(dp[i - 1][j] + d[p].f, d[i][j – 1] + d[p].e)

The answer is the value dp[cf][ce], which is calculated in O(cf * ce * log(ce))

Comment1: exhaustive search can be reduced in 2 times because any two symmetric towers arrangements are equivalent and have the same answer. However, this optimization is not required with a given constraints.

Comment2: the formula of Villain speed decrease 1 / (K + 1) allows to calculate the tower damage for a case when all freezing towers are fixed easily. Freezing towers can be taken into account separately.

Read more »

Tutorial of Codeforces Round #115
 
 
 
 
  • Vote: I like it  
  • +23
  • Vote: I do not like it  

By ashmelev, 6 years ago, In Russian,

Вот и наступил последний день нашего пребывания в Токио. Собственно, на этот день и был запланирован гуглоконтест, а так же все прилагающиеся к нему мероприятия: разбор задач, награждение, пьянка торжественный ужин.


Read more »

 
 
 
 

By ashmelev, 6 years ago, In Russian,

(приношу извинения за большие перерывы во времени между написанием частей, для тех, кто забыл о чем речь или вообще не в курсе, о чем сей пост - вот ссылки на предыдущие части: первая, вторая)

На третий день нашего путешествия нужно уже было переселяться в отель IBIS Roppongi, предложенный гуглом для проживания участников. Отель выглядел очень даже неплохо:

Read more »

 
 
 
 

By ashmelev, 6 years ago, In Russian,

На второй день пребывания в Токио мы, следуя пути самурая плану Милы-сан, отправились на остров Одайба. Главной целью поездки был "музей будущего" Мирайкан:


Read more »

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

By ashmelev, 6 years ago, In Russian,

29 июля в Токио прошел финал соревнования Google Code Jam. Каким-то непонятным образом в этом году мне удалось попасть в финал и посетить столицу Японии. Также на онсайт попал мой однокомандник Владислав Епифанов (vepifanov). Кроме того, мы договорились с саратовскими друзьями - Наташей Бондаренко (natalia) и Артемом Раховым (RAD) о совместном времяпрепровождении. Более того, по счастливому стечению обстоятельств, моя женщина, Мила Голубева (iberia), на данный момент проживает всё в том же Токио и великодушно согласилась сопровождать нас в этом путешествии. Таким образом, русская компания для обсуждения насущных проблем бытия подобралась вполне достойная:

  

Далее речь в этом посте пойдет не о самом соревновании, а о некоторых достопримечательностях Токио. Мы решили приехать на онсайт чуть раньше и успели посетить пару интересных мест, проведя в Японии 4 дня. 

Read more »

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

By ashmelev, 6 years ago, translation, In English,

Problem D.

First, let’s divide graph to connected components (provinces). Next, we consider only new graph on these components – for each province we assign a vertex of the graph. Let the total number of provinces is n. Initially the graph is empty since there are no roads between different provinces. Also for each province we have a limit of the number of tunnels that can be constructed from this province: ki = min (k, ci) where ci – the number of cities which was originally contained in the province (component) i. The resulting provinces graph should be connected after building tunnels and roads. When k = 1 we have to build at least n - 2 roads, otherwise the graph will have at least 3 components and at least 2 tunnels should be constructed from one of them which is prohibited.

Further, we assume that k > = 2. Let’s calculate the largest number of tunnels we can build. Let s – the sum of all numbers ki. Obviously we cannot build more than s / 2 tunnels since each tunnel connects exactly two provinces. The following statement is true: we can construct s / 2 (rounded to the lower side) of tunnels or to make a graph connected by constructing n - 1 tunnels (if s / 2 > = n - 1). Let’s consider vertices which have ki > 1. We may connect these vertices into a chain using tunnels. After that let’s start to connecting vertices with ki = 1to the chain (using tunnels too) while it is possible. Suppose we had less than s / 2 tunnels built and we are unable to build one more tunnel. It means that we have exactly one vertex j with degree no more than kj - 2. Thus kj > 1 and this vertex is included into the chain and all the vertices with ki = 1 are attached to this chain too (otherwise we could build another tunnel), so the graph is connected.

If after building the tunnels we have a connected graph then the answer is 0. Otherwise the graph consists of n - s / 2 components, that is we need to build at least n - s / 2 - 1 roads. In fact such a number of roads will be enough. Let’s draw each of n - s / 2 - 1 roads the following way. First, choose 2 different connected components in the current graph. Because we have built tunnels (and possibly roads) only between different components each of the chosen components is a tree. So these components have vertices with degree not greater than 1. Now, let’s choose one such vertex in each of the selected components and connect the components through these vertices (i.e. the vertices are merged into one keeping the edges from them). Thus we have a new vertex (province) with no more than two tunnels constructed from it, so we did not violate the terms since k >= 2. Thus we can get a connected graph by building additional n - s / 2 - 1 roads which is the answer for the problem.


Problem E.

When x = 2 then the answer is 0. Further we assume that x > 2.

In order to uniquely identify the desired number of items t we must choose a set of numbers ai so that for every y from 2 to x the representation in modes ai is unique, i.e. sets of numbers b (y, i) = y / ai (rounded up) are pairwise distinct among all y. Note that for each i function b(y, i) is monotone by y. Hence if for some i and numbers y and z (y < z) holds b(y, i) = b(z, i) then b(y, i) = b(y + 1, i) too. So to select the set of numbers ai it is sufficient to guarantee that for each y from 2 to x - 1 exists a number j such that b(y, j) < b(y + 1, j). It is easy to see that b(y, j) < b(y + 1, j) if and only if y is divisible by aj. Thus, it is necessary that for each y from 2 to x - 1 exists number ai so that y is a multiple of ai. If some number ai is equal to 1 Vasya can just see the list in this mode to find the desired number and the answer for the problem is 1. Otherwise it is necessary and enough to take all the primes pi < x in our set ai to find the number. Indeed if we will not use some prime number pi then we will be unable to distinguish numbers pi and (pi + 1) (since pi is not divisible by some of the selected numbers). On the contrary if we will use all primes less than x then any number from 2 to x - 1 will be divisible by at least one of them. Thus we need to check whether there are all prime numbers less than x among ai. Since the number of primes from 1 to x is about O(x / ln (x)) for large x all prime numbers less than x cannot be in the set of numbers ai. For example the following statement is true: if x > 20 * n then the answer is -1. This means that we can use the Sieve of Eratosthenes to find all primes less than x for x <= 20 * n and to check whether there is at least one number from them which does not occur in ai. If such number exists then the answer for the problem is -1 otherwise the answer is the number of primes less than x.


Problem F.

If for some velocity v1 we were able to go from point A to point B and receive no more than k hits, then for any velocity v2 > = v1 we also will be able to go from A to B. So we can use  the binary search algorithm to find the answer. 

Suppose we have fixed speed of the tank v. Now we have to count how many enemy tanks will be able to shoot at our tank during the ride. Let’s consider enemy tank i located at the point P on the plane. It may aim at our tank in two ways: turn the turret at point B or rotate the turret at point A and then start turning it from point A to point B. In the first case we may just compare the time required for the tank  to move from A to B with the time required the enemy to aim the turret to point B. If the enemy tank will be able to take aim to B before we can reach this point then the enemy can make a shot. Next consider the second possible enemy strategy.  Let’s draw perpendicular PQ to the line AB. So we have divided the segment AB into 2 parts: AQ and QB (if Q does not lie on the segment AB then one of the parts will be empty and the other is a segment of AB. In this case let Q denote the end of segment AB closest to the base of the perpendicular). Let’s consider the first part of the segment - AQ (before the base of the perpendicular). It is easy to check that while the angular velocity of the turret is a constant, the linear velocity of the enemy sight along the segment AQ is monotonely decreasing. Given the fact that the speed of our tank along AB is constant we find that the difference between the coordinates of the enemy’s sight and the tank at the AQ interval is a convex function of time (second derivative is negative). Also this fact can be verified by finding the second derivative of this function explicitly. Thus we can use the ternary search algorithm for finding the minimum of this function on a time interval corresponding to time when our tank rides at segment AQ. When the minimum value of this function is negative the enemy is able to take aim at our tank and perform a shoot. Otherwise, the tank will ride ahead the enemy sight on the whole interval AQ. (Using similar statements we can find for example the minimum value of the time difference between reaching a point D of the interval AQ by the enemy sight and by our tank). It is possible to avoid the ternary search by finding a moment when the speed of the sight is equal to the speed of our tank and check who is closer to point B at this moment. But in this case we are to carefully handle the cases where one velocity is always greater than the other on the whole interval. 

Now let’s consider the second part of the segment - QB (after the base of the perpendicular). If the enemy is unable to shoot in our tank at the first part of the segment (AQ) then at the time of sighting the enemy on point Q our tank will be located closer to point B than the sight. Similarly the first part of segment AB, we can prove that the linear speed of sight along QB is
monotonely increasing. So if at some point C of segment QB the sight of the enemy tank has caught our tank then speed of the sight should be higher than speed of our tank at that moment (otherwise the enemy would not be able to catch the tank). Due to the monotonicity of the sight velocity on the remaining segment CB the sight will be faster than the tank and the sight will reach point B before our tank. Accordingly, if the enemy's sight has reached point B after our tank then the tank was ahead the sight on the whole interval QB too. Thus, to determine whether the enemy can shoot it is sufficient to check only point B. 

Performing these calculations for each of the n enemies we get the number of hits on our tank and comparing this value with the number k we go to the desired branch of the binary search.

Read more »

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

By ashmelev, 6 years ago, translation, In English,

Problem A.

Let’s call the monster dimension sizes as x1, x2, x3.

1. O(min(k, x1 + x2 + x3)) solution

We can make at most (x1 – 1) + (x2 – 1) + (x3 – 1) cuttings, so we may assume that k <= x1 + x2 + x3 – 3. For each of the three dimensions we will store an integer ai – number of cuttings performed through the corresponding dimension. Let’s perform the following actions k times: consider all numbers ai which we may increase (ai <  xi - 1) , call these dimensions “uncompleted”. Select the minimum number aj among all uncompleted ai and perform a cut through the corresponding dimension (aj will be increased by 1 as the result). Now let’s consider the resulting set after k actions: {a1, a2, a3}. Using the described algorithm we grant that the maximum element of this set is as little as possible and the minimum element is as big as possible. Because the sum a1 + a2 + a3 = k is fixed, we get the maximum product (a1 + 1) * (a2 + 1) * (a3 + 1) which is the answer for the problem.

2. O(1) solution

Instead of simulation all the k actions we may quickly determine values of numbers ai after using the algorithm described above.

Let x – the smallest value among (x– 1). When x * 3 >= k on each of the algorithm iterations all three dimensions will be uncompleted. It means that during the first (k / 3) * 3 steps each of numbers ai will be increased by (k / 3). Then 0, 1 or 2 numbers ai will be increased by 1 subject to value of k % 3. So, we have found values ai.

Otherwise (x * 3 < k) during the first x * 3 steps each of ai will be increased by x. After that we will have at most two uncompleted dimensions which can be processed a similar way (we should choose the minimum value x among the remaining uncompleted dimensions).

 

Problem B.

We may assume that we have exactly n awarded places but some of them give 0 points.

Let’s sort places by amount of points (bi) and racers by amount of currently gained points (ai). First let’s find the best place Vasya can reach. In the best case he will get b0 points (where b0 is the greatest number among bi). So, let the total Vasya’s point is v. Now we should to distribute other prize points to racers so that the number of racers better than Vasya will be minimal. For doing that we are to give maximum number of prizes so that corresponding racers will have less than v points. Note that if we can give k prizes keeping this property, than we can give k “cheapest” prizes too. The following statement is also true: if we can get a prize with t points to racer i and to racer jai > aj, then it is better to give this prize to racer i. Formally: if there exists a way to give k prizes where this prize will get racer j, than there exists a way to give k prizes where this prize will get racer i. It can be proven the following way. Consider a way to give k prizes where racer j got prize with t points, racer i – s points or didn’t get prize at all. In the first case we can swap prizes for racers i and j: ai > aj and ai + s < v (since racer i have got the prize), so aj + s < v, and ai + t < v i.e. this change is acceptable. In the second case we can just give the prize t to racer i instead of racer j. In the both cases we get a way to give k prizes where racer i receive prize t.

Now including this statement we may give prizes to racers using the following greedy algorithm. Let’s begin to give prizes starting from the cheapest one and check the racers starting from the best one (of course excluding Vasya and the best prize). For each prize i we will go through the racers until applicable racer (j) found: bi + aj < v. If no such racers remain we are unable to give more prizes without violating the rule (racers should have less than v points). In this case we should stop the algorithm and the answer is n – k where k is the number of prizes we have given. If we have found such racer j we can give him prize bi and go to the next prize. Complexity of this step is O(n).

Similarly we can find the worst place for Vasya. For doing that we should give him the cheapest prize (note it may have positive points though). After that we should distribute the prizes iterating over prizes from the largest to cheapest and check racers from the worst to the best one trying to make sum of racer’s points more than v.

Total complexity of the described algorithm is O(n * log(n)) because we have to sort prizes and racers.

 

Problem C.

It is easy to see that if we put some symbol c at position p of the string s it will not affect symbols at positions (p+2) and greater. So we have a standard DP problem. State of the dynamic is described by three parameters: p – the number of already processed symbols (or the index of currently processed symbol of the string), c – the previous symbol, t – the number of allowed symbol changes. To calculate the answer for a state we should choose the best value among all symbols for current position (when t > 0) or just go to the index (p + 1) with current symbol s[p]. Thus we get the followings formulas:

d[n][*][*] = 0

d[p][c][t] = d[p + 1][s[p]][t] + bonus[c][s[p]] when t = 0

d[p][c][t] = max(d[p + 1][c’][t – (c’ <> s[p])] + bonus[c][c’])

where n  is the length of string s.

Computation complexity of the algorithm is O(n * k * h^2), where h is the alphabet size (h = 26 for current problem).

Read more »

 
 
 
 
  • Vote: I like it  
  • -11
  • Vote: I do not like it  

By ashmelev, 6 years ago, translation, In English,
Good afternoon!

Authors of the today's contest are Evgeny Lazarev (Nizhny Novgorod STU) and me (Alexey Shmelev, Nizhny Novgorod SU)

Today you will help a boy Vasya find himself in the world of computer games.

Please note, that the round will be held in unusual format - 6 problems with costs 500, 1000, 1000, 1500, 1500 and 2000 points.
 

The round duration is increased to 2 hours and 30 minutes.


We say thanks to Marya Belova for statements translations, Artem Rakhov and Alexander Kouprin for help in contest preparation, writing alternative solutions and preparing of intricate tests.

Good luck and successful submission!

UPD: We apologize for inaccuracy in problem E and incorrect answers to several contestant clarifications.

Read more »

Announcement of Codeforces Beta Round #66
 
 
 
 
  • Vote: I like it  
  • +61
  • Vote: I do not like it