525.md (5780B)
1 Source: https://codeforces.com/blog/entry/17119 2 3 ## [525A — Vitaliy and Patty](https://codeforces.com/problemset/problem/525/A) 4 5 To solve this problem we need to use array *cnt*[]. In this array we will store number of keys of every type, which we already found in rooms, but didn't use. Answer will store in variable ans. 6 7 Now, we iterate on string. If current element of string *s**i* is lowercase letter (key), we make *cnt*[*s**i*]++. Else if current element of string *s**i* uppercase letter (door) and *cnt*[*tolower*(*s**i*)] > 0, we make *cnt*[*tolower*(*s**i*)]--, else we make *ans*++. It remains only to print ans. 8 9 Asymptotic behavior of this solution — O(|*s*|), where |*s*| — length of string *s*. 10 11 ## [525B — Pasha and String](https://codeforces.com/problemset/problem/525/B) 12 13 At first we need to understand next fact — it doesn't matter in wich order make reverses, answer will be the same for all orders. 14 15 Let's numerate elements of string from one. To solve given problem we need to count how many reverses will begin in every position of string. Then we need to count array *sum*[]. In *sum*[*i*] we need to store count of reverses of substrings, which begin in positions which not exceeding *i*. 16 17 Now iterate for *i* from 1 to *n* / 2 and if *sum*[*i*] is odd swap *s**i* and *s**n* - *i* + 1. After that it remains only to print string *s*. 18 19 Asymptotic behavior of this solution — O(*n* + *m*), where *n* — length of string *s*, *m* — count of reverses. 20 21 ## [525C — Ilya and Sticks](https://codeforces.com/problemset/problem/525/C) 22 23 This problem can be solved with help of greedy. At first count array *cnt*[]. In *cnt*[*i*] will store how many sticks with length *i* we have. 24 25 Now iterate for len from maximal length of sticks to minimal. If *cnt*[*len*] is odd and we have sticks with length *len* - 1 (that is *cnt*[*len* - 1] > 0), make *cnt*[*len*]-- and *cnt*[*len* - 1]++. If *cnt*[*len*] is odd and we have no sticks with length *len* - 1 (that is *cnt*[*len* - 1] = 0), make *cnt*[*len*]--. 26 27 In this way we properly done all sawing which we need and guaranteed that all *cnt*[*len*] is even. After that iterate similary on length of sticks and greedily merge pairs from 2 sticks with the same length in fours. It will be length of sides of sought-for rectangles, left only summarize their squares in answer. In the end can left 2 sticks without pair, we must not consider them in answer. 28 29 For example, if *cnt*[5] = 6, *cnt*[4] = 4, *cnt*[2] = 4, we need to merge this sticks in following way — (5, 5, 5, 5), (5, 5, 4, 4), (4, 4, 2, 2). Two sticks with length 2 are left, we must not count them. 30 31 Asymptotic behavior of this solution — O(*n* + *maxlen* - *minlen*), where *n* — count of sticks, *maxlen* — maximal length of stick, *minlen* — minimal length of stick. 32 33 ## [525D — Arthur and Walls](https://codeforces.com/problemset/problem/525/D) 34 35 To solve this problem we need to observe next fact. If in some square whith size 2 × 2 in given matrix there is exactly one asterisk, we must change it on dot. That is if in matrix from dots and asterisks is not square 2 × 2 in which exactly one asterisk and three dots, then all maximum size of the area from dots connected by sides represent rectangles. 36 37 Now solve the problem with help of bfs and this fact. Iterate on all asterisks in given matrix and if only this asterisk contains in some 2 × 2 square, change this asterisk on dot and put this position in queue. Than we need to write standart bfs, in which we will change asterisks on dots in all come out 2 × 2 squares with exactly one asterisk. 38 39 Asymptotic behavior of this solution — O(*n* * *m*), where *n* and *m* sizes of given matrix. 40 41 ## [525E — Anya and Cubes](https://codeforces.com/problemset/problem/525/E) 42 43 To solve this problem we need to use meet-in-the-middle. At first sort given array in increasing order and divide it in two parts. In first part must be first *n* / 2 elements, in second part — other. 44 45 Iterate all submasks of all masks of elements from first part. That is iterate which cubes from first part we take and on which from them we paste exclamation marks. In this way we iterated all possible sums, which we can get with cubes from first part. Let for current submask we get sum sum_lf and use *t**lf* exclamation marks. To store all such sums we use associative arrays *map* < *long* *long* > *cnt*[*k* + 1], where *k* — count of exclamation marks which we have in the beginning. 46 47 After that similary iterate all submasks of all masks of elements from second part. Let for current submask sum is *sum**rg* and number of used exclamation marks is *t**rg*. Then from first part we need to get sum (*s* - *sum**rg*) and we can use only (*k* - *t**rg*) exclamation marks, where *s* — sum which we must get by condition of the problem. Then iterate how many exclamation marks we will use in first part (let it be variable cur) and increase answer on *cnt*[*cur*][*s* - *sum**rg*]. To accelerate our programm we may increase answer only if *cnt*[*cur*].*count*(*s* - *sum**rg*) = *true*. 48 49 For submasks in iterate we can cut off iteration on current sum for submask (it must be less or equal to given *s*) and on current count of exclamation marks (it must be less or equal to given *k*). Also we should not paste exclamation marks on cubecs with numbers larger than 18, because 19! more than 1016 — maximal value of *s*. 50 51 Asymptotic behavior of this solution — O(3((*n* + 1) / 2) * *log*(*maxcnt*) * *k*), where *n* — count of cubes, *maxcnt* — maximal size of associative array, *k* — count of exclamation marks.