Team «We aren’t good, but 400k is 400k» is the first to solve task F after 7 minutes🎈
Team «МегаПачкаЧипсовЛейс» is the first to solve task G after 8 minutes 🎈
Team «Yet another team from Moscow» is the first to solve task D after 35 minutes 🎈
Team «Yet another team from Moscow» is the first to solve task B2 after 37 minutes 🎈
🔥3
Team «Ось Астана-Семей» is the first to solve task A after 76 minutes 🎈
😱17
Congratulations to team «Yet another team from Moscow» for being the first to solve all 12 tasks before the end of the contest! 🎈
🤯18🎉7
Deadline to send screen records is 15th of June, send it to the d.tatar@acc.bc-pf.org mail. Write your team name and team members’ names
Almaty Code Cup pinned «Deadline to send screen records is 15th of June, send it to the d.tatar@acc.bc-pf.org mail. Write your team name and team members’ names»
EDITORIAL
Task A
Task A involves identifying matching pairs of brackets in a sequence. We'll build a tree (or a forest) of nested bracket pairs (which can be done by traversing the string with a stack once). Note that removing a pair of brackets doesn't affect who is paired with whom. Removing a pair of brackets in the tree means removing a vertex and reattaching its children to the parent of the removed vertex. The answer to the task is the number of trees in the forest, which is the same as the number of roots in the forest. For convenience, we'll replace s with "(" + s + ")" so that we have exactly one tree with a non-removable root, and the answer will be the number of its children. We'll implement dynamic programming dp[v][k] representing the maximum number of roots we can obtain in the subtree of vertex v by removing exactly k vertices. This can be easily recalculated as dp[v][k] = max(dp[x][k1] + dp[y][k - k1]). Note that this dynamic programming works in O(n^2) because each pair of vertices in the tree contributes a constant amount of actions in recalculating this DP when we process their LCA.
Task B1:
For obtaining the maximum value, it is not advantageous to include a bit with a '-' sign, and it is advantageous to include a bit with a '+' sign. Conversely, for obtaining the minimum value, the opposite is true.
Task B2:
We'll convert the input data into standard bit strings and store them in a trie from higher bits to lower bits. To find the maximum value max(x ^ y) for a number x, we need to traverse the trie and check: if the current bit sign is '+', whether we can include the bit in the number (x ^ y); if it's '-', whether we can exclude this bit. Note: instead of using a trie, we can simply use lower_bound on an array.
Task C:
We'll show that with the optimal strategy, Pladis will either win within no more than two of his turns, or he will definitely lose. For Pladis to win, he needs to make one of the brackets equal to zero. If initially there is a bracket with identical symbols (like (a|a) or (!b|!b)), he can nullify it on his first move. Suppose there are no such brackets. If there is a symbol that occurs with the same sign with two different other variables (like {(a|b)&(a|d)} or {(!a|x)&(!a|!x)}), Pladis will also win by nullifying this symbol in both brackets and then nullifying one of the remaining symbols on his second move (or Znry will do this for Pladis in the second example). Otherwise, all symbols split into pairs, and Znry will simply complete each bracket for Pladis up to one. This means that it's enough to check the existence of Pladis' first move for which, regardless of Znry's move, he can win with his second move.
Task D
For each segment, we'll project it onto the Ox axis by finding formulas for the images of the points through the similarity of triangles. After that, we can either perform a scanline to include and exclude segments or sort the obtained projections, merge them into non-overlapping segments, and count the answer. It's important to read the input data as integers because floating-point numbers read slowly (TL53).
Task E
We'll precompute all the queries and solve the task offline. For each value of z, we'll remember which queries had this value x == z and which elements of the array a[i] == z. We'll create a segment tree for the XOR operation and initialize it with zeros. We'll iterate through the values of z from 1 to 10^6. For each z, we'll iterate through all i such that a[i] == z and update the segment tree tree.update(pos = i, val = a[i]). After this, we'll answer all queries with x == z simply by querying tree.get(l, r) because all elements a[j] > x are currently zeroed in it, and the answer will be calculated correctly.
Task A
Task A involves identifying matching pairs of brackets in a sequence. We'll build a tree (or a forest) of nested bracket pairs (which can be done by traversing the string with a stack once). Note that removing a pair of brackets doesn't affect who is paired with whom. Removing a pair of brackets in the tree means removing a vertex and reattaching its children to the parent of the removed vertex. The answer to the task is the number of trees in the forest, which is the same as the number of roots in the forest. For convenience, we'll replace s with "(" + s + ")" so that we have exactly one tree with a non-removable root, and the answer will be the number of its children. We'll implement dynamic programming dp[v][k] representing the maximum number of roots we can obtain in the subtree of vertex v by removing exactly k vertices. This can be easily recalculated as dp[v][k] = max(dp[x][k1] + dp[y][k - k1]). Note that this dynamic programming works in O(n^2) because each pair of vertices in the tree contributes a constant amount of actions in recalculating this DP when we process their LCA.
Task B1:
For obtaining the maximum value, it is not advantageous to include a bit with a '-' sign, and it is advantageous to include a bit with a '+' sign. Conversely, for obtaining the minimum value, the opposite is true.
Task B2:
We'll convert the input data into standard bit strings and store them in a trie from higher bits to lower bits. To find the maximum value max(x ^ y) for a number x, we need to traverse the trie and check: if the current bit sign is '+', whether we can include the bit in the number (x ^ y); if it's '-', whether we can exclude this bit. Note: instead of using a trie, we can simply use lower_bound on an array.
Task C:
We'll show that with the optimal strategy, Pladis will either win within no more than two of his turns, or he will definitely lose. For Pladis to win, he needs to make one of the brackets equal to zero. If initially there is a bracket with identical symbols (like (a|a) or (!b|!b)), he can nullify it on his first move. Suppose there are no such brackets. If there is a symbol that occurs with the same sign with two different other variables (like {(a|b)&(a|d)} or {(!a|x)&(!a|!x)}), Pladis will also win by nullifying this symbol in both brackets and then nullifying one of the remaining symbols on his second move (or Znry will do this for Pladis in the second example). Otherwise, all symbols split into pairs, and Znry will simply complete each bracket for Pladis up to one. This means that it's enough to check the existence of Pladis' first move for which, regardless of Znry's move, he can win with his second move.
Task D
For each segment, we'll project it onto the Ox axis by finding formulas for the images of the points through the similarity of triangles. After that, we can either perform a scanline to include and exclude segments or sort the obtained projections, merge them into non-overlapping segments, and count the answer. It's important to read the input data as integers because floating-point numbers read slowly (TL53).
Task E
We'll precompute all the queries and solve the task offline. For each value of z, we'll remember which queries had this value x == z and which elements of the array a[i] == z. We'll create a segment tree for the XOR operation and initialize it with zeros. We'll iterate through the values of z from 1 to 10^6. For each z, we'll iterate through all i such that a[i] == z and update the segment tree tree.update(pos = i, val = a[i]). After this, we'll answer all queries with x == z simply by querying tree.get(l, r) because all elements a[j] > x are currently zeroed in it, and the answer will be calculated correctly.
❤4
Task F
Since arrays a[] and b[] are symmetrical, let's assume that a[] has fewer inversions than b[]. Note that if b[] has at least one inversion, then there will be a pair of neighboring elements b[i] = 1 and b[i + 1] = 0. Swapping them will decrease the number of inversions by one, while swapping any pair of neighboring elements can change the number of inversions by no more than one. Hence, the answer is the absolute difference in the number of inversions in b[] and a[].
Task G
Write the string in a circle and for each pair of adjacent characters, calculate the number of steps required to move from one to the other on the keyboard (Manhattan distance). The answer will be the sum of all such distances minus the distance from s[l] to s[1]. A cyclic shift of the string allows you to move this subtracted transition anywhere, so it's optimal to move it to the position with the maximum distance to the next character.
Task H
If the second attack deals more damage than the first, always use it when possible; otherwise, always use the first attack.
Task I
Since you can stop at vertices, it makes sense to calculate dp[v] for each vertex v — the smallest time at which we can arrive at it. Looking closely, this dp suits Dijkstra's algorithm, and we just need to apply it.
Task J
If x = 1, then p >= 2 and all fractions are simply zero. Let's assume x >= 2. Note that floor(x / y) = (x - (x mod y)) / y. Consequently, floor(1 / p) + floor(x / p) + ... + floor(x^n / p) = (1 - (1 mod p)) / p + (x - (x mod p)) / p + ... + (x^n - (x^n mod p)) / p = ((1 + x + ... + x^n) - (1 mod p) - (x mod p) - ... - (x^n mod p)) / p. The sum 1 + x + ... + x^n can be found using the geometric series formula (x^{n + 1} - 1) / (x - 1). Note that x^k mod p is cyclic with a period of p - 1 by Fermat's Little Theorem, so it's enough to calculate the contribution of the remainder x^k mod p for each 0 <= k <= p - 1 and find the answer.
Task K
Plot points on a line and represent the constraint p[i] <= x as a half-interval [p[i], inf), and p[i] >= x as a half-interval (-inf, p[i]]. We need to find the point that lies in the minimum number of half-intervals. Hence, we can consider all queries offline and compress the coordinates to [1, n + m]. For each p[i], update the segment tree with += 1 for all points that do not fall within the corresponding interval (essentially saying that they need to change the sign of one additional inequality). For p[i] <= x, for example, perform tree.update(l = 1, r = p[i] - 1, val += 1). Then process the queries incrementally, updating the segment tree and querying tree.getmin(1, n + m).
Since arrays a[] and b[] are symmetrical, let's assume that a[] has fewer inversions than b[]. Note that if b[] has at least one inversion, then there will be a pair of neighboring elements b[i] = 1 and b[i + 1] = 0. Swapping them will decrease the number of inversions by one, while swapping any pair of neighboring elements can change the number of inversions by no more than one. Hence, the answer is the absolute difference in the number of inversions in b[] and a[].
Task G
Write the string in a circle and for each pair of adjacent characters, calculate the number of steps required to move from one to the other on the keyboard (Manhattan distance). The answer will be the sum of all such distances minus the distance from s[l] to s[1]. A cyclic shift of the string allows you to move this subtracted transition anywhere, so it's optimal to move it to the position with the maximum distance to the next character.
Task H
If the second attack deals more damage than the first, always use it when possible; otherwise, always use the first attack.
Task I
Since you can stop at vertices, it makes sense to calculate dp[v] for each vertex v — the smallest time at which we can arrive at it. Looking closely, this dp suits Dijkstra's algorithm, and we just need to apply it.
Task J
If x = 1, then p >= 2 and all fractions are simply zero. Let's assume x >= 2. Note that floor(x / y) = (x - (x mod y)) / y. Consequently, floor(1 / p) + floor(x / p) + ... + floor(x^n / p) = (1 - (1 mod p)) / p + (x - (x mod p)) / p + ... + (x^n - (x^n mod p)) / p = ((1 + x + ... + x^n) - (1 mod p) - (x mod p) - ... - (x^n mod p)) / p. The sum 1 + x + ... + x^n can be found using the geometric series formula (x^{n + 1} - 1) / (x - 1). Note that x^k mod p is cyclic with a period of p - 1 by Fermat's Little Theorem, so it's enough to calculate the contribution of the remainder x^k mod p for each 0 <= k <= p - 1 and find the answer.
Task K
Plot points on a line and represent the constraint p[i] <= x as a half-interval [p[i], inf), and p[i] >= x as a half-interval (-inf, p[i]]. We need to find the point that lies in the minimum number of half-intervals. Hence, we can consider all queries offline and compress the coordinates to [1, n + m]. For each p[i], update the segment tree with += 1 for all points that do not fall within the corresponding interval (essentially saying that they need to change the sign of one additional inequality). For p[i] <= x, for example, perform tree.update(l = 1, r = p[i] - 1, val += 1). Then process the queries incrementally, updating the segment tree and querying tree.getmin(1, n + m).