1107.md (7620B)
1 Source: https://codeforces.com/blog/entry/64833 2 3 Continuing with the theme from last time, here's a quick writeup of my approaches: 4 5 #### [1107A - Digits Sequence Dividing](/contest/1107/problem/A "Educational Codeforces Round 59 (Rated for Div. 2)") 6 7 Since we just want to make two numbers such that the first number is smaller than the second, our best bet is to use only the first digit for the first number and the rest of the digits for the second number. Note that since the numbers can have up to 300 digits we shouldn't actually evaluate the second number. Instead, since the digits only include 1 through 9, we can handle that case by checking the number of digits. Code: [49002957](/contest/1107/submission/49002957 "Submission 49002957 by neal") 8 9 #### [1107B - Digital root](/contest/1107/problem/B "Educational Codeforces Round 59 (Rated for Div. 2)") 10 11 The key observation is that the digital root of an integer *k* is the single-digit number 1 ≤ *d* ≤ 9 such that . You can prove this by noticing that  for all *p*. Once we observe this, finding the *k*-th number is very simple; see the code: [48993705](/contest/1107/submission/48993705 "Submission 48993705 by neal") 12 13 #### [1107C - Brutality](/contest/1107/problem/C "Educational Codeforces Round 59 (Rated for Div. 2)") 14 15 Since we are only allowed to push the same button *k* times in a row, let's do a two-pointer sweep to find all segments of consisting of just one button. Within each segment, we'll sort and take the *k* highest values. See the code for details on the two-pointer sweep: [48994498](/contest/1107/submission/48994498 "Submission 48994498 by neal") 16 17 #### [1107D - Compression](/contest/1107/problem/D "Educational Codeforces Round 59 (Rated for Div. 2)") 18 19 After some tinkering with the given condition, we notice that an *x*-compression is possible iff *x* divides *n* and the *n* × *n* matrix is divisible into *x* × *x* matrices such that each matrix is either all 1 or all 0. We can loop over all such *x* and check the condition in *n*2 time per *x*, but this is potentially too slow. 20 21 To speed this up, we can precompute rectangle sums for every rectangle containing the upper-left corner, which enables us to compute the sum of any rectangle in . This improves our time complexity to . Since  ([really!](https://en.wikipedia.org/wiki/Basel_problem)), this means our solution is . Code: [49028814](/contest/1107/submission/49028814 "Submission 49028814 by neal") 22 23 #### [1107E - Vasya and Binary String](/contest/1107/problem/E "Educational Codeforces Round 59 (Rated for Div. 2)") 24 25 We set up a DP on (start index, end index, number of consecutive digits matching our start index). In other words, the current string we are solving is the substring from start index to end index, plus some number of additional digits (all equal to S[start]) added as a prefix to our substring. 26 27 We then have two choices from any given state: 28 29 * Cash in on our consecutive digits at the start and recurse on . 30 * Pick an index *i* such that S[start] = S[i], and collapse everything between those two indices in order to merge them together for an even larger prefix. This results in a score of , and we can loop over all *i* to take the maximum. 31 32 The runtime is , with a very good constant factor. Code: [49036191](/contest/1107/submission/49036191 "Submission 49036191 by neal") 33 34 Does anybody have ? 35 36 #### [1107F - Vasya and Endless Credits](/contest/1107/problem/F "Educational Codeforces Round 59 (Rated for Div. 2)") 37 38 Notice that if we take offer *i* exactly *m* months **before** we buy the car, it will provide us with  money at the time of the car purchase. Moreover, the only values of *m* that make sense are 0 ≤ *m* ≤ *n* - 1. This means we can immediately solve the problem via an algorithm for the [assignment problem](https://en.wikipedia.org/wiki/Assignment_problem), such as min-cost flow or the Hungarian algorithm. This has a runtime of  or , which manages to fit under the time limit with a good implementation. Code: [49033783](/contest/1107/submission/49033783 "Submission 49033783 by neal") 39 40 The better solution is to notice that for all offers *i* where we don't use up all *k**i* months, it's best to sort them by *b**i* (so that the highest values of *b**i* have the lowest values of *m*). This leads to a very nice  DP solution: [49035446](/contest/1107/submission/49035446 "Submission 49035446 by neal") 41 42 #### [1107G - Vasya and Maximum Profit](/contest/1107/problem/G "Educational Codeforces Round 59 (Rated for Div. 2)") 43 44 We can first compute all values of . Since we only care about the maximum such value within our segment, we can use div-conquer to solve every segment. In particular, if we know the index of the maximum value in , we know that any segment crossing this index has this value as its maximum. We can thus solve all segments crossing this maximum and recurse on the left and right sides. 45 46 To find the best crossing segment, note that each problem contributes a value of *a* - *c**i*. We can independently find the largest sum starting from our crossing index going left and the largest sum going right, and add these two together for the best overall crossing segment. 47 48 Unfortunately, since we can't guarantee that the maximum indices will divide our interval nicely in half, this does not lead to the usual  runtime of div-conquer but is instead  in the worst case. To improve on this, we can precompute partial sums of *a* - *c**i* and use [RMQ](https://en.wikipedia.org/wiki/Range_minimum_query) to find the minimum sum left of the crossing index and the maximum sum right of the crossing index. This reduces the crossing computation from  per index to  or , giving an overall runtime of . Code: [49036431](/contest/1107/submission/49036431 "Submission 49036431 by neal")