We hope you enjoyed our problems :) We're working on editorials now, other problems will be added as soon as possible =)↵
↵
[problem:572A]↵
↵
In this problem one need to check whether it's possible to choose $k$ elements from array $A$ and $m$ elements from array $B$ so that each of chosen element in $A$ is less than each of chosen elements in $B$. If it's possible then it's possible to choose $k$ smallest elements in $A$ and $m$ largest elements in $B$. That means that in particular, $k$-th smallest element of $A$ is less than $m$-th largest element in $B$. So, if $A[k] < B[n - m + 1]$ then the answer is "YES" and if not, then the answer is "NO".↵
↵
Problem author: [user:zeliboba,2015-08-22].↵
↵
Problem developers: [user:AlexDmitriev,2015-08-22], [user:Kostroma,2015-08-22].↵
↵
[problem:572B]↵
↵
Coming soon.↵
↵
[problem:571A]↵
↵
Let's count the number of ways to form a triple which can't represent triangle sides, and then we subtract this value from $C_{l+3}^{3} = \frac{(l+1)(l+1)(l+2)}{6}$ — the total number of ways to increase the sticks not more than $l$ in total. This number is obtained from partition of $l$ into 4 summands ($l_a + l_b + l_c + unused_l = l$), or can be counted using a `for` loop. ↵
↵
Now we consider triples $a + l_a, b + l_b, c + l_c$, where $l_a + l_b + l_c \le l, l_a, l_b, l_c \ge 0$. Fix the maximal side, for example it would be $a + l_a$. We'll have to do the following algo for $b + l_b$ and $c + l_c$ in the same way. The triple is not a triangle with maximal side $a + l_a$ if $a + l_a \ge b + l_b + c + l_c$. If we iterate over $l_a$ between $0$ and $l$, we have the following conditions on $l_b, l_c$:↵
$$l_b + l_c \le a - b - c + l_a,$$↵
$$l_b + l_c \le l - l_a,$$↵
$l_b, l_c \ge 0.$↵
So, non-negative integers $l_b, l_c$ should be such that $l_b + l_c \le min(a - b - c + l_a, l - l_a)$. If we denote this minimum as $x$ than we can choose $l_b, l_c$ in $\frac{(x+1)(x+2)}{2}$ different ways (again we divide $x$ into three summands: $l_b, l_c$ and some unused volume). Also when we fix $l_b$, there are $x - l_b + 1$ ways to choose $l_c$, so the overall number of pair $l_b, l_c$ is↵
$$\sum\limits_{l_b=0}^{x}(x - l_b + 1) = \sum\limits_{a=1}^{x+1}a = \frac{(x+1)(x+2)}{2},$$↵
so we obtain the same formula.↵
↵
To sum up, we need to iterate over the maximal side and over the addition to that side, then write these formulas, and subtract the result from the total number of different additions to the sides. The complexity of the solution is $O(l)$.↵
↵
Problem author: [user:Kostroma,2015-08-22].↵
↵
Problem developers: [user:Kostroma,2015-08-22], [user:AlexDmitriev,2015-08-22].↵
↵
[problem:571B]↵
↵
Coming soonWe can divide all indices $[1;n]$ into groups by their remainder modulo $k$. While counting $\sum\limits_{i=1}^{n-k}|a_i - a_{i+k}|$, we can consider each group separately and sum the distances between neighbouring numbers in each group. ↵
↵
Consider one group, corresponding to some remainder $i$ modulo $k$, i.e. containing $a_j$ for $j \equiv i \mod(k)$. Let's write down its numbers from left to right: $b_1, b_2, \ldots, b_m$. Then this group adds to the overall sum the value↵
$$\sum\limits_{j=1}^{m-1} |b_j - b_{j+1}|.$$↵
We can notice that if we sort $b_1, \ldots, b_m$ in non-decreasing order, this sum will not increase. So, in the optimal answer we can consider that numbers in each group don't decrease. Furthermore, in that case this sum is equal to $|b_m - b_1|$.↵
↵
Now consider two groups $b_1, \ldots, b_m$ and $c_1, c_2, \ldots, c_l$, both sorted in non-decreasing order. We claim that either $b_1 \ge c_l$ or $b_m \le c_1$, i.e. segments $[b_1, b_m]$ and $[c_1, c_l]$ can have common points only in their endpoints.↵
↵
Why is this true? These groups add $|b_m - b_1| + |c_l - c_1|$ to the overall sum. We consider the case $c_1 \ge b_1$, the other is symmetric. If $c_1 < b_m$, then swapping $c_1$ and $b_m$ will not increase the values these groups add to the answer, since the right border of $b$ group moves to the left, and the left border of $c$ group moves to the right. So, $c_1 \ge b_m$ in that case, and the assertion is proved.↵
↵
Now we know that the values in each group should from a continuous segment of the sorted original array. In fact, we have $k - (n \mod k)$ groups of size $\frac{n}{k}$ (so called small groups) and $(n \mod k)$ groups of size $(\frac{n}{k} + 1)$ (so called large groups). Consider the following dynamic programming: $dp[L][S]$ — the minimal sum of values added to the answer by $L$ large groups and $S$ small groups, if we choose the elements for them from the first $L \cdot (\frac{n}{k} + 1) + S \cdot \frac{n}{k}$ elements of the sorted array $A$. There are no more than $O(k^2)$ states, and each transition can be made in $O(1)$: we choose large or small group to add and obtain the number it adds to the sum by subtracting two elements of the sorted array. The answer for the problem will be in $dp[(n \mod k)][k - (n \mod k)]$.↵
↵
The overall complexity of the solution is $O(n \log{n} + k^2)$. We can note that in pretests $(n \mod k)$ was quite small, and some slower solutions could pass, but they failed on final tests.↵
↵
Problem author: [user:zeliboba,2015-08-23].↵
↵
Problem developers: [user:Kostroma,2015-08-22], [user:AlexDmitriev,2015-08-22].↵
↵
[problem:571C]↵
↵
Firstly let's assign values to variables occurring in our fomula only with negation or only without negation. After that we can throw away the disjuncts which contained them, since they are already true, and continue the process until it is possible. To make it run in time limit, one should use dfs or bfs algorithm to eliminate these variables and disjuncts.↵
↵
So now we have only variables which have both types of occurrences in disjucnts. Let's build a graph with the vertices corresponding to disjuncts, and for each varible $a$ make an edge between the disjuncts that contain $a$ and $!a$. Now we should choose the directions of edges in this graph in such a way that every vertex has at least one incoming edge. ↵
↵
We can notice that if some connected component of this graph is a tree, the solution is not possible: on each step we can take some leaf of this tree, and we have to orient its only edge to it, and then erase the leaf. In the end we'll have only one vertex, and it'll not have any incoming edges.↵
↵
Otherwise, take some cycle in the component and orient the edges between neighbouring vertices along it. Then run dfs from every vertex of the cycle and orient each visited edge in the direction we went along it. It is easy to easy that after this process every vertex will have at least one incoming edge.↵
↵
So, we should consider cases with the variables which values can be assigned at once, than construct a graph from disjuncts and variables and find whether each connected component has a cycle. If so, we also should carefully construct the answer, assigning the remaining variables their values, looking at the directions of the edges in the graph. The overall complexity is $O(n + m)$.↵
↵
Problem author: [user:zeliboba,2015-08-22].↵
↵
Problem developers: [user:Kostroma,2015-08-22], [user:zeliboba,2015-08-22], [user:yarrr,2015-08-22].↵
↵
[problem:571D]↵
↵
Comingsoon.tomorrow :)↵
↵
[problem:571E]↵
↵
Coming soon.
↵
[problem:572A]↵
↵
In this problem one need to check whether it's possible to choose $k$ elements from array $A$ and $m$ elements from array $B$ so that each of chosen element in $A$ is less than each of chosen elements in $B$. If it's possible then it's possible to choose $k$ smallest elements in $A$ and $m$ largest elements in $B$. That means that in particular, $k$-th smallest element of $A$ is less than $m$-th largest element in $B$. So, if $A[k] < B[n - m + 1]$ then the answer is "YES" and if not, then the answer is "NO".↵
↵
Problem author: [user:zeliboba,2015-08-22].↵
↵
Problem developers: [user:AlexDmitriev,2015-08-22], [user:Kostroma,2015-08-22].↵
↵
[problem:572B]↵
↵
Coming soon.↵
↵
[problem:571A]↵
↵
Let's count the number of ways to form a triple which can't represent triangle sides, and then we subtract this value from $C_{l+3}^{3} = \frac{(l+1)(l+1)(l+2)}{6}$ — the total number of ways to increase the sticks not more than $l$ in total. This number is obtained from partition of $l$ into 4 summands ($l_a + l_b + l_c + unused_l = l$), or can be counted using a `for` loop. ↵
↵
Now we consider triples $a + l_a, b + l_b, c + l_c$, where $l_a + l_b + l_c \le l, l_a, l_b, l_c \ge 0$. Fix the maximal side, for example it would be $a + l_a$. We'll have to do the following algo for $b + l_b$ and $c + l_c$ in the same way. The triple is not a triangle with maximal side $a + l_a$ if $a + l_a \ge b + l_b + c + l_c$. If we iterate over $l_a$ between $0$ and $l$, we have the following conditions on $l_b, l_c$:↵
$$l_b + l_c \le a - b - c + l_a,$$↵
$$l_b + l_c \le l - l_a,$$↵
$l_b, l_c \ge 0.$↵
So, non-negative integers $l_b, l_c$ should be such that $l_b + l_c \le min(a - b - c + l_a, l - l_a)$. If we denote this minimum as $x$ than we can choose $l_b, l_c$ in $\frac{(x+1)(x+2)}{2}$ different ways (again we divide $x$ into three summands: $l_b, l_c$ and some unused volume). Also when we fix $l_b$, there are $x - l_b + 1$ ways to choose $l_c$, so the overall number of pair $l_b, l_c$ is↵
$$\sum\limits_{l_b=0}^{x}(x - l_b + 1) = \sum\limits_{a=1}^{x+1}a = \frac{(x+1)(x+2)}{2},$$↵
so we obtain the same formula.↵
↵
To sum up, we need to iterate over the maximal side and over the addition to that side, then write these formulas, and subtract the result from the total number of different additions to the sides. The complexity of the solution is $O(l)$.↵
↵
Problem author: [user:Kostroma,2015-08-22].↵
↵
Problem developers: [user:Kostroma,2015-08-22], [user:AlexDmitriev,2015-08-22].↵
↵
[problem:571B]↵
↵
↵
Consider one group, corresponding to some remainder $i$ modulo $k$, i.e. containing $a_j$ for $j \equiv i \mod(k)$. Let's write down its numbers from left to right: $b_1, b_2, \ldots, b_m$. Then this group adds to the overall sum the value↵
$$\sum\limits_{j=1}^{m-1} |b_j - b_{j+1}|.$$↵
We can notice that if we sort $b_1, \ldots, b_m$ in non-decreasing order, this sum will not increase. So, in the optimal answer we can consider that numbers in each group don't decrease. Furthermore, in that case this sum is equal to $|b_m - b_1|$.↵
↵
Now consider two groups $b_1, \ldots, b_m$ and $c_1, c_2, \ldots, c_l$, both sorted in non-decreasing order. We claim that either $b_1 \ge c_l$ or $b_m \le c_1$, i.e. segments $[b_1, b_m]$ and $[c_1, c_l]$ can have common points only in their endpoints.↵
↵
Why is this true? These groups add $|b_m - b_1| + |c_l - c_1|$ to the overall sum. We consider the case $c_1 \ge b_1$, the other is symmetric. If $c_1 < b_m$, then swapping $c_1$ and $b_m$ will not increase the values these groups add to the answer, since the right border of $b$ group moves to the left, and the left border of $c$ group moves to the right. So, $c_1 \ge b_m$ in that case, and the assertion is proved.↵
↵
Now we know that the values in each group should from a continuous segment of the sorted original array. In fact, we have $k - (n \mod k)$ groups of size $\frac{n}{k}$ (so called small groups) and $(n \mod k)$ groups of size $(\frac{n}{k} + 1)$ (so called large groups). Consider the following dynamic programming: $dp[L][S]$ — the minimal sum of values added to the answer by $L$ large groups and $S$ small groups, if we choose the elements for them from the first $L \cdot (\frac{n}{k} + 1) + S \cdot \frac{n}{k}$ elements of the sorted array $A$. There are no more than $O(k^2)$ states, and each transition can be made in $O(1)$: we choose large or small group to add and obtain the number it adds to the sum by subtracting two elements of the sorted array. The answer for the problem will be in $dp[(n \mod k)][k - (n \mod k)]$.↵
↵
The overall complexity of the solution is $O(n \log{n} + k^2)$. We can note that in pretests $(n \mod k)$ was quite small, and some slower solutions could pass, but they failed on final tests.↵
↵
Problem author: [user:zeliboba,2015-08-23].↵
↵
Problem developers: [user:Kostroma,2015-08-22], [user:AlexDmitriev,2015-08-22].↵
↵
[problem:571C]↵
↵
Firstly let's assign values to variables occurring in our fomula only with negation or only without negation. After that we can throw away the disjuncts which contained them, since they are already true, and continue the process until it is possible. To make it run in time limit, one should use dfs or bfs algorithm to eliminate these variables and disjuncts.↵
↵
So now we have only variables which have both types of occurrences in disjucnts. Let's build a graph with the vertices corresponding to disjuncts, and for each varible $a$ make an edge between the disjuncts that contain $a$ and $!a$. Now we should choose the directions of edges in this graph in such a way that every vertex has at least one incoming edge. ↵
↵
We can notice that if some connected component of this graph is a tree, the solution is not possible: on each step we can take some leaf of this tree, and we have to orient its only edge to it, and then erase the leaf. In the end we'll have only one vertex, and it'll not have any incoming edges.↵
↵
Otherwise, take some cycle in the component and orient the edges between neighbouring vertices along it. Then run dfs from every vertex of the cycle and orient each visited edge in the direction we went along it. It is easy to easy that after this process every vertex will have at least one incoming edge.↵
↵
So, we should consider cases with the variables which values can be assigned at once, than construct a graph from disjuncts and variables and find whether each connected component has a cycle. If so, we also should carefully construct the answer, assigning the remaining variables their values, looking at the directions of the edges in the graph. The overall complexity is $O(n + m)$.↵
↵
Problem author: [user:zeliboba,2015-08-22].↵
↵
Problem developers: [user:Kostroma,2015-08-22], [user:zeliboba,2015-08-22], [user:yarrr,2015-08-22].↵
↵
[problem:571D]↵
↵
Coming
↵
[problem:571E]↵
↵
Coming soon.
