Problems A and B have no difficult ideas, so let's start from C.
Problem C
Put β = α / 10. Then the given numbers are a1 = [β], a2 = [2β], a3 = [3β], ... an = [nβ], and you have to count [(n + 1)β] ([x] is the integral part). The given equalities are equivalent to the system of inequalities: an ≤ nβ < an + 1,
. Choose maximum among left-hand sides and minimum among right-hand sides and obtain an inequality in the form A ≤ n < B. Now compare integral parts of the numbers A / (n + 1) and B / (n + 1). If B is divisible by (n + 1), subtract 1 from the right-hand side, because of the strict inequality in the right-hand side.
Problem D
Create vertors vi, and put positions of ones to the first vector v1, positions of 2s - to v2, positions of 3s to v3, etc. The vectors can be filled for one pass of the given sequence. The number of permutations is the number of ones, or the size of the first vector. Mentally put the first 1 to the first permutation, the second 1 to the second permutation, and so on. Now turn to 2. If the number of 2s is greater than the number of 1s, there is no solution. Otherwise put the first 2 to the first permutation, the second 2 to the second permutation, and so on. It is possible for some last permutations to remain without 2. Then do the same for 3s (there should be less 3s than 2s), and so on. Obtain the O(n) solution.
Put β = α / 10. Then the given numbers are a1 = [β], a2 = [2β], a3 = [3β], ... an = [nβ], and you have to count [(n + 1)β] ([x] is the integral part). The given equalities are equivalent to the system of inequalities: an ≤ nβ < an + 1,
. Choose maximum among left-hand sides and minimum among right-hand sides and obtain an inequality in the form A ≤ n < B. Now compare integral parts of the numbers A / (n + 1) and B / (n + 1). If B is divisible by (n + 1), subtract 1 from the right-hand side, because of the strict inequality in the right-hand side.Problem D
Create vertors vi, and put positions of ones to the first vector v1, positions of 2s - to v2, positions of 3s to v3, etc. The vectors can be filled for one pass of the given sequence. The number of permutations is the number of ones, or the size of the first vector. Mentally put the first 1 to the first permutation, the second 1 to the second permutation, and so on. Now turn to 2. If the number of 2s is greater than the number of 1s, there is no solution. Otherwise put the first 2 to the first permutation, the second 2 to the second permutation, and so on. It is possible for some last permutations to remain without 2. Then do the same for 3s (there should be less 3s than 2s), and so on. Obtain the O(n) solution.
Problem E
I tell two solutions. The first solution examines three possible cases separately. Build a graph which have pairs (h, t) as vertices, where h and t are dragon's current amounts of heads and tails. Edges are determined by possible Ivan's blows. Firstly, determine by bfs if it is possible to get from the start vertex to (0, 0) and the number of required steps in case if it is possible. Then check if the draw is possible, i.e. if the graph has cycles. Otherwise the graph is acyclic, and by dynamics on the acyclic graph you can find the longest path to a dragon-win position.
I tell two solutions. The first solution examines three possible cases separately. Build a graph which have pairs (h, t) as vertices, where h and t are dragon's current amounts of heads and tails. Edges are determined by possible Ivan's blows. Firstly, determine by bfs if it is possible to get from the start vertex to (0, 0) and the number of required steps in case if it is possible. Then check if the draw is possible, i.e. if the graph has cycles. Otherwise the graph is acyclic, and by dynamics on the acyclic graph you can find the longest path to a dragon-win position.
The second solution is to implement the standard algorithm often used for games on cyclic graphs. In fact the described process is a game on a cyclic graph with Gorynych moves determined uniquely. Start from vertices for that the answer is known, i.e. (0, 0) and h + t >= R, and go by reversed edges marking other vertices as winning or losing. Unmarked vertices will be draw-positions.
Problem F
For each of n days you have to solve the so-called "continuous knapsack problem". The solution is greedy: sort the firms by prices of produced snow and take snow starting from small prices until you get the required volume. Solutions with sorting for each n work too long. The author's solution takes O(nm) time, and it is based on ideas of QuickSort. Choose a random element r in the segment. The same way as in QuickSort, reoreder the rest elements so that elements smaller than r preceed r, and elements greater than r follow r. Calculate the total volume of snow with prices less than r. If it is enough for us - solve the problem on the left subsegment, otherwise - buy all the left subsegment and go to the right subsegment recursively.
For each of n days you have to solve the so-called "continuous knapsack problem". The solution is greedy: sort the firms by prices of produced snow and take snow starting from small prices until you get the required volume. Solutions with sorting for each n work too long. The author's solution takes O(nm) time, and it is based on ideas of QuickSort. Choose a random element r in the segment. The same way as in QuickSort, reoreder the rest elements so that elements smaller than r preceed r, and elements greater than r follow r. Calculate the total volume of snow with prices less than r. If it is enough for us - solve the problem on the left subsegment, otherwise - buy all the left subsegment and go to the right subsegment recursively.
Note an unpleasant feature of this problem. On the one hand, an answer can be rather large. On the other hand, the large precision is required. So you should calculate an integral part and a fractional part of the answer separately.
Problem G
The given graph is connected and has one cycle. First solve the problem for a tree. Choose any vertex as a root, and for each subtree calculate the following characteristics by standard dynamics:
1) number of vertices in it;
The given graph is connected and has one cycle. First solve the problem for a tree. Choose any vertex as a root, and for each subtree calculate the following characteristics by standard dynamics:
1) number of vertices in it;
2) sum of disnances from its root to all vertices in the subtree.
You will get the answer of the root. To find the answer for other vertices, make tree traversal again. Consider a move from a vertiex u to its descendant v. To get to v from vertices of its subtree one have to use the same path as to u but without the last edge. On the contrary, for the other vertices path will be lengthened for the length of the edge (u, v). Thus, d[v] = d[u] - L(u, v) * c[v] + L(u, v) * (n - c[v]), where c[v] is the number of vertices in the subtree with v as a root.
Now consider a graph with one cycle that may have trees attached. Consider the vertices in the cycle as roots of the trees. Calculate the answer inside each tree. The total answer for each vertex is the sum of:
1) the sum of all distances inside its subtree;
2) the sum for all other trees distances from their roots to all vertices in the tree (because to get from a vertex to some vertex in another tree one has to pass its root);
3) distance form the vertex to the root of its tree multiplied by the total number of vertices in other trees;
4) the sum of <legth of the shortest path in cycle from the root to the root of tree t> * <number of vertices in the tree t>.
The most difficult part is calculation of the summand 4. Go through the cycle by two pointers: one to the current vertex, another to the vertex that separetes vertices from that one has to go left or to go right to the current vertex. Moving the pointers one can obtain partial sums for the summand 4 in a total linear time.
The most difficult part is calculation of the summand 4. Go through the cycle by two pointers: one to the current vertex, another to the vertex that separetes vertices from that one has to go left or to go right to the current vertex. Moving the pointers one can obtain partial sums for the summand 4 in a total linear time.
Problem H
Imagine that you have exactly m black-and-white tiles. Then you can solve the problem as follows. Go by cells from top to bottom, from left to right. First put a black tiles, then put c black-and-white tiles, then - b white tiles. As a result you get a border of black-and-white tiles that separates black from white. The black-and-white tiles can be rotated such a way that makes the tiling correct. For example, n = m = 4, a = b = 6, c = 4.
In the general case replace c - m black-and-white tiles (for example) by white ones, and build the tiling. Then replace back white tiles to black-and-white ones starting form the lower-right corner. For example, n = m = 4, a = 6, b = 3, c = 7.
The solution of the problem always exists.
Imagine that you have exactly m black-and-white tiles. Then you can solve the problem as follows. Go by cells from top to bottom, from left to right. First put a black tiles, then put c black-and-white tiles, then - b white tiles. As a result you get a border of black-and-white tiles that separates black from white. The black-and-white tiles can be rotated such a way that makes the tiling correct. For example, n = m = 4, a = b = 6, c = 4.
######## ######## #####/\# ####/..\ \##/.... .\/..... ........ ........
######## ######## #####/\# ####/..\ \##/.... .\/..... .../\../ ../##\/#
The solution of the problem always exists.
nice structure for problem h