codeforces-scrape

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

621.md (6761B)


      1 Source: https://codeforces.com/blog/entry/23196
      2 
      3 [621A - Мокрая Акула и чётность](/contest/621/problem/A "Codeforces Round 341 (Div. 2)")
      4 
      5 First, if the sum of all the numbers is already even, then we do nothing. Otherwise, we remove the smallest odd number. Since, if the sum is odd, we need to remove a number with the same parity to make the sum even. Notice it's always bad to remove more odd numbers, and it does nothing to remove even numbers.
      6 
      7 [621B - Мокрая Акула и слоны](/contest/621/problem/B "Codeforces Round 341 (Div. 2)")
      8 
      9 Let's start with two bishops (x1, y1) and (x2, y2). Notice that if (x1, y1) attacks (x2, y2), either x1 + y1 == x2 + y2 OR x1 — y1 == x2 — y2. So, for each bishop (x, y), we will store x + y in one map and x — y in another map.
     10 
     11 [621C - Мокрая Акула и цветы](/contest/621/problem/C "Codeforces Round 341 (Div. 2)")
     12 
     13 Let *f*(*x*) be the probability that the product of the number of flowers of sharks *x* and ![](https://espresso.codeforces.com/5e2b09ec04582642db8dab50463175c439561e27.png) is divisible by *p*.
     14 
     15 We want the expected value of the number of pairs of neighbouring sharks whose flower numbers are divisible by *p*. From linearity of expectation, this is equal to the probabilities that each pair multiplies to a number divisible by *p*, or *f*(0) + *f*(1) + ... + *f*(*n*). (Don't forget about the wrap-around at *n*)
     16 
     17 Now, for each pair of neighbouring sharks, we need to figure out the probability that their product is divisible by *p*. Consider an interval [*l**i*, *r**i*]. How many numbers in this interval are divisible by *p*? Well, it is easier if we break the interval [*l**i*, *r**i*] up into [1, *r**i*] - [1, *l**i* - 1]. Since 1, 2, ..., *x* contains ![](https://espresso.codeforces.com/2c7ec8bbd24c7db9cee6086303bb738c3ccc65ab.png) numbers divisible by *p*, the interval [*l**i*, *r**i*] contains ![](https://espresso.codeforces.com/26cd9bba9ff58551487e352e120c93ceeec2a380.png) numbers divisible by *p*.
     18 
     19 Now, consider two numbers ![](https://espresso.codeforces.com/21f2f0a210879e470925b27d940384848be41fad.png) and ![](https://espresso.codeforces.com/0097ce8a0600746a7baf097bbad04878f7cd400c.png), with ![](https://espresso.codeforces.com/405a1c3a302fdc07e2cbee37160e7618deecd006.png). Let *a**i* be the number of integers divisible by *p* in the interval [*l**i*, *r**i*], and define *a**j* similarly. Now what's the probability that *f**i*·*f**j* is divisible by *p*? We can count the opposite: the probability that *f**i*·*f**j* is not divisible by *p*. Since *p* is a prime, this means neither *f**i* nor *f**j* is divisible by *p*. The number of integers in [*l**i*, *r**i*] not divisible by *p* is *r**i* - *l**i* + 1 - *a**i*. Similar for *j*. Therefore, the probability *f**i*·*f**j* is not divisible by *p* is given by ![](https://espresso.codeforces.com/93dd84040f16cae8b8944558fd38e37747c58d09.png). Therefore, the probability it is can be given by ![](https://espresso.codeforces.com/0728cb2cd42d1f8d4500191fd059a91b4f489ffd.png). Now, just sum over this for all *i*.
     20 
     21 [621D - Крыса Квеш и сыр](/contest/621/problem/D "Codeforces Round 341 (Div. 2)")
     22 
     23 The tricky Rat Kwesh has finally made an appearance; it is time to prepare for some tricks. But truly, we didn't expect it to be so hard for competitors though. Especially the part about taking log of a negative number.
     24 
     25 We need a way to deal with *x**y**z* and *x**yz*. We cannot directly compare them, 200200200 is way too big. So what we do? Take log! ![](https://espresso.codeforces.com/32c31c1837a97fbf3b6bb5a9452cd00fd8e642a4.png) is an increasing function on positive numbers (we can see this by taking ![](https://espresso.codeforces.com/2d418837712467cab6306acb0f88f3e70f1f6c8a.png), then ![](https://espresso.codeforces.com/2e71b0d70562b3fd73367610c687b6b658af8fe2.png), which is positive when we are dealing with positive numbers). So if ![](https://espresso.codeforces.com/e8a3c54443e888c9867205a255a8a25715c0d213.png), then *x* ≥ *y*.
     26 
     27 When we take log, ![](https://espresso.codeforces.com/c4fb1ef9a0a6c04b6e3a0f743adfabbcb8730eb4.png) But *y**z* can still be 200200, which is still far too big. So now what can we do? Another log! But is it legal? When *x* = 0.1 for example, ![](https://espresso.codeforces.com/e86f9a40da7bfd18d82b5a734eb02eb39eda0776.png), so we cannot take another log. When can we take another log, however? We need ![](https://espresso.codeforces.com/c50a6cb37fed06a2a8e24894cff8e980eb381dd2.png) to be a positive number. *y**z* will always be positive, so all we need is for ![](https://espresso.codeforces.com/fde89a464af67cb3a90ae1d41130fa5c6fcd7623.png) to be positive. This happens when *x* > 1. So if *x*, *y*, *z* > 1, everything will be ok.
     28 
     29 There is another good observation to make. If one of *x*, *y*, *z* is greater than 1, then we can always achieve some expression (out of those 12) whose value is greater than 1. But if *x* < 1, then *x**a* will never be greater than 1. So if at least one of *x*, *y*, *z* is greater than 1, then we can discard those bases that are less than or equal to 1. In this case, ![](https://espresso.codeforces.com/4e78e2eecd027458a95a9697a6fb181e9fba2fe4.png). Remember that ![](https://espresso.codeforces.com/2d02463aeb8259d13221aedf50278cad1676b9b1.png), so ![](https://espresso.codeforces.com/1bf33799f2aae28f2fdf2173b94284b2ec6183d7.png). Similarly, ![](https://espresso.codeforces.com/255c902e61dbf057205fa87a8149eb86947a89c5.png).
     30 
     31 The last case is when *x* ≤ 1, *y* ≤ 1, *z* ≤ 1. Then, notice that for example, ![](https://espresso.codeforces.com/c39eb02b27c939e7e9d16dc1de403e0c6b8a3171.png). But the denominator of this fraction is something we recognize, because 10 / 3 > 1. So if all *x*, *y*, *z* < 1, then it is the same as the original problem, except we are looking for the minimum this time.
     32 
     33 [621E - Мокрая Акула и блоки](/contest/621/problem/E "Codeforces Round 341 (Div. 2)")
     34 
     35 First, let us build an X by X matrix. We will be applying matrix exponentiation on this matrix. For each modulo value T from 0 to X — 1, and each value in the array with index i between 1 and n, we will do: matrix[T][(10 * T + arr[i]) % X]++. This is because, notice that for each block we allow one more way to go between a modulo value T, and (10 * T + arr[i]) % X. We are multiplying T by 10 because we are "left-shifting" the number in a way (i.e. changing 123 -> 1230), and then adding arr[i] to it. Notice that this basically simulates the concatenation that Wet Shark is conducting, without need of a brute force dp approach.