Codeforces Round #256 — Editorial

Codeforces Round #256 — Editorial

By Bugman, 8 years ago, translation,

448A - Rewards

Solution:7139559

Because rewards of one type can be on one shelf, lets calculate number of cups — a and number of medals — b. Minimum number of shelves that will be required for all cups can be found by formula (a + 5 - 1) / 5. The same with shelves with medals: (b + 10 - 1) / 10. If sum of this two values more than n then answer is "NO" and "YES" otherwise.

448B - Suffix Structures

Solution:7139584

Consider each case separately. If we use only suffix automaton then s transform to some of its subsequence. Checking that t is a subsequence of s can be performed in different ways. Easiest and fastest — well-known two pointers method. In case of using suffix array we can get every permutation of s. If it is not obvious for you, try to think. Thus, s and t must be anagrams. If we count number of each letter in each string, we can check this. If every letter appears in s the same times as in t then words are anagrams. In case of using both structures strategy is: remove some letters and shuffle the rest. It is possible if every letter appears in s not less times than in t. Otherwise it is impossible to make t from s. Total complexity O(|s| + |t| + 26).

448C - Painting Fence

Solution:7139610

To solve this problem we need to understand some little things. First, every horizontally stroke must be as widely as possible. Second, under every horizontally stroke should be only horizontally strokes. So, if bottom of fence painted by horizontally stroke then number of this strokes must at least min(a1, a2, ..., an). These strokes maybe divides fence into some unpainted disconnected parts. For all of these parts we need to sum they answers. Now its clearly that solution is recursive. It takes segment [l, r] and height of painted bottom h. But we must not forget about situation when all planks painted with vertically strokes. In this case answer must be limited by r - l + 1 (length of segment). With given constrains of n we can find minimum on segment by looking all the elements from segment. Complexity in this case will be O(n2). But if we use for example segment tree, we can achieve O(nlogn) complexity.

448D - Multiplication Table

Solution:7139620

Solution is binary search by answer. We need to find largest x such that amount of numbers from table, least than x, is strictly less than k. To calculate this count we sum counts from rows. In i th row there will be . Total complexity is O(nlog(nm)).

448E - Divisors

Solution:7139644

Learn how to transform Xi into Xi + 1. For this we need to concatenate lists of divisors for all elements of Xi. To do this efficiently, precalculate divisors of X (because for every i Xi consist of its divisors). It can be done by well-known method with complexity. How to calculate divisors of divisors? Need to know that for the given constrains for X maximum number of divisors D(X) will be 6720 (in the number 963761198400), so divisors of divisors can be calculated in O(D2(X)) time. With this lists we can transform Xi into Xi + 1 in O(N) time, were N = 105 — is the limit of numbers in output. Now learn how to transform Xi into X2i. What says Xi? Besides what would be X after i steps, it can tell where goes everyone divisor of X after i - 1 steps. Actually, Xi is concatenation of all Yi - 1, where Y is divisor of X. For example, 103 = [1, 1, 1, 2, 1, 1, 5, 1, 1, 2, 1, 5, 1, 2, 5, 10] = [1] + [1, 1, 2] + [1, 1, 5] + [1, 1, 2, 1, 5, 1, 2, 5, 10] = 12 + 22 + 52 + 102. How to know which segment corresponds for some Y? Lets pos(Y) be the first index of Y in Xi. Then needed segment starts from pos(prev(Y)) + 1 and ends in pos(Y), where prev(Y) is previous divisor before Y in sorted list of divisors. So, to make X2i from Xi we need to know where goes every element from Xi after i steps. We know all its divisors — it is one step, and for every divisor we know where it goes after i - 1 step. Thus, we again need to concatenate some segments in correct order. It also can be done in O(N) time. How to find now Xk for every k? The method is similar as fast exponentiation:

Xk = [X] when k = 0,

if k is odd then transform Xk - 1 to Xk,

if k is even then transform Xk / 2 to Xk.

This method takes O(logk) iterations. And one small trick: obviously that for X > 1 Xk starts from k ones, so k can be limited by N. Total complexity of solution is .