codeforces-scrape

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

2246.md (7419B)


      1 Source: https://codeforces.com/blog/entry/155143
      2 
      3 We hope you enjoyed the contest as much as we enjoyed writing it! Thank you especially to [PCTprobability](/profile/PCTprobability "International Grandmaster PCTprobability") [for](https://codeforces.com/contest/2246/submission/382271865) [your](https://codeforces.com/contest/2246/submission/382275385) [very](https://codeforces.com/contest/2246/submission/382277166) [entertaining](https://codeforces.com/contest/2246/submission/382278076) [submissions](https://codeforces.com/contest/2246/submission/382279367) [to](https://codeforces.com/contest/2246/submission/382283699) [problem](https://codeforces.com/contest/2246/submission/382285777) [E](https://codeforces.com/contest/2246/submission/382287709).
      4 
      5 **Rating predictions**
      6 
      7 ![ ](/predownloaded/90/af/90af678d167a48f6e9c92993a28c15ea40087ed9.png)
      8 
      9 [2246A - farmpiggie and Subset Sum](/contest/2246/problem/A "Codeforces Round 1108 (Div. 2)")
     10 
     11 **Hint 1**
     12 
     13 Try to eliminate a large class of possible sums.
     14 
     15 **Hint 2**
     16 
     17 Think about parity. Is it possible to eliminate all odd numbers?
     18 
     19 **Solution**
     20 
     21 Tutorial is loading...
     22 
     23 [2246B - ezraft and Array](/contest/2246/problem/B "Codeforces Round 1108 (Div. 2)")
     24 
     25 **Hint**
     26 
     27 Try to construct the solution iteratively, by adding each new element.
     28 
     29 **Solution**
     30 
     31 Tutorial is loading...
     32 
     33 [2246C - 0mar and Alternating Sums](/contest/2246/problem/C "Codeforces Round 1108 (Div. 2)")
     34 
     35 **Hint 1**
     36 
     37 For a subsequence to have an alternating sum of zero, it must contain an even number of elements from every group of equal numbers.
     38 
     39 **Hint 2**
     40 
     41 The number of ways to pick an even size subsequence is equal to the number of ways to pick an odd size subsequence.
     42 
     43 **Hint 2.1**
     44 
     45 If the array is of size $n$, there are $2^{n-1}$ ways to pick an odd size subsequence.
     46 
     47 **Hint 3**
     48 
     49 Try to find a simple formula for the case where there are only positive elements.
     50 
     51 **Hint 3.1**
     52 
     53 The formula is $2^{n-d}$ where $d$ is the number of distinct elements. This is because you must pick an even size subset from every group of equal numbers, and multiplying all the choices together gives you $2^{n-d}$.
     54 
     55 **Hint 4**
     56 
     57 Do casework on whether or not you select an odd number of $-1$ elements.
     58 
     59 **Solution**
     60 
     61 ### [2246C - 0mar and Alternating Sums](/contest/2246/problem/C "Codeforces Round 1108 (Div. 2)")
     62 
     63 First, let's solve the problem for only positive integers (i.e. $1 \leq a_i \leq 10^9$). For a subsequence to have an alternating sum of zero, it must contain an even number of elements from every group of equal numbers.
     64 
     65 **Proof**
     66 
     67 The alternating sum of the subsequence $b_1, \ldots, b_m$ is the sum $b_1 - b_2 + b_3 + \ldots + (-1)^{m+1}b_m.$ If $m$ is even, we can pair the terms into the form
     68 
     69 $(b_1-b_2) + (b_3 - b_4) + \ldots + (b_{m-1} - b_{m}).$
     70 
     71 Since each of these terms is non-positive, the sum is zero if and only if all the terms are zero, which happens iff the subsequence contains an even number of elements from each group of equal numbers.
     72 
     73 If $m$ is odd, we can group the terms as follows:
     74 
     75 $b_1 + (b_3-b_2) + (b_5 - b_4) + \ldots + (b_{m-1} - b_{m-2}).$
     76 
     77 Since $b_1 \gt 0$ and all the other terms are non-negative the alternating sum cannot be zero.
     78 
     79 Since the number of odd and even length subsequences of a group are equal, the number of subsequences of the array which contain an even number of elements from each group is the product of $2^{(\text{group size} -1)}$ over all numbers, which simplifies to $2^{(n - d)}$, where $d$ is the number of distinct elements in the array.
     80 
     81 **Proof that the number of odd and even length subsequences are equal**
     82 
     83 Let $S = {1,2,\ldots,n}.$ Our claim is equivalent to the statement that $S$ has $2^{n-1}$ subsets of even size. Let $T$ be a subset of $S$ which does not contain $1$. Then $|T \cup {1}| = |T| + 1,$ so its size has opposite parity. Furthermore this set is unique for $T$. Thus there are exactly $2^{n-1}$ pairs $(T, T \cup {1}),$ and each pair contains exactly one even size subset, so there are $2^{n-1}$ subsets of even size.
     84 
     85 Now we consider the full problem, with $a_i$ possibly equal to $-1.$ In this case there exist subsequences with alternating sum zero which do not contain an even number of elements from each group.
     86 
     87 Note that the number of subsequences containing an even number of $-1$ elements is $2^{(n - d)}$, since they will cancel each other, hence this reduces to the situation discussed above.
     88 
     89 It remains to count the number of subsequences which contain an odd number of $-1$ elements. Let the total number of $-1$ elements in the array be $c$. There are $2^{c-1}$ ways to pick an odd number of them. Given that our subsequence contains an odd number of $-1$ elements, the positive elements of the subsequence must have an alternating sum of $-1.$ This occurs precisely when there exists a pair $(v,v+1)$ such that both $v$ and $v+1$ occur an odd number of times, and the remaining elements all occur an even number of times in the subsequence.
     90 
     91 **Proof**
     92 
     93 Using the same notation as in the previous proof, we see that $b_1, \ldots, b_m$ must again be even length since otherwise the alternating sum will be positive.
     94 
     95 In the case where $b_1, \ldots, b_m$ has even length, we need exactly one of the terms $(b_i - b_{i+1})$ as grouped previously to be equal to $-1.$ This is precisely the characterization given.
     96 
     97 For any value $v$ such that both $v$ and $v+1$ occur, we can choose the pair $(v,v+1)$ to be the pair with odd counts. This "flip" does not change the number of choices, since in each group the number of odd and even length subsequences are equal.
     98 
     99 Therefore, the answer is $2^{(n - d)}$ if $-1$ isn't present; otherwise it is $2^{(n - d)} \cdot (\ell + 1)$, where $\ell$ is the number of values $v$ such that both $v$ and $v+1$ occur in the array.
    100 
    101 [2246D - diss_quack and Array Game](/contest/2246/problem/D "Codeforces Round 1108 (Div. 2)")
    102 
    103 **Hint 1**
    104 
    105 Try to solve the problem with no increments.
    106 
    107 **Hint 1.1**
    108 
    109 Do casework on whether or not there is an odd element in the array.
    110 
    111 **Hint 1.2**
    112 
    113 If there is an odd element, the answer is
    114 
    115 $\sum_{i=1}^n (\textsf{popcount}(a_i) + \#\textsf{bits}(a_i) - 1).$
    116 
    117 Otherwise you must first remove the minimum LSB from all the elements and then this answer is forced.
    118 
    119 This is true because if there is an odd element Bob can always put it in position 2, and force Alice to operate on each element individually.
    120 
    121 **Hint 2**
    122 
    123 Try fixing the minimum LSB over all $a_i$.
    124 
    125 **Solution**
    126 
    127 Tutorial is loading...
    128 
    129 [2246E - lce4113 and Security Game](/contest/2246/problem/E "Codeforces Round 1108 (Div. 2)")
    130 
    131 **Hint 1**
    132 
    133 You only need to determine one bit of $v$ in order to determine $b.$
    134 
    135 **Hint 2**
    136 
    137 The case $o = x$ needs to be handled carefully.
    138 
    139 **Hint 3**
    140 
    141 Try randomization.
    142 
    143 **Solution**
    144 
    145 Tutorial is loading...
    146 
    147 [2246F - Whoname and Unsorted Array](/contest/2246/problem/F "Codeforces Round 1108 (Div. 2)")
    148 
    149 **Hint 1**
    150 
    151 Consider the inversion count to check whether or not it is possible.
    152 
    153 **Hint 1.1**
    154 
    155 It is not possible if $n$ is even and the initial inversion count is odd.
    156 
    157 **Hint 2**
    158 
    159 Try sorting the elements in the suffix.
    160 
    161 **Hint 3**
    162 
    163 There is a clever $3$-move operation when you can't add the next element to the suffix.
    164 
    165 **Solution**
    166 
    167 Tutorial is loading...
    168 
    169 **Bonus**
    170 
    171 There is a solution that works in $\frac{5n}{3}$ operations.
    172 
    173 **Bonus++**
    174 
    175 Brute force suggests that it is always possible in at most $n$ moves.