582.md (12483B)
1 Source: https://codeforces.com/blog/entry/20692 2 3 **Adiv2** 4 5 To solve the problem one could just store two arrays *hused*[*j*] and *vused*[*j*] sized *n* and filled with false initially. Then process intersections one by one from 1 to *n*, and if for *i*-th intersections both *hused*[*h**i*] and *vused*[*v**i*] are false, add *i* to answer and set both *hused*[*h**i*] and *vused*[*v**i*] with true meaning that *h**i*-th horizontal and *v**i*-th vertical roads are now asphalted, and skip asphalting the intersection roads otherwise. 6 7 Such solution has *O*(*n*2) complexity. 8 9 Jury's solution: [13390628](/contest/583/submission/13390628 "Submission 13390628 by danilka.pro") 10 11 **Bdiv2** 12 13 It is always optimal to pass all the computers in the row, starting from 1-st to *n*-th, then from *n*-th to first, then again from first to *n*-th, etc. and collecting the information parts as possible, while not all of them are collected. 14 15 Such way gives robot maximal use of every direction change. *O*(*n*2) solution using this approach must have been passed system tests. 16 17 Jury's solution: [13390612](/contest/583/submission/13390612 "Submission 13390612 by danilka.pro") 18 19 **Adiv1** 20 21 Let the answer be *a*1 ≤ *a*2 ≤ ... ≤ *a**n*. We will use the fact that *gcd*(*a**i*, *a**j*) ≤ *a**min*(*i*, *j*). 22 23 It is true that *gcd*(*a**n*, *a**n*) = *a**n* ≥ *a**i* ≥ *gcd*(*a**i*, *a**j*) for every 1 ≤ *i*, *j* ≤ *n*. That means that *a**n* is equal to maximum element in the table. Let set *a**n* to maximal element in the table and delete it from table elements set. We've deleted *gcd*(*a**n*, *a**n*), so the set now contains all *gcd*(*a**i*, *a**j*), for every 1 ≤ *i*, *j* ≤ *n* and 1 ≤ *min*(*i*, *j*) ≤ *n* - 1. 24 25 By the last two inequalities *gcd*(*a**i*, *a**j*) ≤ *a**min*(*i*, *j*) ≤ *a**n* - 1 = *gcd*(*a**n* - 1, *a**n* - 1). As soon as set contains *gcd*(*a**n* - 1, *a**n* - 1), the maximum element in current element set is equal to *a**n* - 1. As far as we already know *a**n*, let's delete the *gcd*(*a**n* - 1, *a**n* - 1), *gcd*(*a**n* - 1, *a**n*), *gcd*(*a**n*, *a**n* - 1) from the element set. Now set contains all the *gcd*(*a**i*, *a**j*), for every 1 ≤ *i*, *j* ≤ *n* and 1 ≤ *min*(*i*, *j*) ≤ *n* - 2. 26 27 We're repeating that operation for every *k* from *n* - 2 to 1, setting *a**k* to maximum element in the set and deleting the *gcd*(*a**k*, *a**k*), *gcd*(*a**i*, *a**k*), *gcd*(*a**k*, *a**i*) for every *k* < *i* ≤ *n* from the set. 28 29 One could prove correctness of this algorithm by mathematical induction. For performing deleting and getting maximum element operations one could use multiset or map structure, so solution has complexity . 30 31 Jury's solution: [13390679](/contest/582/submission/13390679 "Submission 13390679 by danilka.pro") 32 33 **Bdiv1** 34 35 One could calculate matrix sized *n* × *n* *mt*[*i*][*j*] — the length of the longest non-decreasing subsequence in array *a*1, *a*2, ..., *a**n*, starting at element, greater-or-equal to *a**i* and ending strictly in *a**j* element with *j*-th index. 36 37 One could prove that if we have two matrices sized *n* × *n* *A*[*i*][*j*] (the answer for *a*1, *a*2, ..., *a**pn* starting at element, greater-or-equal to *a**i* and ending strictly in *a**j* element with *j*-th index inside last block (*a*(*p* - 1)*n* + 1, ..., *a**pn*) and *B*[*i*][*j*] (the answer for *a*1, *a*2, ..., *a**qn* ), then the multiplication of this matrices in a way 38 39  40 41 will give the same matrix but for length *p* + *q*. As soon as such multiplication is associative, next we will use fast matrix exponentiation algorithm to calculate *M*[*i*][*j*] (the answer for *a*1, *a*2, ..., *a**nT*) — matrix *mt*[*i*][*j*] raised in power *T*. The answer is the maximum in matrix *M*. Such solution has complexity . 42 43 Jury's solution (with matrices): [13390660](/contest/582/submission/13390660 "Submission 13390660 by danilka.pro") 44 45 There's an alternative solution. As soon as *a*1, *a*2, ..., *a**nT* contains maximum *n* distinct elements, it's any non-decreasing subsequence has a maximum of *n* - 1 increasing consequtive element pairs. Using that fact, one could calculate standard longest non-decreasing subsequence dynamic programming on first *n* array blocks (*a*1, ..., *a**n*2) and longest non-decreasing subsequence DP on the last *n* array blocks (*a**nT* - *n* + 1, ..., *a**nT*). All other *T* - 2*n* blocks between them will make subsegment of consequtive equal elements in longest non-decreasing subsequence. 46 47 So, for fixed *a**i*, in which longest non-decreasing subsequence of length *p* on first *n* blocks array ends, and for fixed *a**j* ≥ *a**i*, in which longest non-decreasing subsequence of length *s* on last *n* blocks array starts, we must update the answer with *p* + (*T* - 2*n*)*count*(*a**i*) + *s*, where *count*(*x*) is the number of occurences of *x* in *a*1, ..., *a**n* array. This gives us  solution. 48 49 Jury's solution (with suffix and prefix): [13390666](/contest/582/submission/13390666 "Submission 13390666 by danilka.pro") 50 51 **Cdiv1** 52 53 Let's fix *s* for every (*l*, *s*) pair. One could easily prove, that if subarray contains *a**i* element, than *a**i* must be greater-or-equal than *a**j* for every *j* such that . Let's use this idea and fix *g* = *gcd*(*n*, *s*) (it must be a divisor of *n*). To check if *a**i* can be in subarray with such constraints, let's for every 0 ≤ *r* < *g* calculate 54 55 . 56 57 It's true that every good subarray must consist of and only of . For finding all such subarrays we will use two pointers approach and for every good *a**i*, such that  is not good we will find *a**j* such that  are good and  is not good. Let  has *k* elements . Any it's subarray is superior, so it gives us arrays of length 1, 2, ..., *k* with count *k*, *k* - 1, ..., 1. As soon as sum of all *k* is not greater than *n*, we could just increase counts straightforward. There's a case when all *a**i* are good, in which we must do another increases. Next we must add to the answer only counts of length *x*, such that *gcd*(*x*, *n*) = *g*. 58 59 Solution described above has complexity *O*(*d*(*n*)*n*), where *d*(*n*) is the number of divisors of *n*. 60 61 Jury's solution: [13390645](/contest/582/submission/13390645 "Submission 13390645 by danilka.pro") 62 63 **Ddiv1** 64 65 It is a common fact that for a prime *p* and integer *n* maximum α, such that *p*α|*n*! is calculated as , where *p**w* ≤ *n* < *p**w* + 1. As soon as , the maximum α for  is calculated as . 66 67 One could see, that if we consider numbers *n*, *k* and *n* - *k* in *p*-th based numeric system, rounded-down division by *p**x* means dropping last *x* digits of its *p*-th based representation. As soon as *k* + (*n* - *k*) = *n*, every *i*-th summand in α corresponds to carry in adding *k* to *n* - *k* in *p*-th numeric system from *i* - 1-th to *i*-th digit position and is to be 0 or 1. 68 69 First, let convert *A* given in statement from 10 to *p*-th numeric system. In case, if α is greater than number of digits in *A* in *p*-th numeric system, the answer is 0. Next we will calculate dynamic programming on *A* *p*-th based representation. 70 71 *dp*[*i*][*x*][*e*][*r*] — the answer for prefix of length *i* possible equal to prefix of *A* representation (indicator *e*), *x*-th power of *p* was already calculated, and there must be carry equal to *r* from current to previous position. One could calculate it by bruteforcing all of *p*2 variants of placing *i*-th digits in *n* and *k* according to *r* and *e* and *i*-th digit of *A*, and make a translation to next state. It can be avoided by noticing that the number of variants of placing digits is always a sum of arithmetic progression and can be calculated in *O*(1). 72 73 It's highly recommended to examine jury's solution with complexity *O*(|*A*|2 + |*A*|*min*(|*A*|, α)). 74 75 Jury's solution: [13390698](/contest/582/submission/13390698 "Submission 13390698 by danilka.pro") 76 77 **Ediv1** 78 79 One could prove that the number of binary functions on 4 variables is equal to 224, and can be coded by storing a 24-bit binary mask, in which every bit is storing function value for corresponding variable set. It is true, that if *mask**f* and *mask**g* are correspond to functions *f*(*A*, *B*, *C*, *D*) and *g*(*A*, *B*, *C*, *D*), then function (*f*&g)(A, *B*, *C*, *D*) corresponds to *mask**f*&*mask**g* bitmask. 80 81 Now, we could parse expression given input into binary tree. I should notice that the number of non-list nodes of such tree is about . Now, let's calculate dynamic programming on every vertex *v* — *dp*[*v*][*mask*] is the number of ways to place symbols in expression in the way that subtree of vertex *v* will correspond to function representing by *mask*. For list nodes such dynamic is calculated pretty straightforward by considering all possible *mask* values and matching it with the variable. One could easily recalculate it for one node using calculated answers for left and right subtree in 416 operations: *dp*[*v*][*lmask*|*rmask*] + = *dp*[*l*][*lmask*] * *dp*[*r*][*rmask*]. 82 83 But all the task is how to make it faster. One could calculate *s*[*mask*], where *s*[*mask*] is equal to sum of all its submasks (the masks containing 1-bits only in positions where *mask* contains 1-bits) in 24·224 operations using following code: 84 85 ``` 86 for (int mask = 0; mask < (1 << 16); ++mask) s[mask] = dp[x][mask]; 87 for (int i = 0; i < 16; ++i) 88 for (int mask = 0; mask < (1 << 16); ++mask) 89 if (!(mask & (1 << i))) s[mask ^ (1 << i)] += s[mask]; 90 ``` 91 92 Let's calculate *sl*[*mask*] and *sr*[*mask*] for *dp*[*l*][*mask*] and *dp*[*r*][*mask*] respectively. If we will find *s*[*mask*] = *sl*[*mask*] * *sr*[*mask*], *s*[*mask*] will contain multiplications of values of pairs of masks from left and right *dp*'s, which are submasks of *mask*. As soon as we need pairs, which in bitwise OR will give us exactly *mask*, we should exclude pairs, which in bitwise OR gives a submask of *mask*, not equal to *mask*. This gives us exclusion-inclusion principle idea. The formula of this will be 93 94 , where *p* is the parity of number of bits in *mask*^*submask*. 95 96 Such sum could be calculated with approach above, but subtracting instead of adding 97 98 ``` 99 for (int mask = 0; mask < (1 << 16); ++mask) s[mask] = sl[mask] * sr[mask]; 100 for (int i = 0; i < 16; ++i) 101 for (int mask = 0; mask < (1 << 16); ++mask) 102 if (!(mask & (1 << i))) s[mask ^ (1 << i)] -= s[mask]; 103 ``` 104 105 In such way we will recalculate dynamic for one vertex in about 3·24·216 operations. 106 107 Jury's solution: [13390713](/contest/582/submission/13390713 "Submission 13390713 by danilka.pro")