1
Codeforces Round #103 (Div. 2) Разбор Задач.
source link: https://codeforces.com/blog/entry/3693
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Codeforces Round #103 (Div. 2) Разбор Задач.
By Polichka, 11 years ago, translation,
Problem A
It's clear that the leftmost soldier with the maximum height should be the first and the rightmost soldier with the minimum height should be the last. Thus we will minimize the number of swaps. And the answer is number of leftmost soldier with the maximum height - 1 + n - number of rightmost soldier with the minimum height. And if the leftmost soldier with the maximum height is more right then the rightmost soldier with the minimum height we should subtract one from the answer.
Problem B
Let's try to check all integer points of the table perimeter and add to the answer such of them that don't cover by circles of radiators. Let xa < xb and ya < yb, and if it's not true then swap xa and xb, ya and yb. So generals sit in the next integer points: (xa, y), (xb, y), (x, ya), (x, yb), where xa ≤ x ≤ xb и ya ≤ y ≤ yb. We should be attentive when we count the generals who sits in points: (xa, ya), (xa, yb), (xb, ya), (xb, yb), that don't count them twice.
Problem C
Let's count number of each letter in the second string and save it, for example, in array a[1..26]. For the first strings' prefix of length n, where n is the length of second string, (it's the first substring) we count number of each letter in array b[1..26]. We don't count characters ``\texttt{?}''. If there are b[i] ≤ a[i] for all i, then it's good substring. Then go to the second substring: subtract from the array b the first character: b[s[1] - 'a' + 1] – and add n + 1 character: b[s[n + 1] - 'a' + 1] + + . If some of these characters is ``\texttt{?}'' then we shouldn't do for it the subtraction or addition. Then repeat the showed check and go to the next substring. Let's repeat this procedure for all substrings of length n.
Problem D
d[i] --- the minimum distance from vertex s to vertex i, that counted by algorithm of Dijkstra. "et's count the number of points on each edge of the graph that are on the distance l form the vertex s (and l --- the minimum distance from these points to s).
For edge (u, v):
if d[u] < l and l - d[u] < w(u, v) and w(u, v) - (l - d[u]) + d[v] > l then add to the answer the point on this edge, the distance of which to the vertex u is l - d[u];
if d[v] < l and l - d[v] < w(u, v) and w(u, v) - (l - d[v]) + d[u] > l then add to the answer the point on this edge, the distance of which to the vertex v is l - d[v];
if d[v] < l and d[u] < l and d[u] + d[v] + w(u, v) = 2 * l then add to the answer the point on this edge, the distance of which to the vertex v is l - d[v] and to the vertex u is l - d[u].
And if d[i] = l, then let's add to the answer this point.
Problem E
It's clear that the nearest squares of the secondary diagonal to some sportsman form the "segment" of the squares of the secondary diagonal. Let's write these segments for each sportsman.
Let's consider sportsmen so that we should compare to each sportsman excactly one square of the secondary diagonal from his "segment" and to each square of the secondary diagonal no more then one sportsman. It's clear that sportsmen can reach theirs squares without occupying the same square simultaneously with another sportsman. We should maximize the number of choosen sportsmen. And solution of this reformulated problem is greedy.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK