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.