584A - Olesya and Rodion

Two cases: t = 10 and t ≠ 10.

If t = 10 then there are two cases again :). If n = 1 then answer is  - 1 (because there is not any digit divisible by t). If n > 1, then answer, for example, is '1111...110' (contains n - 1 ones).

If t < 10 then answer, for example, is 'tttttttt' (it, obviously, divisible by t).

584B - Kolya and Tanya

The number of ways to choose a_i (without any conditions) — 3³ⁿ. Let A be the number of ways to choose a_i with condition that in every triangle gnomes have 6 coins. Then answer is 3³ⁿ - A.

Note that we can separate all gnomes on n independent triangles (i-th triangle contains of a_i, a_i + n, a_i + 2n, i < n). So we can count answer for one triangle and then multiply the results. To count answer for one triangle, we can note that there are 7 ways to choose gnomes with 6 coins (all permutations 1, 2, 3 and 2, 2, 2).

So answer is — 3³ⁿ - 7ⁿ. We count it in O(n).

584C - Marina and Vasya

Let's find a string that will be equal to s1 in k = n - t positions and equal to s2 in k = n - t positions. Let's denote q = quantity of i that s1_i = s2_i. If k ≤ q, then let's take k positions such that s1_pos = s2_pos and put in answer the same symbols. Then put in other n - k positions symbols, which are not equal to corresponding in s1 and s2 (we can do it, because we have 26 letters).

Now k > q. So, if there is an answer, where exists pos such that s1_pos = s2_pos, s1_pos ≠ ans_pos, let's denote ans_i = s1_i, and then in any position such that s1_i ≠ s2_i = ans_i and s1_i = ans_i (and in the same position in s2) we will choose a_i, such that a_i ≠ s1_i and a_i ≠ s2_i (we can do it because k > q). So, for every position from q we can put symbols, equal to corresponding symbols in s1 and s2. Now we have strings s1, s2 of length n - q (such that s1_i ≠ s2_i for every i) and we should find string ans such that f(ans, s1) = f(ans, s2). We know that s1_i ≠ s2_i, so ans_i may be equal to corresponding in s1 or to corresponding in s2 or not equal to s1_i and to s2_i. So, we need, at least, 2(k - q) symbols in answer to make f(s1, ans) = k - q and f(s2, ans) = k - q. Consequently, if n - q < 2(k - q), the answer is  - 1, and else just put first k - q symbols in answer from s1, next k - q symbols from s2, and others won't be equal to corresponding in s1 and s2.

Solution works in O(n).

584D - Dima and Lisa

There is a fact that the distance between adjacent prime numbers isn't big. For n = 10⁹ maximal distanse is 282. So let's find maximal prime p, such that p < n - 1 (we can just decrease n while it's not prime(we can check it in )). We know that n - p < 300. Now we have even (because n and p are odd) number n - p and we should divide it into a sum of two primes. As n - p < 300, we can just iterate over small primes P and check if P is prime and n - p - P is prime. You can check that there is a solution for all even numbers less than 300 by bruteforce.

584E - Anton and Ira

We can consider that we pay 2|i - j| coins for swap (we can divide answer in the end). Then we can consider that we pay |i - j| coins for moving p_i and |i - j| for moving p_j. So, if x was on position i and then came to position j, then we will pay at least |i - j| coins. Then the answer is at least (pp — position k in permutation p, and ps — position k in permutation s). Let's prove that this is the answer by showing the algorithm of making swaps.

Let's consider that permutation s is sorted (our task is equal to it). Then we will put numbers from n to 1 on their positions.

How we can put n on its position? Denote p_pos = n. Let's prove that there exists a position pos2 such that pos < pos2 and p_pos2 ≤ pos(then we will swap p_pos2 with n (and both numbers will move to their final positions and n will move to the right, so we can repeat this process until n returns to its position)). We can note that there are only n - pos positions that are bigger than pos. And how many numbers on these positions can be bigger than pos? We can say that answer is n - pos, but it's incorrect, because n is bigger than pos, but pos_n ≤ pos. Now we can use Pigeonhole principle and say that position x, such that x > pos and p_x ≤ pos exists.

But now our algorithm is O(n³). How we can put n in its position in O(n) operations? Let's move the pointer to the right while number is bigger than pos. Then swap n with found number. After we can move pointer from new n's position, so pointer always moves to the right and will not do more then n steps.