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  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  numbers divisible by *p*, the interval [*l**i*, *r**i*] contains  numbers divisible by *p*. 18 19 Now, consider two numbers  and , with . 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 . Therefore, the probability it is can be given by . 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!  is an increasing function on positive numbers (we can see this by taking , then , which is positive when we are dealing with positive numbers). So if , then *x* ≥ *y*. 26 27 When we take log,  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, , so we cannot take another log. When can we take another log, however? We need  to be a positive number. *y**z* will always be positive, so all we need is for  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, . Remember that , so . Similarly, . 30 31 The last case is when *x* ≤ 1, *y* ≤ 1, *z* ≤ 1. Then, notice that for example, . 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.