489.md (3759B)
1 Source: https://codeforces.com/blog/entry/14741 2 3 ### [489A - SwapSort](/contest/489/problem/A "Codeforces Round 277.5 (Div. 2)") 4 5 All you need is to swap the current minimum with the *i*-th element each time. You can do it with the code like: 6 7 ``` 8 for (int i = 0; i < n; i++) 9 { 10 int j = i; 11 for (int t = i; t < n; t++) 12 if (a[j] > a[t]) 13 j = t; 14 if (i != j) 15 answer.push_back(make_pair(i, j)); 16 swap(a[i], a[j]); 17 } 18 ``` 19 20 This solution makes at most n-1 swap operation. Also `if (i != j)` is not necessary. 21 22 ### [489B - BerSU Ball](/contest/489/problem/B "Codeforces Round 277.5 (Div. 2)") 23 24 There are about 100500 ways to solve the problem. You can find maximal matching in a bipartite graph boys-girls, write dynamic programming or just use greedy approach. 25 26 Let's sort boys and girls by skill. If boy with lowest skill can be matched, it is good idea to match him. It can't reduce answer size. Use girl with lowest skill to match. So you can use code like: 27 28 ``` 29 sort(boys.begin(), boys.end()); 30 sort(girls.begin(), girls.end()); 31 32 for (int i = 0; i < n; i++) 33 for (int j = 0; j < m; j++) 34 if (abs(boys[i] - girls[j]) <= 1) 35 { 36 girls[j] = 1000; 37 result++; 38 break; 39 } 40 ``` 41 42 ### [489C - Given Length and Sum of Digits...](/contest/489/problem/C "Codeforces Round 277.5 (Div. 2)") 43 44 There is a greedy approach to solve the problem. Just try first digit from lower values to higher (in subtask to minimize number) and check if it is possible to construct a tail in such a way that it satisfies rule about length/sum. You can use a function `can(m,s)' that answers if it is possible to construct a sequence of length *m* with the sum of digits *s*: 45 46 ``` 47 bool can(int m, int s) 48 { 49 return s >= 0 && s <= 9 * m; 50 } 51 ``` 52 53 Using the function `can(m,s)` you can easily pick up answer digit-by-digit. For the first part of problem (to minimize number) this part of code is: 54 55 ``` 56 int sum = s; 57 for (int i = 0; i < m; i++) 58 for (int d = 0; d < 10; d++) 59 if ((i > 0 || d > 0 || (m == 1 && d == 0)) && can(m - i - 1, sum - d)) 60 { 61 minn += char('0' + d); 62 sum -= d; 63 break; 64 } 65 ``` 66 67 The equation `(i > 0 || d > 0 || (m == 1 && d == 0))` is needed to be careful with leading zeroes. 68 69 ### [489D - Unbearable Controversy of Being](/contest/489/problem/D "Codeforces Round 277.5 (Div. 2)") 70 71 Let's iterate through all combinations of *a* and *c* just two simple nested loops in *O*(*n*2) and find all candidates for *b* and *d* inside. To find candidates you can go through all neighbors of *a* and check that they are neighbors of *c*. Among all the candidates you should choose two junctions as *b* and *d*. So just use <https://en.wikipedia.org/wiki/Combination> All you need is to add to the answer , where *r* is the number of candidates (common neighbors of *a* and *c*). The code is: 72 73 ``` 74 for (int a = 0; a < n; a++) 75 for (int c = 0; c < n; c++) 76 if (a != c) 77 { 78 int r = 0; 79 for (int b = 0; b < nxt[a].size(); b++) 80 if (nxt[a][b] != a && nxt[a][b] != c && g[nxt[a][b]][c]) 81 r++; 82 result += r * (r - 1) / 2; 83 } 84 ``` 85 86 It is easy to see that the total complexity is *O*(*nm*), because of sum of number of neighbors over all junctions is exactly *m*. 87 88 **P.S. I'll be grateful if some of you will write editorial of E and F in comments because of now I should leave Codeforces and will return back some hours later. Thank you for participation!**