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*).

The number of ways to choose *a*_{i} (without any conditions) — 3^{3n}. 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^{3n} - *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^{3n} - 7^{n}. We count it in *O*(*n*).

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

Now *k* > *q*. So, if there is an answer, where exists *pos* such that *s*1_{pos} = *s*2_{pos}, *s*1_{pos} ≠ *ans*_{pos}, let's denote *ans*_{i} = *s*1_{i}, and then in any position such that *s*1_{i} ≠ *s*2_{i} = *ans*_{i} and *s*1_{i} = *ans*_{i} (and in the same position in *s*2) we will choose *a*_{i}, such that *a*_{i} ≠ *s*1_{i} and *a*_{i} ≠ *s*2_{i} (we can do it because *k* > *q*). So, for every position from *q* we can put symbols, equal to corresponding symbols in *s*1 and *s*2. Now we have strings *s*1, *s*2 of length *n* - *q* (such that *s*1_{i} ≠ *s*2_{i} for every i) and we should find string *ans* such that *f*(*ans*, *s*1) = *f*(*ans*, *s*2). We know that *s*1_{i} ≠ *s*2_{i}, so *ans*_{i} may be equal to corresponding in *s*1 or to corresponding in *s*2 or not equal to *s*1_{i} and to *s*2_{i}. So, we need, at least, 2(*k* - *q*) symbols in answer to make *f*(*s*1, *ans*) = *k* - *q* and *f*(*s*2, *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 *s*1, next *k* - *q* symbols from *s*2, and others won't be equal to corresponding in *s*1 and *s*2.

Solution works in *O*(*n*).

There is a fact that the distance between adjacent prime numbers isn't big. For *n* = 10^{9} 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.

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 *pos*2 such that *pos* < *pos*2 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*^{3}). 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.

Problem D is clone of Timus #1356 ? But task C is more difficult than D . . .

Thanks for the awesome round! :)

BTW, there is a typo in Problem D's description:

"More formally, you are given an odd numer n." ->

"More formally, you are given an odd number n."

Whats proof for greedy method used for problem D ?

http://sweet.ua.pt/tos/goldbach.html

If we modify the 584C - Marina and Vasya to find

but not

, what is the fast solution to the new problem?

For example, "aaabbc" is different from "bbcaad" in exactly 1 characters in the new "difference rule" because one permutation of "bbcaad" is "aadbbc". The difference between s1 and s2 in the new problem may be calculated like this:

And it seemed that we can use the character c with minimal cnt[c] to "provide difference" firstly if we want to build a second string.

Didn't the question tell us to find a third string different from them in exactly t characters (irrespective of positions) i.e. your modified version?

Please correct me if I am making some mistake.

So I wasn't the only one with the same confusion. Here is what the author wanted to mean:

If am not wrong, the difference in problem C was based on the characters at the same positions. The difference in my modified version is based on the count of each character irrespective of positions. If what you said is about the modified version, I think you are correct.

I think this is easy to understand solution. 13473346

This is late, but this can be a solution to your modify .

where's the proof of correctness for Problem D ?

Goldbach's Conjecture

also Goldbach's_weak_conjecture

I have a questions considering problem E. 1. Why is the problem of transforming permutation p to s equal to problem of transforming permutation p to (1,2,...,n)? 2. Shouldn't it be "Let's move the pointer to the right until number becomes

lower or equal topos."The main idea is that if your look for the position of s[n] (the value at n-th position of s) in p, let's say the position is 2, then the same argument tell you that the position of at least one of s[1] or s[2] in p must be greater than 2.

After you understood 1., then you know that you would like to swap n with number that has pos GREATER than pos of n. So that n is actually moving toward the end. Otherwise you are moving n farer from its target.

s_{1}= 1,s_{2}= 2, .... Then you change them in permutationpand in permutations.Not able to understand the tutorial Please help me with 584E. Why converting p to s is equivalent to converting p to (1,2,3,....). Please help!!

Interesting 584E. While I keep getting TLE for printing output with std::cout, the same test case could be finished in <200ms by printf...

Are there any method to significantly speed up std::cout?

`ios_base::sync_with_stdio(false);`

`cin.tie(0);`

After some more testing, I have got the following results toying with printf and cout. For the worst test case:

So I guess I would stick to printf from now :/

I can't find C like difficult problem, more like hard to implement problem.

Actually, I think that it becomes somewhat easier to implement if you first set the output to something completely different from both strings

aandband then iteratively refine it, always maintaining the invariant that it is equidistant fromaandb.It's not hard to notice that, at each step, you must either change an element

isuch thata_{i}=b_{i}or change two elementsi,jsuch thata_{i}≠b_{i}anda_{j}≠b_{j}. For more details, take a look at this code: http://codeforces.com/contest/584/submission/13449413Nice implementation. Clear and straightforward.

Self explanatory code.

I solved D by using 3 every time. I precomputed primes up to 10^6 and then tried to find the first prime p for which (n-p-3) is prime. It is always found fast enough (31 ms runtime, actually), but I have no proof of why it works.

http://codeforces.com/contest/584/submission/13480500

This also follows from Goldbach's conjecture (if it were proven),

n- 3 is even so there should be two primesp1,p2 such thatn- 3 =p1 +p2, orn-p1 - 3 =p2.Yes, but there is no proof that those two primes (or at least one of them) are <= 10^6.

Well ..

https://en.wikipedia.org/wiki/Goldbach%27s_conjecture#Verified_results

If you read Wikipedia's article on Goldbach's conjecture they claim:

"3325581707333960528 is the smallest number that has no Goldbach partition with a prime below 9781".

Although I haven't gone to the source of this verification so I don't know whether it's actually true.

Notice this implies your 'search for the first prime..' part will try -possibly much- less than 10000 possible partitions.

That's funny, I literally read the whole "Verified results" section except for this last sentence. Also that's a really interesting fact, I definitely wouldn't have guessed that primes are this common. Bad intuition on my part, I guess.

This theorem might be of interest: https://en.wikipedia.org/wiki/Prime_number_theorem. Roughly, in the neighborhood of

n, you can expect about one in every numbers to be prime. Knowing this is occasionally useful when analyzing (or designing) "brute force" algorithms that would otherwise seem to give TLE.On a related note, it seems that Google once posted several recruitment billboards with the text "{first 10-digit prime found in consecutive digits of

e}.com". Turns out the expected solution was just to brute force the possible sequences :)Source: http://mathworld.wolfram.com/news/2004-10-13/google/

Can someone explain me how did he get The number of ways to choose ai = (3)^(3*n) in Problem B.

each element of a can have one of three values (1 or 2 or 3), and the number of elements of a is 3*n so the number of ways to choose the values of a = 3^(3*n)

“You can check that there is a solution for all even numbers less than 300 by bruteforce.” Actually，there is a solution for all even numbers less than 10^18. https://en.wikipedia.org/wiki/Goldbach%27s_conjecture

Can somebody explain how E solution works? I didn't understand very well the tutorial, sorry :/

Thanks.

Sure :)

Let

aandbbe two permutations of lengthnand suppose that we want to transformaintob. Now, lets_{x}denote the position to which we want to move the valuexina-- in other words,s_{bi}=i. The first thing to notice is that the theoretically best value for the answer is . The only way to reach it would be to move each elementa_{i}to the positions_{ai}without ever getting farther from it. And indeed, it turns out that we can always do that!If we sequentially process elements from the right, a possible strategy is the following: visit one element at a time and, if it should be to the right, try to move it to its final position by performing swaps along the "good pairs" on the path between it and its destination. I'm calling a pair (

a_{i},a_{j}) "good" if swappinga_{i}anda_{j}moves them both closer to their final positions. (Remember, swapping a pair that isn't good would make it impossible to reach the optimal value.)Here's my implementation: http://codeforces.com/contest/584/submission/13502664 (

sin the explanation corresponds todesired_posin the code)johnjq , thanks for the excellent explanation, now I understood!

mras, you're welcome :)

New bie here, why left to right doesn't yield minimum cost ?

How to prove that the solution for the problem E requires the smallest amount of money?

Because solution moves numbers only to their positions in final array

## Problem_D

After accepted, I clicked the editorial .

when I Clicked submit option, I thought that My solution might be wrong.

But accepted!!!!!!!!

OK, I have a question.

I know every even number(greter than 4 ) represnt as sum of two prime number .

But is it possible to represent an odd number as sum of at most two prime number(all the time? ???

In that problem, first I find out large prime number<=n.

then I calculate another number "m" which is(n-large_prime).

but "m" is not always even number . if m>1 and odd number , then is it possible to represent m as sum of at most two prime number???

Every problem of this contest is beautiful and mathematical.

For problem D , how you have figured out maximal distance is 282?