codeforces-scrape

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

2218.md (13554B)


      1 Source: https://codeforces.com/blog/entry/152680
      2 
      3 I hope you all enjoyed the contest! Special thanks to:
      4 
      5 * [damamila](/profile/damamila "Эксперт damamila"), for creating problem G
      6 * [chromate00](/profile/chromate00 "Эксперт chromate00"), [AG-88301](/profile/AG-88301 "Эксперт AG-88301"), [simplelife](/profile/simplelife "Эксперт simplelife"), [SpyrosAliv](/profile/SpyrosAliv "Кандидат в мастера SpyrosAliv"), [reirugan](/profile/reirugan "Кандидат в мастера reirugan") and [damamila](/profile/damamila "Эксперт damamila") for editorials for B-G respectively.
      7 * [cry](/profile/cry "Международный мастер cry"), for helping answer clarifications.
      8 
      9 **Rate the contest!**
     10 
     11 **Quality**
     12 
     13 * Excellent contest
     14 * Good contest
     15 * Average contest
     16 * Bad contest
     17 * Horrible contest
     18 
     19 **Difficulty**
     20 
     21 * Trivial contest
     22 * Easy contest
     23 * Average contest
     24 * Hard contest
     25 * Impossible contest
     26 
     27 #### [A — The 67th Integer Problem](https://codeforces.com/contest/2218/problem/A)
     28 
     29 **Solution**
     30 
     31 Many solutions exist here, and they are all trivial to find. Consider the value of $\min(x, y)$ when $x$ is constant, and you vary $y$. When $y \gt = x$, the value is $x$, and when $y \lt x$ the value is $y$. Therefore, the largest that $\min(x, y))$ can get for any value of $y$ is $x$. Therefore, outputting $y$ as any integer greater than or equal to $x$ works.
     32 
     33 A common mistake was to output $y=x+1$, which fails because $68$ is greater than $67$, therefore not a valid output.
     34 
     35 **Code (Python)**
     36 
     37 ```
     38 for _ in range(int(input())):
     39     print(67)
     40 ```
     41 
     42 **Rate the problem!**
     43 
     44 **Quality**
     45 
     46 * Excellent problem
     47 * Good problem
     48 * Average problem
     49 * Bad problem
     50 * Horrible problem
     51 
     52 **Difficulty**
     53 
     54 * Trivial problem
     55 * Easy problem
     56 * Average problem
     57 * Hard problem
     58 * Impossible problem
     59 
     60 #### [B — The 67th 6-7 Integer Problem](https://codeforces.com/contest/2218/problem/B)
     61 
     62 **Solution**
     63 
     64 Note how negating 6 out of 7 numbers is equivalent to negating all of them, and then negating one out of 7 numbers. Therefore, you can negate all 7 numbers, and then negate the least one afterwards.
     65 
     66 **Code (Python)**
     67 
     68 ```
     69 for i in range(int(input())):
     70     nums = list(map(int, input().split()))
     71     print(2 * max(nums) - sum(nums))
     72 ```
     73 
     74 **Rate the problem!**
     75 
     76 **Quality**
     77 
     78 * Excellent problem
     79 * Good problem
     80 * Average problem
     81 * Bad problem
     82 * Horrible problem
     83 
     84 **Difficulty**
     85 
     86 * Trivial problem
     87 * Easy problem
     88 * Average problem
     89 * Hard problem
     90 * Impossible problem
     91 
     92 #### [C — The 67th Permutation Problem](https://codeforces.com/contest/2218/problem/C)
     93 
     94 **Solution**
     95 
     96 Observe that the position of an element doesn't really matter: we are only interested in whether an element is a median, a large element or a small element (in its triple).
     97 
     98 Since $3n$ has no elements larger than it, it must be a large element. Similarly, since $1$ has no elements smaller than it, it must be a small element.
     99 
    100 To maximise the sum of medians, we should pick the largest possible median available, which is $3n-1$. Since $1 \lt 3n-1 \lt 3n$, this forms a valid triple.
    101 
    102 Now we can repeat the process on the subset ${2, 3, ... 3n-2}$, yielding the construction
    103 
    104 $\{1, 3n-1, 3n\}, \{2, 3n-2, 3n-3\}, \cdots , \{n, 2n-1, 2n\}$
    105 
    106 **Proof that this is optimal**
    107 
    108 Let the $i^{th}$ triple be ${l_i, m_i, r_i}$, with $l_i \lt m_i \lt r_i$, and wlog let $m_1 \lt m_2 \lt \cdots \lt m_n$ be the $n$ medians.
    109 
    110 Each median needs an element strictly larger than it not used in any other triple. So there should be at least $1$ element larger than $m_n$, at least $3$ elements larger than $m_{n-1}$ (namely $m_n$, $r_n$, $r_{n-1}$), and more generally, at least $2k - 1$ elements larger than $m_{n-k+1}$.
    111 
    112 In the set $1 \ldots 3n$, there are $3n - m_{n-k+1}$ elements larger than m_{n-k+1} (namely $m_{n-k+1}+1 \ldots 3n$), and so we need
    113 
    114 $2k-1 \leq 3n - m\_{n-k+1}$
    115 
    116 Rearranging, we get $m_{n-k+1} \leq 3n - 2k + 1$, as in the optimal construction.
    117 
    118 **Code (Python)**
    119 
    120 ```
    121 for _ in range(int(input())):
    122     n = int(input())
    123     k = 3 * n
    124     for i in range(1,n+1):
    125         print(i, k-1, k, end=" ")
    126         k -= 2
    127     print()
    128 ```
    129 
    130 **Rate the problem!**
    131 
    132 **Quality**
    133 
    134 * Excellent problem
    135 * Good problem
    136 * Average problem
    137 * Bad problem
    138 * Horrible problem
    139 
    140 **Difficulty**
    141 
    142 * Trivial problem
    143 * Easy problem
    144 * Average problem
    145 * Hard problem
    146 * Impossible problem
    147 
    148 #### [D — The 67th OEIS Problem](https://codeforces.com/contest/2218/problem/D)
    149 
    150 **Hint 1**
    151 
    152 Think something related to coprime numbers.
    153 
    154 **Solution**
    155 
    156 There are many ways to construct the array — we will provide two ways to do it.
    157 
    158 Let's take $n+1$ distinct numbers $b_1,b_2,\ldots,b_{n+1}$.
    159 
    160 Now let $a_i=b_i\cdot b_{i+1}$ for all $i$.
    161 
    162 Now $\operatorname{gcd}(a_i,a_{i+1})=b_{i+1}\cdot \operatorname{gcd}(b_i,b_{i+2})$.
    163 
    164 Now if $\operatorname{gcd}(b_i,b_{i+2})=1$ for all $i$, then we can obtain a distinct gcd for each adjacent pair and the construction is valid.
    165 
    166 One way to obtain this is to let all $b_i$ be all primes starting from $2,3,5,\ldots$. Since all numbers are coprime to each other, their pairwise $gcd$ is $1$ and we get a valid construction.
    167 
    168 Another way to obtain this to let all $b_i$ be odd numbers starting from $1,3,5,\ldots$. Since $\operatorname{gcd}(x,x+4)=1$ , where $x$ is odd, this construction is also valid.
    169 
    170 **Code (Python)**
    171 
    172 ```
    173 for _ in range(int(input())):
    174     n = int(input())
    175     k = 1
    176     for i in range(1,n+1):
    177         print(k * (k+2), end=" ")
    178         k += 2
    179     print()
    180 ```
    181 
    182 **Rate the problem!**
    183 
    184 **Quality**
    185 
    186 * Excellent problem
    187 * Good problem
    188 * Average problem
    189 * Bad problem
    190 * Horrible problem
    191 
    192 **Difficulty**
    193 
    194 * Trivial problem
    195 * Easy problem
    196 * Average problem
    197 * Hard problem
    198 * Impossible problem
    199 
    200 #### [E — The 67th XOR Problem](https://codeforces.com/contest/2218/problem/E)
    201 
    202 **Hint 1**
    203 
    204 What happens after two operations? Does the first operation matter?
    205 
    206 **Hint 2**
    207 
    208 Remember the propery that $x \oplus x = 0$.
    209 
    210 **Solution**
    211 
    212 We have an array $a = [a_1, a_2, a_3, \ldots, a_n]$. Suppose we performed the operations from left to right, to see how operations affect the array.
    213 
    214 After the first operation, the array becomes: $a = [a_2 \oplus a_1, a_3 \oplus a_1, \ldots, a_n \oplus a_1]$. Note that the first element was removed.
    215 
    216 After the second operation, the array becomes $a = [(a_3 \oplus a_1) \oplus (a_2 \oplus a_1), \ldots, (a_n \oplus a_1) \oplus (a_2 \oplus a_1)]$. Due to Hint $2$, this is the same as $a = [a_3 \oplus a_2, \ldots, a_n \oplus a_2]$.
    217 
    218 Note that this new array is independent of $a_1$. In fact, after any two operations, the value of the element chosen in the first operation does not matter. Taking this a step further: when doing three operations, the elements chosen for the first two operations do not matter. Inductively, the only thing that matters is the element we choose last for an operation (let it be $x$) and which element we never choose for an operation (let it be $y$). The final value of the array is going to be $x \oplus y$.
    219 
    220 Since $n$ is small, it is enough to brute force all possible pairs $(x, y)$. The answer is the maximum value of $a_x \oplus a_y$ among all pairs.
    221 
    222 **Code (Python)**
    223 
    224 ```
    225 for _ in range(int(input())):
    226     n = int(input())
    227     a = list(map(int, input().split()))
    228     m = 0
    229     for i in range(n):
    230         for j in range(i+1, n):
    231             m = max(m, a[i] ^ a[j])
    232             
    233     print(m)
    234 ```
    235 
    236 **Bonus**
    237 
    238 The problem of finding the integers $a$ and $b$ from an array such that $a \oplus b$ is maximized can be done in $O(n \log n)$ using a trie.
    239 
    240 You can see in detail how this would work on [this](https://threadsiiithyderabad.quora.com/Tutorial-on-Trie-and-example-problems) post. Roughly speaking, we insert the binary representation of each number in the trie. After that, for each number we try to find which other number gives maximum xor, which can be done with a greedy walk on the trie.
    241 
    242 **Rate the problem!**
    243 
    244 **Quality**
    245 
    246 * Excellent problem
    247 * Good problem
    248 * Average problem
    249 * Bad problem
    250 * Horrible problem
    251 
    252 **Difficulty**
    253 
    254 * Trivial problem
    255 * Easy problem
    256 * Average problem
    257 * Hard problem
    258 * Impossible problem
    259 
    260 #### [F — The 67th Tree Problem](https://codeforces.com/contest/2218/problem/F)
    261 
    262 **Hint 1**
    263 
    264 We know that the number of vertices in the entire tree is $x+y$. Therefore, the subtree of the root has size $x+y$. So if $x+y$ is even and $x$ is zero, there is no valid tree. Similarly, if $x+y$ is odd and $y$ is zero, there is no valid tree. From this point onwards, we can now exclude the root by decrementing either $x$ or $y$, and only considering the other vertices. The root will be trivially satisfied.
    265 
    266 **Hint 2**
    267 
    268 We claim that for any vertex whose subtree has an even size, it must have at least one child with an odd size. Indeed, suppose all of its children have even size. Then the total number of vertices in the subtree will be the sum of some even numbers, plus one, the node itself. By contrapositive, this implies the desired claim.
    269 
    270 Therefore, if the number of vertices with an even subtree size is larger than the number of vertices with an odd subtree size (excluding the root), there is no valid tree.
    271 
    272 **Hint 3**
    273 
    274 All other cases are possible.
    275 
    276 **Solution**
    277 
    278 Read the hints.
    279 
    280 Now, we will try to make every vertex (excluding the root) have subtree size either $1$ or $2$. To do this, we will attach $x$ disjoint pairs of vertices. Then we will attach each pair, and all of the remaining vertices, to the root. Now, the number of vertices with an even subtree size is exactly $x$, the parent from each of the pairs, as desired.
    281 
    282 **Code (Python)**
    283 
    284 ```
    285 for _ in range(int(input())):
    286     x, y = map(int, input().split())
    287     n = x + y
    288     d = y - x
    289 
    290     if (x == 0 and n % 2 == 0) or n//2<x:
    291         print("NO")
    292         continue
    293 
    294     print("YES")
    295 
    296     mm = 2 * x + (d % 2)
    297 
    298     for i in range(2, mm + 1):
    299         print(i - 1, i)
    300 
    301     for i in range(mm + 1, n + 1):
    302         print(mm, i)
    303 ```
    304 
    305 **Rate the problem!**
    306 
    307 **Quality**
    308 
    309 * Excellent problem
    310 * Good problem
    311 * Average problem
    312 * Bad problem
    313 * Horrible problem
    314 
    315 **Difficulty**
    316 
    317 * Trivial problem
    318 * Easy problem
    319 * Average problem
    320 * Hard problem
    321 * Impossible problem
    322 
    323 #### [G — The 67th Iteration of "Counting is Fun"](https://codeforces.com/contest/2218/problem/G)
    324 
    325 **Hint 1**
    326 
    327 When is there no valid $a$?
    328 
    329 **Hint 2**
    330 
    331 Remember for a person $i$ with $b_i \gt 0$ to be able to sit down, one of their neighbours already needs to be sat down.
    332 
    333 **Hint 3**
    334 
    335 What do you notice about people where $b_i = 0$?
    336 
    337 **Hint 4**
    338 
    339 If $b_i = 0$, then $a_i$ must also equal $0$.
    340 
    341 **Solution**
    342 
    343 If a person $i$ with $b_i \gt 0$ has no neighbour with a smaller $b_i$, they would never sit down so there is no valid $a$ so we output $0$.
    344 
    345 We can observe that all $a_i$ are independent of each other so long as they are consistent with the array $b$. This means we can compute the number of possible $a_i$ for every $i$ separately.
    346 
    347 Let $c_t$ be the number of people sat down at time $t$ or earlier. This is all people where $b_i \leq t$. For a time $t$, we can calculate $c_t$ using prefix sums as it is the sum of $c_{t-1}$ and the number of people that sit down at time $t$.
    348 
    349 For a person to sit down at time $t$, two conditions had to be met:
    350 
    351 1. At least $a_i$ people have already sat down strictly before time $t$.
    352 2. At least one of their neighbors (person $i−1$ or $i+1$, if they exist) has already sat down strictly before time $t$.
    353 
    354 We can now split people into $2$ types depending on which condition occurs first for them.
    355 
    356 Type A: Condition $1$ is satisfied first. This means they are waiting for one of their neighbours to sit down so they can sit down. A person is of this type if the earliest time one of their neighbours sat down is exactly $1$ less than the time they sat down. This means their $a_i$ can be any value between $1$ and $c_{t-1}$ inclusive so there are $c_{t-1}$ possible values.
    357 
    358 Type B: Condition $2$ is satisfied first. This means they are waiting for enough people to have sat down. A person is of this type if the time they sit down is at least $2$ greater than the earliest time one of their neighbours sat down. Since they did not sit down at time $t-1$, their $a_i$ must be greater than $c_{t-2}$. This means it must be between $c_{t-2}+1$ and $c_{t-1}$ inclusive, giving $c_{t-1}-c_{t-2}$ possibilities.
    359 
    360 We can iterate over all people $i$ and look at the earliest time one of their neighbours sat down to find out which type of person they are, and then compute how many valid $a_i$ there are for them.
    361 
    362 Finally, we can multiply the number of valid $a_i$ for every person, and output this modulo $676767677$.
    363 
    364 **Code (Python)**
    365 
    366 ```
    367 from itertools import accumulate
    368 MOD = 676767677
    369 
    370 for _ in range(int(input())):
    371     n, m = map(int, input().split())
    372     b = [*map(int, input().split())]
    373     cnt = [0] * m
    374     for i in range(n):
    375         cnt[b[i]] += 1
    376     p = [0, *accumulate(cnt)]
    377     ans = 1
    378     for i in range(n):
    379         if b[i] > 0:
    380             t = float("inf")
    381             for v in (i-1, i+1):
    382                 if v not in range(n): continue
    383                 t = min(t, b[v])
    384             t += 1
    385             if b[i] > t:
    386                 ans = ans * cnt[b[i] - 1] % MOD
    387             elif b[i] == t:
    388                 ans = ans * p[b[i]] % MOD
    389             else:
    390                 ans = 0
    391     print(ans % MOD)
    392 ```
    393 
    394 **Rate the problem!**
    395 
    396 **Quality**
    397 
    398 * Excellent problem
    399 * Good problem
    400 * Average problem
    401 * Bad problem
    402 * Horrible problem
    403 
    404 **Difficulty**
    405 
    406 * Trivial problem
    407 * Easy problem
    408 * Average problem
    409 * Hard problem
    410 * Impossible problem