840.md (9713B)
1 Source: https://codeforces.com/blog/entry/53943 2 3 **Generous Kefa — Adiv2** 4 **(Authors: [Mediocrity](/profile/Mediocrity "Candidate Master Mediocrity"), [totsamyzed](/profile/totsamyzed "Candidate Master totsamyzed"))** 5 6 Consider each balloon color separately. For some color *c*, we can only assign all balloons of this color to Kefa's friends if *c* ≤ *k*. Because otherwise, by pigeonhole principle, at least one of the friends will end up with at least two balloons of the same color. 7 This leads us to a fairly simple solution: calculate number of occurrences for each color, like, *cnt**c*. 8 Then just check that *cnt**c* ≤ *k* for each possible *c*. 9 **Complexity: *O*(*N* + *K*)** 10 11 **Godsend — Bdiv2** 12 **(Author: [Mediocrity](/profile/Mediocrity "Candidate Master Mediocrity"))** 13 14 First player wins if there is at least one odd number in the array. Let's prove this. 15 Let's denote total count of odd numbers at *T*. 16 There are two cases to consider: 17 1) *T* is odd. First player takes whole array and wins. 18 2) *T* is even. Suppose that position of the rightmost odd number is *pos*. Then the strategy for the first player is as follows: in his first move, pick subarray [1;*pos* - 1]. The remaining suffix of the array will have exactly one odd number that second player won't be able to include in his subarray. So, regardless of his move, first player will take the remaining numbers and win. 19 **Complexity: *O*(*N*)** 20 21 **Leha and function — Adiv1** 22 **(Author: [Mediocrity](/profile/Mediocrity "Candidate Master Mediocrity"))** 23 24 First of all, let's understand what is the value of *F*(*N*, *K*). 25 For any subset of size *K*, say, *a*1, *a*2...*a**K*, we can represent it as a sequence of numbers *d*1, *d*2...*d**K* + 1, so that *d*1 = *a*1, *d*1 + *d*2 = *a*2, ..., . 26 We're interested in *E*[*d*1], expected value of *d*1. Knowing some basic facts about expected values, we can derive the following: 27 *E*[*d*1 + ... + *d**K* + 1] = *N* + 1 28 *E*[*d*1] + ... + *E*[*d**K* + 1] = (*K* + 1)·*E*[*d*1] 29 And we immediately get that . 30 We could also get the formula by using the Hockey Stick Identity, as [Benq](/profile/Benq "Grandmaster Benq") stated in his comment. 31 Now, according to rearrangement inequality,  is maximized when *A* is increasing and *B* is decreasing. 32 **Complexity: *O*(*NlogN*)** 33 34 **Leha and another game about graph — Bdiv1** 35 **(Authors: [244mhq](/profile/244mhq "Unrated, 244mhq"), [totsamyzed](/profile/totsamyzed "Candidate Master totsamyzed"))** 36 37 Model solution uses the fact that the graph is connected. 38 We'll prove that "good" subset exists iff - 1 values among *d**i* can be changed to 0 / 1 so that  is even. If the sum can only be odd, there is no solution obviously (every single valid graph has even sum of degrees). Now we'll show how to build the answer for any case with even sum. 39 First of all, change all - 1 values so that the sum becomes even. 40 Then let's find any spanning tree and denote any vertex as the root. The problem is actually much easier now. 41 Let's process vertices one by one, by depth: from leaves to root. Let's denote current vertex as *cur*. 42 There are two cases: 43 1) *d**cur* = 0 44 In this case we ignore the edge from *cur* to *parent**cur* and forget about *cur*. Sum remains even. 45 2) *d**cur* = 1 46 In this case we add the edge from *cur* to *parent**cur* to the answer, change *d**parent**cur* to the opposite value and forget about *cur*. As you can see, sum changed its parity when we changed *d**parent**cur*, but then it changed back when we discarded *cur*. So, again, sum remains even. 47 Using this simple manipulations we come up with final answer. 48 **Complexity: *O*(*N* + *M*)** 49 50 **On the bench — Cdiv1** 51 **(Authors: [Mediocrity](/profile/Mediocrity "Candidate Master Mediocrity"), [totsamyzed](/profile/totsamyzed "Candidate Master totsamyzed"))** 52 53 Let's divide all numbers into groups. Scan all numbers from left to right. Suppose that current position is *i*. If *group**i* is not calculated yet, *i* forms a new group. Assign unique number to *group**i*. Then for all *j* such that *j* > *i* and *a*[*j*]·*a*[*i*] is a perfect square, make *group**j* equal to *group**i*. Now we can use dynamic programming to calculate the answer. 54 *F*(*i*, *j*) will denote the number of ways to place first *i* groups having *j* "bad" pairs of neighbors. 55 Suppose we want to make a transition from *F*(*i*, *j*). Let's denote size of group *i* as *size*, and total count of numbers placed before as *total*. 56 We will iterate *S* from 1 to *min*(*size*, *total* + 1) and *D* from 0 to *min*(*j*, *S*). 57 *S* is the number of subsegments we will break the next group in, and *D* is the number of currently existing "bad" pairs we will eliminate. 58 This transition will add *T* to *F*(*i* + 1, *j* - *D* + *size* - *S*) (*D* "pairs" eliminated, *size* - *S* new pairs appeared after placing new group). 59 *T* is the number of ways to place the new group according to *S* and *D* values. 60 Actually it's . Why? Because there are  ways to break group of size *size* into *S* subsegments. 61  ways to select those *D* "bad" pairs out of existing *j* we will eliminate. 62 And  ways to choose placements for *S* - *D* subsegment (other *D* are breaking some pairs so their positions are predefined). 63 After all calculations, the answer is *F*(*g*, 0), where *g* is the total number of groups. 64 **Complexity: O(N^3)** 65 66 **Destiny — Ddiv1** 67 **(Authors: [Mediocrity](/profile/Mediocrity "Candidate Master Mediocrity"), [totsamyzed](/profile/totsamyzed "Candidate Master totsamyzed"))** 68 69 We will use classical divide and conquer approach to answer each query. 70 Suppose current query is at subsegment [*L*;*R*]. Divide the original array into two parts: [1;*mid*] and [*mid* + 1;*N*], where . If our whole query belongs to the first or the second part only, discard the other part and repeat the process of division. Otherwise, *L* ≤ *mid* ≤ *R*. We claim that if we form a set of *K* most frequent values on [*L*;*mid*] and *K* most frequent values on [*mid* + 1;*R*], one of the values from this set will be the answer, or there is no suitable value. 71 72 *K* most frequent values thing can be precalculated. Run recursive function *build*(*node*, *L*, *R*). First, like in a segment tree, we'll run this function from left and right son of *node*. 73 Then we need *K* most frequent values to be precalculated for all subsegments [*L*1;*R*1], such that *L* ≤ *L*1 ≤ *R*1 ≤ *R* and at least one of *L*1 and *R*1 is equal to . 74 75 We will consider segments such that their left border is *mid* in the following order: [*mid*;*mid*], [*mid*;*mid* + 1], ...[*mid*;*R*]. If we already have *K* most frequent values and their counts for [*mid*, *i*], it's rather easy to calculate them for [*mid*, *i* + 1]. We update the count of *a**i* + 1 and see if anything should be updated for the new list of most frequent values. 76 77 Exactly the same process happens to the left side of *mid*: we are working with the subsegments in order [*mid*;*mid*], [*mid* - 1;*mid*], ..., [*L*;*mid*]. 78 79 Now, having all this data precalculated, we can easily run divide and conquer and get the candidates for being the solution at any [*L*;*R*] segment. Checking a candidate is not a problem as well: we can save all occurrences in the array for each number and then, using binary search, easily answer the following questions: "How many times *x* appears from *L* to *R*?". 80 81 **Complexity: O(KNlogN)** 82 83 **In a trap — Ediv1** 84 **(Author: [Mediocrity](/profile/Mediocrity "Candidate Master Mediocrity"))** 85 86 The path from *u* to *v* can be divided into blocks of 256 nodes and (possibly) a single block with less than 256 nodes. We can consider this last block separately, by iterating all of its nodes. 87 Now we need to deal with the blocks with length exactly 256. They are determined by two numbers: *x* — last node in the block, and *d* — 8 highest bits. We can precalculate this values and then use them to answer the queries. 88 Let's now talk about precalculating *answer*(*x*, *d*). Let's fix *x* and 255 nodes after *x*. It's easy to notice that lowest 8 bits will always be as following: 0, 1, ..., 255. We can xor this values: 0 with *a**x*, 1 with *a**next**x* and so on, and store the results in a trie. Now we can iterate all possible values of *d* (from 0 to 255) and the only thing left is to find a number stored in a trie, say *q*, such that *q* xor 255·*d* is maximized. 89 90 **Complexity: O(NsqrtNlogN)**