432.md (3991B)
1 Source: https://codeforces.com/blog/entry/12310 2 3 ### [432A - Choosing Teams](/contest/432/problem/A "Codeforces Round 246 (Div. 2)") 4 5 In this problem you should count number of students who can participate in ACM, divide it by 3 and round down. It could be done like this: 6 7 ``` 8 int cnt = 0; 9 10 for(int i = 0; i < n; i++) 11 if (5 - a[i] >= k) 12 cnt++; 13 14 int ans = cnt / 3; 15 ``` 16 17 ### [432B - Football Kit](/contest/432/problem/B "Codeforces Round 246 (Div. 2)") 18 19 Count for every team number of games in home kit. For team *i* it equals to sum of *n* - 1 games at home and some away games with such teams which home kit color equals away kit color of team *i*. To count number of such away games you could calc array *cnt*[*j*] — number of teams with home color kit *j*. The solution could be implemented in this wasy: 20 21 ``` 22 for(int i = 0; i < n; i++) 23 cnt[ x[i] ]++; 24 25 for(int i = 0; i < n; i++) 26 { 27 ans_home[i] = n - 1; 28 ans_home[i] += cnt[ y[i] ]; 29 30 ans_away[i] = 2 * (n - 1) - ans_home[i]; 31 } 32 ``` 33 34 ### [432C - Prime Swaps](/contest/432/problem/C "Codeforces Round 246 (Div. 2)") 35 36 The solution can be described by pseudo-code: 37 38 1. Consider elements of permutation from 1 to *n* 39 2. While current element *i* is not sutiated on position *i* 40 3. Let the position of element *i* equals *pos* 41 4. Find maximum prime integer *p* which is less or equal than $pos — i + 1 42 5. Swap element in positions *pos* and *pos* - *p* + 1 43 44 It could be proved that such algorithm makes less than 4*n* swaps (for example, by implementing the algorithm) 45 46 This algorithm should be implemented optimally. You should maintain positions of elements of permutation. Swap function in author's solution: 47 48 ``` 49 void doSwap(int i, int j){ 50 int x = a[i], y = a[j]; 51 a[j] = x, pos[x] = j; 52 a[i] = y, pos[y] = i; 53 result.push_back(make_pair(i, j)); 54 } 55 ``` 56 57 ### [432D - Prefixes and Suffixes](/contest/432/problem/D "Codeforces Round 246 (Div. 2)") 58 59 The problem could be solved using different algorithms with z and prefix functions. Let's describe the solution with prefix function *p* of string *s*. 60 Calc prefix function and create a tree where vertices — integers from 0 to |*s*|, edges — from *p*[*i*] to *i* for every *i*. The root of the tree is 0. For every vertex *v* calc the number of values *p*[*i*] = *v* — that is *cnt*[*v*]. Then for every *v* calc the sum all values *cnt*[*u*] for every *u* in to subtree of *v*. 61 62 The general answer to the problem is: 63 64 Find all lenghts of the prefixes which matches the suffixes — these values are |*s*|, *p*[|*s*|], *p*[*p*[|*s*|]], *p*[*p*[*p*[|*s*|]]]... For every such length *L* the answer to the problem is *sum*[*L*] + 1. 65 66 ### [432E - Square Tiling](/contest/432/problem/E "Codeforces Round 246 (Div. 2)") 67 68 This is popular test 6 :) 69 70 ``` 71 13 5 72 73 AAAAA 74 AAAAA 75 AAAAA 76 AAAAA 77 AAAAA 78 BBBBB 79 BBBBB 80 BBBBB 81 BBBBB 82 BBBBB 83 AAACA 84 AAABB 85 AAABB 86 ``` 87 88 The problem could be solved in a standard way — try to fill the table from the first cell to the last and try to put the miminum letter. 89 90 Consider the first row. Obviously it begins from some letters A (to be exact *min*(*n*, *m*) letters A). When we put some letters A in the first row, we should put several letters A in some next rows to make a square. The next letter could be only B. 91 92 Describe the solution in general. Assume that we have already considered some rows. Consider row *i*. Some cells in this row could be already painted. Consider unpainted cells from left to the right. For every such cell consider its color from A to Z. Two cases should be considered: 93 94 1. Put in this cell the minimum possible letter (neighbours have no such letter) 95 2. If the previous cell in this row was not painted at the beginning of considering row *i*, now it is already painted. We should try to merge the current cell with the square of the previous cell. 96 97 Choose the best case from these cases. Try to get the answer on test *n* = 13 *m* = 5 to understand the algorithm better.