356.md (10448B)
1 Source: https://codeforces.com/blog/entry/9210 2 3 #### [357A - Group of Students](/contest/357/problem/A "Codeforces Round 207 (Div. 2)") 4 5 In this problem you need to iterate over all possible values of passing rate from 1 to 100 and for each value calculate the sizes of two groups. 6 7 #### [357B - Flag Day](/contest/357/problem/B "Codeforces Round 207 (Div. 2)") 8 9 Let's process the dances in the given order and determine the colors of dancers' clothes. If there are no dancer from some previous dance, we can give the dances different colors arbitrarily. And if there is such dancer, we already know the color of his clothes. So, we arbitrarily distribute the other two colors between the remaning two dancers. 10 11 #### [356A - Knight Tournament](/contest/356/problem/A "Codeforces Round 207 (Div. 1)") 12 13 Let's the current fight (*l*, *r*, *x*) consists of *K* knights fighting. Then all we have to do is to find all these knights in time *O*(*K*) or *O*(*KlogN*). There are several ways to do that, let's consider some of them. 14 15 The first way is to store the numbers of all alive knights in std::set (C++) or TreeSet (Java). Then in C++ we can use lower_bound method to find the first knight in the fight that is alive, and to iterate over this set, each time moving to the next alive knight. In Java we should use subSet method. 16 17 ``` 18 set<int> alive; 19 for (int i = 0; i < n; i++) 20 alive.insert(i); 21 22 for (int i = 0; i < m; i++) { 23 int l, r, x; 24 scanf("%d%d%d", &l, &r, &x); 25 l--, r--, x--; 26 set<int>::iterator it = alive.lower_bound(l); 27 vector<int> toErase; 28 while(it != alive.end()){ 29 int cur = *it; 30 if(cur > r) 31 break; 32 if(cur != x){ 33 toErase.pb(cur); answer[cur] = x; 34 } 35 it++; 36 } 37 38 for (size_t j = 0; j < toErase.size(); j++) 39 alive.erase(toErase[j]); 40 } 41 ``` 42 43 The second way is to define array next with the following meaning: 44 45 * if knight *v* is alive, then *next*[*v*] = *v*; 46 * if knight *v* is out of tournament, next[v] points to some knight *u* (*next*[*v*] = *u*), such that there are no alive knights between *v* and *u*; 47 48 To find the first alive knight starting from the knight *v* we need to follow this links until we find the first knight *w* with *next*[*w*] = *w*. In order not to pass the same links too many times, we will use the trick known as path compression (it is used in Disjoint Set Union). Note that you should handle the case when the current knight is the last knight and is out of tournament. 49 50 ``` 51 int getNext(int v){ 52 if(next[v] == v) 53 return v; 54 return next[v] = getNext(next[v]); 55 } 56 57 ... 58 59 int cur = getNext(l); 60 while(cur <= r){ 61 if(cur == x){ 62 cur = cur + 1; 63 }else{ 64 answer[cur] = x; 65 next[cur] = cur + 1; 66 } 67 68 cur = getNext(cur); 69 } 70 ``` 71 72 #### [356B - Xenia and Hamming](/contest/356/problem/B "Codeforces Round 207 (Div. 1)") 73 74 Let's denote the length of the first string as *lenX*, the length of the second string as *lenY*. Let *L* = *LCM*(*lenX*, *lenY*). It's obvious that *L* is a period of the long strings *a* and *b*, so we can find the distance of its' prefixes of length *L* and multiply the answer by . Let's fix the position *i* in the string *x* and think about all characters from the second string it will be compared with. It it easy to conclude that it will be compared with such *y**j* that *i* ≡ *j* (*mod* *g*), where *g* = *GCD*(*lenX*, *lenY*). For each possible remainder of division by *g* and for each character *c* we can calculate *count*(*r*, *c*) — the number of characters *c* that appear in *y* in such positions *j* that *j* *mod* *g* = *r*. When calculating the Hamming distance, the character *x**i* will be compared with exactly *count*(*i* *mod* *g*, *x**i*) characters from *y* that are equal to it, all other comparisons will add one to the distance. 75 76 ``` 77 private void solve() { 78 Scanner in = new Scanner(System.in); 79 long n = in.nextLong(), m = in.nextLong(); 80 String x = in.next(), y = in.next(); 81 int lenX = x.length(), lenY = y.length(); 82 int g = gcd(lenX, lenY); 83 long L = lenX * (long)lenY / g; 84 long answer = L; 85 int[][] count = new int[g][26]; 86 for (int j = 0; j < lenY; j++) { 87 count[j % g][y.charAt(j) - 'a']++; 88 } 89 for (int i = 0; i < lenX; i++) { 90 answer -= count[i % g][x.charAt(i) - 'a']; 91 } 92 System.out.println(answer * (n * lenX / L)); 93 } 94 ``` 95 96 #### [356C - Compartments](/contest/356/problem/C "Codeforces Round 207 (Div. 1)") 97 98 In the problem you should come up with some right greedy algorithm. One of correct approaches acts as follows: 99 100 1. Firstly, it joins all "twos" and "ones" (to get "threes"). Several "ones" should be moved. 101 2. Then you should consider two cases depend on amounts of "ones" and "twos". If initially you have more "ones", you should try to join remaining after the first point "ones" into groups of three. If initially you have more "twos", you should try to join remaining after the first point "twos" into groups of three. You can get two "threes" from three "twos". 102 3. After the first point and the second point some "ones" or "twos" can remain. You shouldn't come up with common solution. Else you should just to consider all possible cases. 103 104 To solve the problem you should follow your common sense (is it greedy?). Writing naive solution (bfs search) for stress purposes is not so bad for proving correctness of your solution. 105 106 #### [356D - Bags and Coins](/contest/356/problem/D "Codeforces Round 207 (Div. 1)") 107 108 It's easy to see that bags and their relations "lies directly in" should form directed forest. Each vertex should be given value *c**i* — the number of coins in the corresponding bag. Let's denote the sum of values *c**j* in the subtree of vertex *i* as *f**i*. The following conditions should be met: 109 110 * *f**i* = *a**i* 111 * then sum of *f**i* of roots equals *s*. 112 113 It's clear that one of the bags with largest *a**i* must be the root of some tree. It's quite easy to see that the solution exists if and only if there exists a subset *a**i*1, *a**i*2, ..., *a**ik* such that *a**i*1 + *a**i*2 + ... + *a**ik* = *s* and this subset contains at least one bag with the largest *a**i*. It's obvious that it is necessary condition, the sufficiency is also easy to see: let's suppose we have such subset. Then all bags from the subset, except one of the largest, will be roots of the signle-vertex trees (i.e. *c**i* = *a**i* for them). All bags that are not in the subset we will consequentially put into the largest bag, forming the "russian doll" (this tree will be directed chain). 114 115 So, we reduced the task to the well-known subset-sum problem: from the items *a*1, *a*2, ... *a**n* find the subset with the given sum *s*. This problem is NP-Complete, and with these constraints is solved in a following way: let *T*(*i*, *j*) = 1 if it is possible to obtain sum *j* using some of the first *i* items, and *T*(*i*, *j*) = 0 otherwise. Then . The *i*-th row of this table depends only on the previous row, so we don't have to store the whole table in memory. Also we should use the fact that the values of the table are zeroes and ones, and we can use bit compression and store each row in an array of int's of size . To get the *i*-th row, we should calculate the bitwise OR of the previous row and the previous row shifted to the left by *a**i* positions. That is, we can find out whether it possible to obtain the sum *s* in approximately  operations. To find the actual way to obtain *s*, we need to use the following trick: for every possible sum *j* we will remember the value *first*(*j*) — the number of such item that after considering this item it became possible to obtain *j*. This allows us to restore the solution. 116 117 #### [356E - Xenia and String Problem](/contest/356/problem/E "Codeforces Round 207 (Div. 1)") 118 119 During the contest most of participants write the solutions that are very similar to the author's one. One of the author's solution uses hashes (but there exist solution without it), you can see short description of the solution below: 120 121 1. For each position *i* calculate with hashes the maximal value of *L**i*, such that substring *s*[(*i* - *L**i* + 1)..(*i* + *L**i* - 1)] is Gray string. Also, calculate the maximal value *P**i*, that substring *s*[(*i* - *P**i* + 1)..(*i* + *P**i* - 1)] differs from some Gray string in at most one position. You can see that *P**i* ≥ *L**i*. If *P**i* > *L**i*, also remember position and letter in the position, that differs Gray string and the substring. 122 2. You can see, that if we don't need to change letters, then the answer for the problem is , where *f*(*L*) = 12 + 32 + 72 + ... + *L*2. So, calculate an answer without changes. 123 3. Next, iterate through all positions and letters in it. What is the new answer for the problem? Look at all Gray strings that occurs in our string and touches our fixed position. After we change this position the string will not be Gray string anymore (so we should subtract the squired length of the string from our answer). Look at all Gray strings that differs in exactly fixed position from some substring of the string. If we change the letter in the position to the fixed letter, all such strings will be added to the answer (and we should add their squired lengths). 124 4. Summary, with *P**i* and *L**i* we need to calculate for each position and letter, how the answer differs if we change the letter in the position to the fixed one. For that reason we should use offline update (+=) on the segment. After the values will be calculated we can update our answer with all possible values.