599.md (5844B)
1 Source: https://codeforces.com/blog/entry/21685 2 3 Problem A. 4 5 Everything that you needed to do — solve some similar cases. 6 7 You need to check the following cases: 8 9 * Home  the first shop  the second shop  home 10 * Home  the first shop  the second shop  the first shop  home 11 * Home  the second shop  home  the first shop  home 12 * Home  the second shop  the first shop  the second shop  home 13 14 Time: *O*(1) 15 16 Problem B. 17 18 First of all, you should read the statement carefully. Then, for every element 1 ... *N* create a list of integers from what we can get this number. 19 20 After that you have to check some cases, before that create a special mark for answer *Ambiguity*: 21 22 Let current element of the given array is *b**i* 23 24 * If two or more elements exist from which it's possible to get *b**i*, then use your special mark that answer is *Ambiguity* 25 * If no elements exist from which it's possible to get *b**i*, then print *Impossible* 26 * If only one element exists from which it's possible to get *b**i* just change *b**i* to the value of this element 27 28 Finally, if you marked your special mark then print *Ambiguity*, else print *Possible* and correct answer. 29 30 Time: *O*(*N*) 31 32 Problem C. 33 34 Let's take a minute to see how the best answer should look like. 35 36 Let *H**i* be a sorted sequence of *h**i*. Let ***E*** — set of indices of the last elements of each block. Then  *e*  ***E***, first *e* sorted elements of sequence *h**i* are equal to the first *e* elements of the sequence *H**j*. 37 38 So, it is not difficult to notice that the size of ***E*** is the answer for the problem. 39 40 Firstly, we need to calculate two arrays: *prefmax* and *suffmin*, where *prefmax**i* — maximum between *a*1, *a*2, ..., *a**i*, and *suffmin**i* — minimum between *a**i*, *a**i* + 1, ..., *a**n*. 41 42 If you want to get the answer, just calculate the number of indices *i* that *prefmax**i* ≤ *suffmin**i* + 1. 43 44 Time: *O*(*N*) 45 46 Problem D. 47 48 First of all, let's solve this problem for *n* ≤ *m*, and then just swap *n* and *m* and print the answer. Important! Not to print squares twice! 49 50 We can use this formula for fixed *n* & *m* (*n* ≤ *m*) for calculating the value of *x*.  51 52 Then  53 54 Using the sum squares and the sum of the first *k* numbers we can easily solve this problem. 55 56 Getting 6*x* = 6*n*2 * *m* - 3(*n*2 + *n*3 - *nm* - *n*2) + 2*n*3 - 3*n*3 + *n* = 3 * *m* * *n*2 + 3 * *m* * *n* - *n*3 + *n* 57 58 As we solved this task for *n* ≤ *m* the 3*n*2 * *m* = ≈ *n*3, it means that *n* is not greater than . 59 60 Time:  61 62 Problem E. 63 64 The solution for this problem is dynamic programming. 65 66 Let *f**root*, *mask* is the number of ways to build a tree with root in vertex *root* using vertices from the mask *mask* and all restrictions were met. For convenience we shall number the vertices from zero. 67 68 The answer is *f*0, 2*n* - 1. 69 70 Trivial states are the states where a mask has only one single bit. In such cases *f**root*, *mask* = 1. 71 72 Let's solve this task recursively with memorization. To make the transition, we need to choose some kind of mask *newMask*, which is **necessarily is the submask** of mask *mask*. Then we should try to find new root *newRoot* in mask *newMask*. Also, in order not to count the same tree repeatedly impose conditions on the mask *newMask*. Namely, we shall take only such masks *newMask*, in which the senior bit (not in charge of the *root*) coincides with a senior bit (not in charge of the *root*) of the mask *mask*. After that, you need to check the fulfillment of all conditions to the edges and to the lca. If everything is OK, update . Where  means ***xor***. 73 74 What about checking lca, it's possible to do it in time *O*(*N*2) — previously memorized lca for each pair or in the worst case in time *O*(*Q*) just iterating through all pairs of vertices, for which some vertex *v* is lca. 75 76 Time: *O*(3*N*·*N*3) or *O*(3*N*·*N*·*Q*)