Codeforces Round #299 Editorial

Python Code by Zlobober

Sol1: Consider n has x digits, f(i) = decimal representation of binary string i, m is a binary string of size x and its i - th digit is 0 if and only if the i - th digit of n is 4. Finally, answer equals to 2¹ + 2² + … + 2^x - 1 + f(m) + 1.

Time complexity: O(log(n))

Sol2: Count the number of lucky numbers less than or equal to n using bitmask (assign a binary string to each lucky number by replacing 4s with 0 and 7s with 1).

Time complexity: O(2^log(n))

Another Code by SoroushE

Python Code by Zlobober

536A - Tavas and Karafs

Lemma: Sequence h₁, h₂, …, h_n is (m, t) - Tavas-Eatable if and only if max(h₁, h₂, …, h_n) ≤ t and h₁ + h₂ + … + h_n ≤ m × t.

Proof: only if is obvious (if the sequence is Tavas-Eatable, then it fulfills the condition).

So we should prove that if the conditions are fulfilled, then the sequence is Tavas-Eatable.

Use induction on h₁ + h₂ + ... + h_n. Induction definition: the lemma above is true for every sequence h with sum of elements at most k. So now we should prove it for h₁ + h₂ + ... + h_n = k + 1. There are two cases:

1- There are at least m non-zero elements in the sequence. So, the number of elements equal to t is at most m (otherwise sum will exceed m × t). So, we decrease m maximum elements by 1. Maximum element will be at most t - 1 and sum will be at least m × t - m = m(t - 1). So according to the induction definition, the new sequence is (m, t - 1) - Tavas-Eatable, so h is (m, t) - Tavas-Eatable.

2- There are less than m non-zero elements in the sequence. We decrease them all by 1. Obviously, the new sequence has maximum element at most equal to t - 1 so its sum will be at most m(t - 1). So according to the induction definition, the new sequence is (m, t - 1) - Tavas-Eatable, so h is (m, t) - Tavas-Eatable.

For this problem, use binary search on r and use the fact that the sequence is non-decreasing and $\text{[math]}$ .

Time complexity: O(qlog(mt))

536B - Tavas and Malekas

First of all you need to find uncovered positions in s (because rest of them will determine uniquely). If there is no parados in covered positions (a position should have more than one value), then the answer will be 0, otherwise it’s 26^uncovered. To check this, you just need to check that no two consecutive matches in s have parados. So, for this purpose, you need to check if a prefix of t is equal to one of its suffixes in O(1). You can easily check this with prefix function (or Z function).

Time complexity: O(n + m)

536C - Tavas and Pashmaks

For each competitor put the point $\text{[math]}$ in the Cartesian plane. So, the time a competitor finishes the match is $\text{[math]}$ .

Determine their convex hull(with maximum number of points. i.e it doesn’t matter to have π radians angle). Let L be the leftmost point on this convex hull (if there are more than one, choose the one with minimum y component). Similarly, let D be the point with minimum y component on this convex hull (if there are more than one, consider the leftmost).

Proof: $\text{[math]}$ is the scalar product that is smaller if the point $\text{[math]}$ is farther in the direction of (S, R). It's obvious that the farthest points in some direction among the given set lie on a convex hull. (S, R) can get any value that is vector in first quadrant. So we need the points on the convex hull that we actually calculate (also we know that the points on the right or top of the convex hull, are not in the answer, because they're always losers).

It’s easy to see that the answer is the points on the path from D to L on the convex hull (bottom-left arc). i.e the bottom-left part of the convex hull.

Time complexity: O(nlog(n))

In this problem, we recommend you to use integers. How ? Look at the code below

Code of double version by PrinceOfPersia

In this code, function CROSS returns $\text{[math]}$ (it's from order of 10¹⁶, so there won't be any overflows.)

In double version, you should have a very small epsilon.

Another Code With Lower Envelope of Lines by Haghani

536D - Tavas in Kansas

For each vertex v, put a point (dis(s, v), dis(v, t)) with its point (score) in the Cartesian plane. The first player in his/her turn chooses a vertical line and erases all the points on its left side. Second player in his/her turn chooses a horizontal line and erases all the point below it.

Each player tries to maximize his/her score.

Obviously, each time a player chooses a line on the right/upper side of his/her last choice. Imagine that there are A different x components x₁ < x₂ < … < x_A and B different y components y₁ < y₂ < … < y_B among all these lines. So, we can show each state before the game ends with a pair (a, b) (1 ≤ a ≤ A, 1 ≤ b ≤ B It means that in this state a point (X, Y) is not erased yet if and only if x_a ≤ X and y_b ≤ Y).

So, using dp, dp[a][b][i] (1 ≤ i ≤ 2) is the maximum score of i - th player in state (a, b) and it’s i - th player’s turn. So, consider s[a][b] is the sum of the scores of all valid points in state (a, b) and t[a][b] is the amount of them. So,

If i = 1 then, dp[a][b][i] = max(s[a][b] - dp[c][b][2]) (a ≤ c ≤ A, t[c][b] < t[a][b]).

Otherwise dp[a][b][i] = max(s[a][b] - dp[a][c][1]) (b ≤ c ≤ B, t[a][c] < t[a][b]).

So we need two backward fors for our dp and another for on i. So, now the only thing that matters is updating the dp. For this purpose, we need two more arrays QA and QB.

QA[b][1] = the minimum value of pairs (dp[j][b][2], t[j][b]) and QA[b][2] = minimum value of pairs (dp[j][b][2], t[j][b]) such that t[j][b] > QA[b][1].second in the states we’ve seen so far. Similarly, QB[a][1] = the minimum value of pairs (dp[a][j][1], t[a][j]) and QB[a][2] = minimum value of pairs (dp[a][j][1], t[a][j]) such that t[a][j] > QB[a][1].second in the states we’ve seen so far. Now updating dp is pretty easy :

dp[a][b][1] = s[a][b] - (t[a][b] ≤ QA[b][1].second?QA[b][2].first: QA[b][1].first).

dp[a][b][2] = s[a][b] - (t[a][b] ≤ QB[a][1].second?QB[a][2].first: QB[a][1].first).

And updating QA and QB is super easy.

Now, let f = dp[1][1][1] and S be the sum of scores of all points. So, the score of first player is f and the second one is S - f.

Time complexity: O(n²)

Code by sobhan.miryoosefi

536E - Tavas on the Path

Let's call the answer for vertices v and u with edges e₁, e₂, ..., e_k on the path, score of sequence w(e₁), w(e₂), ..., w(e_k).

Use heavy-light decomposition. Decompose the edges into chains. So, for each Query, decompose the path into subchains. After solving the problem for them, combine them. Problem for subchains is :

We have an array a₁, a₂, …, a_n and q queries. Each query gives numbers x, y, l (1 ≤ x ≤ y ≤ n) and we should print the goodness of subarray a_x, a_x + 1, …, a_y.

For this problem, we have too choices: 1.Solve offline with a normal segment tree. 2.Solve online using persistent segment tree. Now, I prefer to use the first approach. Sort the array to have a permutation of 1, 2, …, n: p₁, p₂, …, p_n and a_p₁ ≥ a_p₂ ≥ … ≥ a_{p_n}. Also sort the queries in the decreasing order of l. No for i - th query (in the sorted order) we have information: x, y, l, index.

Then, use two pointers. Keep a pointer = n and Initially we have a binary string b, of length n with all indices set to 0. Then in each query:

for i = 1 to q
	while (pointer > 1 and l[i] >= a[pointer])
		Set p[pointer]-th bit of b (from left) to 1
		pointer = pointer - 1
	answer to query number index[i] = T(bx…by)

Now, we should fins T(b_x…T_y). For this purpose, we need a segment tree. In each node of the segment tree, we need to keep a package named node.

struct node{
	int p, s, cnt, tot;
};

A package node is used for calculating T of a binary string c. p = the number of leading 1s, s = the number of trading 1s, cnt = the total number of 1s, tot = the T value of the binary string after deleting its leading and trading 1s.

Merging two nodes is really easy. Also after reversing c, we just need to swap p and s.

So, we can determine the node of this subarray in subchains.

After solving these offline for subchains it's time for combining.

Merge the node of subchains in the path from v to LCA(v, u) then merge the result with the reverse of the nodes of answers in the subchains in path from LCA(v, u) to u.

Time complexity: O((n + m)log²(n))

Code by PrinceOfPersia (This was one of the hardest codes I ever wrote in competitive programming :D)

Shorter Code by Haghani