MikhailRubinchik.ru's blog

By MikhailRubinchik.ru, 4 years ago, translation, In English,

Hello everyone

I created and prepared all problems for the first round of Yandex.Algorithm . Below you will find editorial. I am sorry if something in solutions discriptions is not clear, if you have questions — please ask them in comments.

Problem A. Cheese

If potato takes less time to heat, than cheese to melt, then it is impossible. Otherwise, we either heat the potato a little and then put cheese on it, or heat the cheese to some degree, put it on the potato and continue to heat them together.

Problem В. Travelling in the Square

After leaving the central square there are four possible directions to go to, on the next step there is a choice from two turns and after that the route is fully determined. Thus, there are only 8 different routes. Each of them can be represented by a single string of length 9. Let’s put these strings in a constant array. While reading the input data let’s ignore all line breaks, so that we have a single string of length 9. Now we just need to find a string in the constant array, that equals to the input string (given that “?” is equal to any symbol).

Problem С. Opencup

Note, that if your team is not in top 30, it doesn’t matter which place it took. So let’s think that the only places available are the places from 1 to 31 (the last place means that we should output 1000). For every place from 1 to 30 let’s check whether we can stay in top 10. The worst case scenario is top 10 teams (excluding yours) take top 10 places in the last Grand Prix. Let’s assign a place to each of top 10 teams in such a way, so they would rank higher than you team. That we can do using simple brute-force. The total amount of operations will then be 31 * 10! * 10, which is about a billion. 31 can be replaced with log 31, and that takes us to about 200 million operations, which will probably be enough to get an OK for the solution, if it is implemented efficiently. Otherwise, several straight-forward optimizations will lead to a success. For example, you can check correctness of a permutation while building it. To eliminate a risk of exceeding the Time Limit, you can use a greedy approach when assigning points to top 10 teams.

Problem D. Cold countries

Let t be the number of pairs (boy + girl) that will eventually sleep next to each other. We are going to solve the problem for each t separately and then sum the answers with coefficients C(p, t). There are 2t! satisfying permutations if we are solving the problem for pairs only. To every such permutation we should now add w — t girls and m — t boys. Between some pairs (or between a pair and a wall) we can put only girls, and between other pairs — only boys. If t is odd, there is x ways to do it (for both girls and boys), where t = 2x — 1. The number of ways to put boys into permutation then looks like this: m! * C(m + x, x). First multiplier describes the order of boys and the second solves a standard combinatorics problem of putting m objects between t walls. We can then simplify the expression and get (m + x)! / x! (the same for girls). So, for an odd t we have an answer 2 * (t!) * (m + x)! * (w + x)! / x! / x!. We will not compute the answer for an even t here, but note, that in this case one should consider two possibilities: when the leftmost person in a first pair a boy and when it is a girl. This solution has O(p * log MOD) complexity, and this is too slow. The second factor appears because of the necessity of performing a division (or finding modular multiplicative inverse). Let’s notice, that we need to find it only for factorials of numbers from 1 to p and 1 / fact[y] = 1/ fact[y — 1] * 1 / y. We can find multiplicative inverse for numbers 1 .. p in O(p log log p) time, using Sieve of Eratosthenes, and then calculate the inverse for composite numbers in O(1), and for primes in log MOD. Also, you could have gotten an OK using only caсhing of already computed values. There is also a linear algorithm for finding multiplicative inverse elements, you can find its’ description in comments to this discussion: http://apps.topcoder.com/forums/?module=Thread&threadID=680416&mc=26&view=threaded

Problem E. Lillebror and Karlsson

Let’s represent a chocolate as a binary string of length m which contains n ones. We now need to split the string into a minimal amount of substrings, that fit our criteria. The resulting partition will contain n strings, of which some consist of ones and zeroes, and some only of zeroes (let’s call them zero-strings). To solve the problem we must minimize the amount of zero-strings. Let f[i] be a minimal number of zero-strings in a partition of a prefix of length i. We are going to initialize f[i] = f[j] if (i + j) / 2 — integer, s[(i + j) / 2] = ‘1’ and there are no other ones between positions i and j. If there is no such j, we initialize f[i] with infinity. Now we need to update f[i] = min(f[i], f[k] + 1]), using all k such that s[k..i] is a zero-string. Using the fact that all such k form a single substring, we can maintain minimum of them and update f[i] using O(1) time. We now have a solution with complexity O(m). Let’s transform it into O(n) solution. Initialization: f[0] = 0; f[i] = 1, if there are no ones to the left from i and s[i] = ‘0’. Now let’s find initial values of f[i] for all positions between the leftmost (first) ‘1’ and the second one. To do that we’ll need to reverse the array f. If the right end of array “covers” the right “1”, then we just need to delete everything after it. If the right end didn’t reach the right “1”, we need to add some values into array (let’s take a minimal value in the array + 1). After that step we have initial values for all positions between first two ones. Now let’s run through array from left to right and update a value on each position to a (minimum on the prefix with the end in this position) + 1. Similarly, we can calculate f[i] for all positions between second and third “1” and so on. Our array is too long, so we need to compress it. If there are x consecutive values y we will store corresponding part of array as a pair (x, y). Now we can add a bunch of equal values (and in this algorithm we only add equal values) in O(1) time. The amount of deleted values is not greater than the amount of added. Finally, let’s notice, that the difference between maximal and minimal values in the array is 1 or less. c — position of the minimal element in the array. To the right from it there can’t be a number greater than c + 1. Similarly, on a previous step we could not have had numbers greater than c + 1 to the left from it. Thus, our array in compressed form never has more than 3 elements, and we can reverse and run through it in O(1) time.

Problem F. Dynamic Complexity of String

For each border of length g there is a period of length T such that g + T = |S|. Because of that, we can find a minimal period of a string by subtracting from its’ length the length of maximal border. This is derived directly from the definitions of period and border (for more information search the Internet for “border array and period”). Furthermore, if the borders are scanned in decreasing order, the prefix function of each next border will be greater, than the previous one, and that means that minimal period will decrease (or stay the same). After calculating a prefix-function we can in O(1) find complexity for each prefix. To do that take the answer for the maximal border and add 1 if its’ period is different from the period of the next border (in decreasing order). We now know how to find an answer and how to write a checker for the problem. What left is to learn how to find the right string. First, it’s useful to look at known “interesting“ strings, for example “random string”, Zimin strings, Thue–Morse strings, Fibonacci strings, string from identical letters and so on (for more information search the Internet for “combinatorics on words”). In this case we can use Fibonacci strings. Note, that solution to this problem has a practical value. Some string algorithms have complexity O(dynamic complexity of string), and solution described above generates worst-case tests for such algorithms. Dynamic complexity of random strings is O(n), so if your problem can potentially be solved using borders’ analysis, you definitely should add such tests to a testset to increase the perfomance time of those algorithms by log n.

Read more »

  • Vote: I like it
  • +37
  • Vote: I do not like it