ZhNV's blog

By ZhNV, 6 years ago, translation, In English

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 ai (without any conditions) — 33n. Let A be the number of ways to choose ai with condition that in every triangle gnomes have 6 coins. Then answer is 33n - A.

Note that we can separate all gnomes on n independent triangles (i-th triangle contains of ai, ai + n, ai + 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 — 33n - 7n. 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 s1i = s2i. If k ≤ q, then let's take k positions such that s1pos = s2pos 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 s1pos = s2pos, s1pos ≠ anspos, let's denote ansi = s1i, and then in any position such that s1i ≠ s2i = ansi and s1i = ansi (and in the same position in s2) we will choose ai, such that ai ≠ s1i and ai ≠ s2i (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 s1i ≠ s2i for every i) and we should find string ans such that f(ans, s1) = f(ans, s2). We know that s1i ≠ s2i, so ansi may be equal to corresponding in s1 or to corresponding in s2 or not equal to s1i and to s2i. 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 = 109 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 pi and |i - j| for moving pj. 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 ppos = n. Let's prove that there exists a position pos2 such that pos < pos2 and ppos2 ≤ pos(then we will swap ppos2 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 posn ≤ pos. Now we can use Pigeonhole principle and say that position x, such that x > pos and px ≤ pos exists.

But now our algorithm is O(n3). 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.

Read more »

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

By ZhNV, history, 6 years ago, translation, In English

Hello, Codeforces!

I'd like to invite you to Codeforces Round #324 (Div. 2). It'll be held on Tuesday, October 6 at 19:30 MSK and as usual Div. 1 participants can join out of competition.

Great thanks to Zlobober (Maxim Akhmedov) for helping me preparing the contest, to Delinur (Maria Belova) for translating the statements into English, to MikeMirzayanov (Mike Mirzayanov) for the Codeforces and Polygon. This is my first round, and, I hope, it won't be the last one.

You will be given five problems and two hours to solve them. The scoring distribution will be announced later.

Characters from problems have their prototypes — my friends, familiars, native, and this round is dedicated to them.

UPD : 500-1000-1500-2000-2500

Good luck and high rating!

UPD2 Round has finished, thanks for participation!

Congratulations to the winners!

1). Siunaus

2). aasddf

3). M_H_M

4). lal

5). femsub

Editorial will be published later

UPD3 Editorial

Read more »

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