313.md (3882B)
1 Source: https://codeforces.com/blog/entry/7826 2 3 [313A - Ilya and Bank Account](/contest/313/problem/A "Codeforces Round 186 (Div. 2)") 4 5 This problem is the easiest one. You need to use only div and mod functions. If *n*>0, then answer is *n*, else you need to delete one of two digits. 6 7 For better understanding you can look at [solution](//codeforces.com/contest/313/submission/3794963). 8 9 [313B - Ilya and Queries](/contest/313/problem/B "Codeforces Round 186 (Div. 2)") 10 11 Precalculate some array *A**i*, that *A**i* = 1, if *s**i* = *s**i* + 1, else *A**i* = 0. Now for any query (*l*, *r*), you need to find sum of *A**i*, that (*l* ≤ *i* < *r*). It is standart problem. For solving this problem you can precalcutate some another array Sum, where *Sum**i* = *A*1 + *A*2 + ... + *A**i*. Then sum of interval (*l*, *r*) is Sum_r — Sum_{l-1}. 12 13 For better understanding you can look at [solution](//codeforces.com/contest/313/submission/3798187). 14 15 [313C - Ilya and Matrix](/contest/313/problem/C "Codeforces Round 186 (Div. 2)") 16 17 At the start sort array. Let *C**i* — number of times of entering the number in *A**і* optimal placement. Answer is sum of *A**i* * *C**i* for all *i* (1 ≤ *i* ≤ 4*n*). If we look at the array *C*, we can see that for maximal element *C* = *n* + 1 (for array with size 4*n*), then for second, third and fourth maximum elements *C* = *n*. On this basis we can see, that for array with non-increasing order answer calculate like *Sum*(1, 1) + *Sum*(1, 4) + *Sum*(1, 16) + ... + *Sum*(1, 4*n*). So, for solve this problem you have to know only sort. 18 19 For better understanding you can look at [solution](//codeforces.com/contest/313/submission/3798779) 20 21 [313D - Ilya and Roads](/contest/313/problem/D "Codeforces Round 186 (Div. 2)") 22 23 To solve this problem you need to use dynamic programming. Let *Full**i*, *j* — minimal cost of covering interval (*i*, *j*). Fix left border and move right. You can solve this subtask with complexity *O*(*nm*) or *O*(*nmlogn*). Now we need to solve the standart problem of dynamic programming. Cover *K* points with intervals that have not intersect. This problem with square dynamic. *dp**i*, *j* — minimal cost of covering *j*-points, if you look some prefix length *i*. Answer for all problem is minimal integer from *dp**i*, *j*, (*k* ≤ *j* ≤ *n*). 24 To solve second part: 25 26 1) *dp**i* + 1, *j* = *min*(*dp**i* + 1, *j*, *dp**i*, *j*) — skip point with number *i* + 1 27 28 2) *dp**k*, *j* + *len* = *min*(*dp**k*, *j* + *len*, *dp**i*, *j* + *Cost*); *Cost* — cost of interval with length *len*, that ending at point k. We precalculate *Cost* at first part of solution. 29 30 For better understanding you can look at [solution](//codeforces.com/contest/313/submission/3800042) 31 32 [313E - Ilya and Two Numbers](/contest/313/problem/E "Codeforces Round 186 (Div. 2)") 33 34 Author solution is harder than that which is offered by [MrDindows](/profile/MrDindows "Candidate Master MrDindows"). It is solution of [MrDindows](/profile/MrDindows "Candidate Master MrDindows"). 35 36 1) Get the number of our sequences in sorted by frequencies. Thus from the first sequence (hereinafter — the first type) — in a direct order from the second — to the contrary. 37 38 2) These numbers are put on the stack, where if, recording onto the stack of the second type, we find the number at the top of the first type, then this pair of extract and add to the answer. 39 40 3) At the end, obviously the stack we can find a number of properties of the second type and the first bottom — on. Then their grouping in response pairs with the start and end. 41 42 For better understanding you can look at [solution](//codeforces.com/contest/313/submission/3803538). 43 44 *Sorry* *for* *waiting*.