369A - Valera and Plates

We will use greedy algorithm. Let's now i-th day, and current dish is a dish of first type. Then if we have the bowl, let's use it. Otherwise we will increase the answer. If the current dish is a dish of the second type, we first try to get the plate, and then the bowl. If there are no plates/bowls at all, then we will increase the answer.

Author's solution: 5306397

369B - Valera and Contest

In this task you are to determine such array a₁, a₂, ..., a_n, that following conditions are met:

1. r ≥ a₁ ≥ a₂ ≥ ... ≥ a_n ≥ l;
2. ;
3. ;

It's clear to understand, that value s_k should be distributed evenly between the first k elements. For example, you can use following algorithm:

remainder = (s_k mod k);
for(int i = 0; i < k; i++) 
{
	a_i = s_k / k + (remainder > 0);
	remainder = remainder - 1;
}

If k ≠ n, you should use same algorithm with other elements, but there are to distribute value s_all - s_k.

Some participants forgot about test, where k = n. They received RE11.

Author's solution: 5306414

369C - Valera and Elections

Consider all the roads that we need to repair. Mark the ends of u, v white. After that, we will consider a simple dynamic programming d[v] (v is the vertex) on the tree that for each vertex in the tree determines the number of white vertexes in the subtree. It is easy to calculate this by using a recursive function calc(v, prev) (v is the current node, and prev its immediate ancestor):

calc(v, prev)
{
	d[v] = 0; 
	if (white[v])
		dv += 1; 
	for all vertexes u such that there is the edge (u,v) or (v,u), u != prev:
		calc(u, v);
		d[v] += d[u];  
}

After that we will add to answer all white vertexes v such that next condition is correct: d[v] = 1

Author's solution: 5306500

369D - Valera and Fools

Let's p[A] is the p_A from the statement.

It's clear to understand that you can discribe the state by using pair of integers (A, B), where A is a number of the fool with smallest index, B — the second fool from the left. It is clear to understand that fool with indexes j ≥ B will be living. After that we will use bfs on the states (A, B).

State (0, 1) is always visitable, because it is initial. We will push it in the queue. After that, there are only three transitions from current state (A, B).

1. (B + 1, B + 2) — this transition is possible if and only if p[A] > 0 and there are some fool with index j ≥ B, which has non-zero value p[j] > 0.
2. (A, B + 1) — this transition is possible if and only if p[A] > 0 и there are no fool with index j ≥ B, which has p[j] = 100.
3. (B, B + 1) — this transition is possible if and only if p[A] ≠ 100 and there are some fool with index j ≥ B, which has non-zero value p[j] > 0.

After that you are to determine number of states, which has distance from state (0, 1) less or equal to k. Also you should be careful, that if there are only one fool, that he doesn't shot.

Author's solution: 5306516

369E - Valera and Queries

Let's calculate sets xs[y] — all segments, whose right borders are exactly equal to y. Now we reduce our task to another. For each query we will count the number of segments that doesn't belong to any one point. Let's it will be the value v. Then the answer to the query is n - v. We add to our request the point 0 and a point MV + 1, where MV = 1000000. Let points request have the form x₁ < x₂... < x_n. Consider the x_i and x_i + 1. Let p_i is the number of segments that lie strictly inside x_i and x_i + 1. Then v = p₁ + p₂ + ... + p_n - 1. We will use following algorithm to find the values p_i. Let consider all such pairs (x, x_i + 1) for all requests and to add them to a second set xQ[y] — all pairs whose right boundary is equal to r. Then to find the values p of pairs (x_i, x_i + 1) we will iterate ascending the right border. Additionally, we will support Fenwick's tree, which can make  +  = 1 at the point, and can calculate sum of the prefix. Let i — the current right border. Then we can find out the value p for all pairs (l, r), with the right border is equal to the i (l, i). Let j left border of the pair. Then the answer for the pair is the value of S - sum(j), where S — all added to the Fenwick's left borders, and sum(j) — sum of the prefix j. After that, for the current coordinate i we need to consider all segments in the set xs[i]. Let j left boundary of the segment. Then we need to make  +  = 1 at the point j in our Fenwick's tree. The total solution complexity is .

Authors solution: 5306535