codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1973.md (18015B)


      1 Source: https://codeforces.com/blog/entry/129556
      2 
      3 We hope you enjoyed the problems! Thank you for your participation! We are really sorry that A and D turned out to be harder than usual.
      4 
      5 [Problem A](https://codeforces.com/contest/1973/problem/A): idea by [prvocislo](/profile/prvocislo "Grandmaster prvocislo") and [satyam343](/profile/satyam343 "Master satyam343"), prepared by [prvocislo](/profile/prvocislo "Grandmaster prvocislo")
      6 
      7 **Hint 1:**
      8 
      9 If someone would claim that the number of draws that happened between the three players are $d_{1, 2}$, $d_{1, 3}$ and $d_{2, 3}$, can you check in $O(1)$ whether this can be true?
     10 
     11 **Hint 2:**
     12 
     13 The constraints are very small. The number of draws between any two players is at most $30$.
     14 
     15 **Hint 3:**
     16 
     17 Hint 3: Try all the possibilities for $d_{1, 2}$, $d_{1, 3}$ and $d_{2, 3}$ and find the one with the biggest sum out of all possibilities that could've been the result of game that ended with scores $p_1$, $p_2$ and $p_3$.
     18 
     19 **Solution:**
     20 
     21 After each round, sum of players' scores increases by 2, so if the sum $p_1 + p_2 + p_3$ is odd, answer is $-1$.
     22 
     23 Now, as the hints suggest, you can try all possible combinations of $d_{1, 2}$, $d_{1, 3}$ and $d_{2, 3}$ with three for-loops and check for each combination whether it could result in scores $p_1$, $p_2$ and $p_3$. Specifically, it must hold that $p_1 - d_{1, 2} - d_{1, 3} \equiv 0 \mod 2$, $d_{1, 2} + d_{1, 3} \leq p_1$ and the same two conditions for $p_2$ and $p_3$ analogously. Now you can find the biggest value of $d_{1, 2}$ + $d_{1, 3}$ + $d_{2, 3}$ over all valid choices and print it as the answer.
     24 
     25 The time complexity is $O(t \cdot \max(p) ^3)$.
     26 
     27 Implementation in Python: [261998440](/contest/1973/submission/261998440 "Submission 261998440 by myvaluska")
     28 
     29 **Bonus:**
     30 
     31 There exists an $O(1)$ solution with simpler implementation. Claim: The answer is min($(p_1+p_2+p_3)/2$,$p_1+p_2$). Let's prove this: if $p_1+p_2 \leq p_3$, then it's possible that players $1$ and $2$ played $p_1$ and $p_2$ draws with player $3$, after which there can't happen any additional draws in the game. if $p_1+p_2 \gt p_3$, that means $p_1 \gt p_3-p_2$, so player $1$ can first play $p_3-p_2$ draws with player $3$. Note, that if sum $p_1+p_2+p_3$ is even, then $p_1-(p_3-p_2)$ will also be even, so player $1$ can play $(p_1-(p_3-p_2))/2$ draws with each of players $2$ and $3$, thus adding up his score to exactly $p_1$. Finally, players $2$ and $3$ can play $p_2 - (p_1-(p_2-p_3))/2$ draws anong them, after which their scores become $p_2$ and $p_3$ respectively. Thus, it is possible that all rounds played ended with draws, making answer equal to $(p_1+p_2+p_3)/2$.
     32 
     33 Implementation in C++: [261998652](/contest/1973/submission/261998652 "Submission 261998652 by myvaluska")
     34 
     35 [Problem B](https://codeforces.com/contest/1973/problem/B): idea by [prvocislo](/profile/prvocislo "Grandmaster prvocislo"), prepared by [prvocislo](/profile/prvocislo "Grandmaster prvocislo")
     36 
     37 **Definition:**
     38 
     39 We will say that the array is $k$-lonely if $a_i|a_{i+1}| \ldots |a_{i+k−1}=a_j|a_{j+1}| \ldots |a_{j+k−1}$ is true for any two positive integers $1 \leq i,j \leq n−k+1$. Let $A$ be the maximum value an element in array $a$ can have.
     40 
     41 **Hint 1:**
     42 
     43 how to check if the array is $k$-lonely in $O(n \log A)$?
     44 
     45 **Hint 2:**
     46 
     47 if the array is $k$-lonely, the array is also $k+1$-lonely
     48 
     49 **Hint 3:**
     50 
     51 binary search the answer :)
     52 
     53 **Solution:**
     54 
     55 If the array is $k$-lonely, then since $a_i | \ldots | a_{i+k} = (a_i | \ldots | a_{i+k-1}) | (a_{i+1} | \ldots | a_{i+k}) = (a_j | \ldots | a_{j+k-1}) | (a_{j+1} | \ldots | a_{j+k}) = a_j | \ldots | a_{j+k}$, the array is also $k+1$-lonely.
     56 
     57 You can check whether an array is $k$-lonely in $O(n \log A)$ by calculating the OR of every segment of length $k$. You can do this by iterating $i$ from $1$ to $n-k+1$ and mantaining an array $t$ of size $\log n$ where $t[j]$ will be equal to the number of elements from $a_i, ..., a_{i+k-1}$ that have the bit $2^j$ set. For $i = 1$ we can calculate this array in $O (k \log A)$ and then when moving $i$ to the right, we can update the array in $O (\log A)$ complexity and we can also calculate the OR of all elements in the segment, using the array $t$, in $O (\log A)$.
     58 
     59 Once you have a checking function that runs in $O (n \log A)$, you can binary search the answer in $O(n \log A \log n)$ time, which is fast enough to pass.
     60 
     61 Implementation in C++: [261999140](/contest/1973/submission/261999140 "Submission 261999140 by myvaluska")
     62 
     63 **Bonus 1:**
     64 
     65 There also exists a nice $O(n \log A)$ solution, you can try to find it and get AC with it too :)
     66 
     67 **Hint:**
     68 
     69 Try calculating the lower bound on the total loneliness for each bit separately. Then the maximum of these is the answer.
     70 
     71 **Bonus 2:**
     72 
     73 Originally the problem had the same constraints, but you could also insert up to one arbitrary number in the array and find the minimum loneliness you can achieve in this way. It was proposed as the problem C. However, since the original B turned out to be too hard, this problem was made easier and shifted to this position.
     74 
     75 [Problem C](https://codeforces.com/contest/1973/problem/C): idea by [prvocislo](/profile/prvocislo "Grandmaster prvocislo"), prepared by [prvocislo](/profile/prvocislo "Grandmaster prvocislo")
     76 
     77 **Hint 1:**
     78 
     79 $n$ is even. What is the obvious upper bound on the number of the local maximums?
     80 
     81 **Hint 2:**
     82 
     83 Right, it is ${n \over 2} - 1$. We can actually achieve this value for any permutation.
     84 
     85 **Hint 3:**
     86 
     87 Consider $p_1 = n$. Can you find $q$ such that all other odd positions will be local maximums?
     88 
     89 **Solution:**
     90 
     91 We can easily prove that the sequence can have at most ${n \over 2} - 1$ local maximums, because the corner elements can't be the local maximums and no two consecutive elements can be local maximums. Let's see how we can achieve this upper bound.
     92 
     93 Let's consider the case when $n$ is at odd position in the original array first. We will construct a permutation $q$ such that the resulting array $a$ will have local maximums at all the odd positions except the first one. We can do this by placing the numbers ${n \over 2} + 1, {n \over 2} + 2, \ldots n$ at the odd indexes in $q$, giving the bigger numbers to the indexes with smaller $p_i$, and placing the numbers $1, 2, \ldots, {n \over 2}$ at the even indexes in $p$, giving the smaller numbers to the indexes with bigger $p_i$. Then since $n$ belongs to an odd index, the $a_i$ for each odd $i$ will be at least $n + 1$ while the $a_i$ for each even $i$ will be at most $n$. So every element of $a$ at odd position, except for the corner, will be a local maximum. This means we will have ${n \over 2} - 1$ local maximums, which is optimal, as we noitced above.
     94 
     95 We can get the solution for the case when $n$ is at even position analogously. For example, by reversing the permutation $p$, calculating the right permutation $q$, reversing them again and printing this $q$ as the answer.
     96 
     97 Time complexity: $O(n \log n)$ because of sorting. Actually, since you are sorting a permutation, you can do it in just $O(n)$ but it's not necessary.
     98 
     99 Implementation in C++: [261999352](/contest/1973/submission/261999352 "Submission 261999352 by myvaluska")
    100 
    101 [Problem D](https://codeforces.com/contest/1973/problem/D): idea by [prvocislo](/profile/prvocislo "Grandmaster prvocislo") and [TimDee](/profile/TimDee "Grandmaster TimDee"), prepared by [prvocislo](/profile/prvocislo "Grandmaster prvocislo") and [TimDee](/profile/TimDee "Grandmaster TimDee")
    102 
    103 **Hint 1:**
    104 
    105 Let $m$ be value we want to find. What values can $m$ take?
    106 
    107 **Hint 2:**
    108 
    109 Look at the maximum value in array $a$.
    110 
    111 **Hint 3:**
    112 
    113 Can you find the maximum value in array?
    114 
    115 **Hint 4:**
    116 
    117 Think about the segment containing the maximum value.
    118 
    119 **Hint 5:**
    120 
    121 Can you finish the problem in $n$ queries?
    122 
    123 **Solution:**
    124 
    125 Let's denote maximum value in array $a$ as $mx$. Since the element with maximum value will belong to some segment, then if $m$ exists, $m$ will be divisible by $mx$. Obviously, $m$ can't be greater than $n \cdot mx$, so now the candidates for value of $m$ are $mx, 2 \cdot mx, 3 \cdot mx, \dots, n \cdot mx$.
    126 
    127 To find the value of $mx$ we can query $?$ $1$ $n \cdot i$ for each $1\leq i \leq n$ and $mx$ will be equal to such $i$, querying which will give $n$ as the answer.
    128 
    129 We can check each of $n$ possible values in $k$ queries, but that wouldn't fit in query limit.
    130 
    131 Actually, since the length of each segment in partition will be greater than or equal to $\frac{m}{mx}$, and there are exactly $k$ segments, we can get a simple inequality $k \cdot \frac{m}{mx} \leq n$ (since sum of lengths of segments is exactly $n$), which means $m$ can not be greater than $mx \cdot \lfloor{n/k}\rfloor$, so it is enough to check first $\lfloor{n/k}\rfloor$ candidates for $m$ in $k$ queries each. Total number of queries used would be $n + k \cdot \lfloor{n/k}\rfloor$ which doesn't exceed $2n$.
    132 
    133 Implementation in C++: [261999488](/contest/1973/submission/261999488 "Submission 261999488 by myvaluska")
    134 
    135 [Problem E](https://codeforces.com/contest/1973/problem/E): idea by [prvocislo](/profile/prvocislo "Grandmaster prvocislo"), prepared by [prvocislo](/profile/prvocislo "Grandmaster prvocislo")
    136 
    137 **Hint 1:**
    138 
    139 Forget about graphs and data structures, there exists a simple $O(n)$ solution.
    140 
    141 **Hint 2:**
    142 
    143 Find the number of pairs with $l = r$ for which you can sort the permutation.
    144 
    145 **Hint 3:**
    146 
    147 Okay now that you have the special case handled, let's proceed to the general case. Find the minimum and maximum number that need to be swapped. Write down the inequalities that $l$ and $r$ have to satisfy so that we can swap these two elements with some other elements. This is the obvious necessary condition, right?
    148 
    149 **Hint 4:**
    150 
    151 Right, so if $l \neq r$ and additionally, $l$ and $r$ satisfy the inequalities mentioned above, is it enough?
    152 
    153 **Hint 5:**
    154 
    155 Yes, it is enough. But you can try to find the proof too :)
    156 
    157 **Solution:**
    158 
    159 Let's consider the pairs $l, r$ that have $l = r$ first. Then you can swap each $x$ with at most one other element, $l - x$. So if $i \neq p_i$ for some $i$, then we need to be able to swap the element $i$ with the element $p_i$, so it must hold that $l = i + p_i$. This is obviously also a sufficient condition, so it's enough to just find all $i + p_i$ for $i \neq p_i$, if there exist more then one different value, there's no good pair with $l = r$, if there's exactly one different value, there's exactly one good pair with $l = r$ and otherwise there are $2 n$ such pairs.
    160 
    161 Now let's count the pairs with $l \neq r$. If the array is sorted already, all pairs of $l, r$ are good. From now, consider only the case when the array isn't sorted yet.
    162 
    163 Let $L$ be the smallest value such that $p_L \neq L$ and $R$ the largest such value respectively. We obviously need to be able to swap $L$ and $R$ with some other values.
    164 
    165 Note that $L \neq n$ and $R \neq 1$, otherwise the array would be sorted already. Now we can get the inequalities $l \leq L + n$ and $R + 1 \leq r$, those are the necessary conditions for being able to swap the numbers $L, R$ with at least one other element.
    166 
    167 We can actually prove that these are the sufficient conditions too. If $l, r$ satisfy these conditions, then for any number $X$ in the range $[L, R-1]$, we can find an $x$ in the range $[l, r]$ such that $1 \leq x - X \leq n$ and then we can swap the numbers $X$ and $X + 1$, while not affecting any other element, by swapping $X$ and $x - X$ first and then swapping $X + 1$ and $x - X$. Thanks to this, we can sort the whole range of values between $L$ and $R$ — while the array isn't sorted, we will always find the smallest index $i$ that doesn't have the right value and keep swapping the value $p_i$ with the value $p_i - 1$, so eventually we will get $p_i = i$ and we can continue sorting on the right.
    168 
    169 So it's enough to just count the number of pairs $l, r$ such that $l \neq r$, $l \leq L + n$ and $R + 1 \leq r$, add it to the answer and print it.
    170 
    171 All of this can be done in time and memory complexity $O(n)$.
    172 
    173 Implementation in C++: [261999566](/contest/1973/submission/261999566 "Submission 261999566 by myvaluska") (I used set and therefore the time complexity is $O(n \log n)$ because it was more comfortable)
    174 
    175 [Problem F](https://codeforces.com/contest/1973/problem/F): idea by [prvocislo](/profile/prvocislo "Grandmaster prvocislo"), prepared by [prvocislo](/profile/prvocislo "Grandmaster prvocislo")
    176 
    177 **Hint 1:**
    178 
    179 What are the possible pairs of $\gcd$'s of the two arrays we can have after some swaps?
    180 
    181 **Hint 2:**
    182 
    183 For every pair $(X, Y)$ such that $X$ divides $a_1$ and $Y$ divides $b_1$, let's calculate the total number of indices $i$ such that we can have $X | a_i$ and $Y | b_i$ (either with or without the swap), and the minimum cost of swaps to achieve this. This is all we need to solve the problem, right?
    184 
    185 **Hint 3:**
    186 
    187 Write for each $i$ the conditions that the pair $(X, Y)$ has to satisfy in order to add $i$ to the result/make swap on the position $i$. Use something like SOS-DP to add up all the values efficiently.
    188 
    189 **Solution:**
    190 
    191 Let $k$ be the maximum value of $a_i$, $b_i$ on input ($10^8$). Let $D(k)$ be the maximum number of divisors a number in range $[1, \ldots, k]$ can have and $P(k)$ the maximum number of prime divisors such number can have.
    192 
    193 Let's think about how to solve one query (with $M$ coins) for now. Assume that in the optimal solution, we never swap $a_1$ and $b_1$. In the end, we will just run the same solution on input where $a_1$ and $b_1$ is swapped and $M$ is decreased by $c_1$, and then we will take the maximum of the two values these two runs will find.
    194 
    195 So now, in the optimal solution, the gcd of $a$ is always a divisor of $a_1$, and the $\gcd$ of $b$ is a divisor of $b_1$. Let's start by factorizing the two numbers in $O(\sqrt k)$.
    196 
    197 Now we will precalculate something in order to be efficiently able to determine for every $X$, a divisor of $a$, and $Y$, a divisor of $b_1$, whether we can have $\gcd(a_1, \ldots, a_n) = X$ and $gcd(b_1, ..., b_n) = Y$ simultaneously (and also the minimum cost of making it so). Then we can obviously answer the query by finding the best pair with sum at most $M$.
    198 
    199 Let's create new two dimensional arrays $P$ and $S$ of size $D(a_1) \times D(b_1)$. We will use $P$ to be able to tell the number of indexes $i$ such that we have either $X | a_i$ and $Y | b_i$ or $X | b_i$ and $Y | a_i$. If this count won't be $n$, then obviously we can't have $X$ and $Y$ as $\gcd$'s of $a$ and $b$. Also, we will use $S$ to tell us the sum of costs of all swaps we need to perform to have $X | \gcd(a_1, \ldots, a_n)$ and $Y | \gcd(b_1, ..., b_n)$.
    200 
    201 Now how to make two such arrays efficiently? It is obvious that if the pair of $\gcd$ s $(X, Y)$ is consistent with some indexes in the original array, then for every pair $(x, y)$ such that $x|X$ and $y|Y$, this pair of $\gcd$s is also consistent with those indexes (and maybe even more, also maybe some swaps just became unnecessary, but the point is, it doesn't get worse). So if we want to add some value to a pair, we also want to get it added to all its divisors. That's why, in order to calculate the arrays efficiently, we will first add some values on some positions and then do something like $2D$ prefix sums — for every cell $(x, y)$ we will sum the values for all pairs $(X, Y)$ such that $x | X$ and $y | Y$ and update its current value with it. Assuming this is going to happen in the end, let's look at every $i$ and consider what pairs are "good" for this index — with or without the swap:
    202 
    203 a) If $X$ divides $a_i$ and $Y$ divides $b_i$: For this type of pairs, we don't need to make any swaps on this index. Let's add $1$ to $P[\gcd(a_1, a_i)][\gcd(b_1, b_i)]$ to indicate that for all $(X, Y)$ such that $X|a_i$ and $Y|b_i$, we don't have to perform any swaps at the position $i$, the index is good as it is.
    204 
    205 b) $X$ divides $b_i$ and $Y$ divides $a_i$: In this case we will add $1$ to $P[\gcd(a_1, b_i)][\gcd(b_1, a_i])]$ and $c_i$ to $S[\gcd(a_1, b_i)][\gcd(b_1, a_i)]$ to indicate that if we pick $X$, $Y$ such that $X|b_i$ and $Y|a_i$, we can make index $i$ good if we swap $a_i$ and $b_i$.
    206 
    207 c) $X$ and $Y$ both divide both $a_i$ and $b_i$: To avoid counting both of the previous cases and therefore overcounting, we will add $-1$ to $P[\gcd(a_1, a_i, b_i)][\gcd(b_1, a_i, b_i)]$ and $-c_i$ to $S[\gcd(a_1, a_i, b_i)][\gcd(b_1, a_i, b_i)]$ (we have to undo paying for the swap since in this case we actually don't have to pay for it, but it falls under the case b) too).
    208 
    209 This step can be done in $O(n \log k)$.
    210 
    211 Now let's fix the arrays $P$ and $S$ so they store the actual values, not just the values we need to add.
    212 
    213 We will go through all primes $p$ dividing $a_1$ and update $P[X][Y]$ with $P[p \cdot X][Y]$ and $S[X][Y]$ with $S[p \cdot X][Y]$, similarly for all primes dividing $b_1$. If we make those updates in the right order, we achieve that $P[x][y]$ is the sum of all original values $P[X][Y]$ for all the pairs $(X, Y)$ such that $x|X$ and $y|Y$ like we wanted (and we can do the same for $S$).
    214 
    215 By careful precalculation of divisors and their order while factorizing, we can do this step in $O(D(k)^2 P(k))$. Some efficient implementations with extra log might pass also, but you will have to be more careful.
    216 
    217 For multiple queries, after precalculating the possible sums of $\gcd$ s and their costs, you can sort them and use binary search to answer the queries.
    218 
    219 Time complexity: $O(n \log k + \sqrt k + D(k)^2 P(k) + D(k)^2 \log D(k) + q \log D(k))$ Memory complexity: $O(n + D(k)^2 + P(k))$
    220 
    221 Implementation in C++: [261999743](/contest/1973/submission/261999743 "Submission 261999743 by myvaluska")
    222 
    223 Fun fact: While making the original proposal, I invented a version of this problem with lower constraints and thought it could be nice Div2C. Few days later, while I was on a walk, I realized this solution exists, so we decided to try to propose it as the hardest problem.