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

5). femsub

Editorial will be published later

**UPD3** Editorial

Hope it will be a great Round :-) Happy coding :-)

Hope it's another interesting round. Good luck to all :)

I think clear problems with no story are better because there are many coders at codeforces that their main language is not english or Russian

Totally agree. For me it is quite difficult to read and understand the storylines in English. Sometimes I even look up a dictionary for words that I don't know.

It's a part of problem! You must have good English skills to understand storyline clearly. I think English tasks for Russian users will be more fair.

and Russian tasks for American and UK users? =). It is nonsense.

English is the main language of interaction between countries. You can't code in Russian; you code in English. So it makes sense that tasks should be in English.

1C is progaramming language (guess on what) on Russian. Now you know more.

1C, not C1.

:D

Best wishes to ACM ICPC — 2015 regional/sub-regional participants for their upcoming regional/sub-regional contest and congrats to those who already manage to qualify for

ACM-ICPC World Finals 2016 — Phuket:)"The scoring distribution will be announced later."So mainstream ;)

hello

So much grey。。

hope to see a lot of math problems :D

Lots of down votes here :D :v

This parrot seems angry :P

I had green parrot, but when cf change color, I changed color of that parrot too

You are very brave to comment here today. Look at all the downvotes.

"Downvote squad" hard at work :p

Same

Yeah! The color matches with your CF color. Hopefully you'll get a blue parrot soon :)

inbox me more such pics ( ͡° ͜ʖ ͡°)

Gayle Laakmann live session or this contest :D

Isn't she over-rated?

check this quora link quora. With all due respect ma'am, try to accept that there are people in this world a lot more smarter than u and being a bit** will not change that. :)

Isn't she stupid for saying that? Gennady won't even care, let alone give her a comeback.

yes i know.. in comments section she clearly states she knows him and compares herself and him as apples and oranges . LMAO XD

WHAAAAAAAAAAAAAAAAAAA????? brb,, dying on the floor laughing :D

Obligatory: Who?

The scoring distribution will be announced later later later late lat la l..........

where is scoring distribution ??

Auto comment: topic has been updated by ZhNV (previous revision, new revision, compare).z

at problem d i output 3

2 2 23 i have wrong answer on pretest 1 , which has n=27 why? LE : my bad, sorry

What was the problem?

I forgot a return 1;

The windows returns it automatically,but on linux is a big problem. Sorry guys for the misunderstanding

z

why did you copy? this is bad

B — What's wrong with the solution

`3^(3n) - 7^n`

?Nothing.

So it is actually right? I kept getting WA. Maybe I've got some mistakes in modular arithmetic ?

Yep, with modulo formula is like this ((3^n) % MOD — (7^n) % MOD + MOD) % MOD. Because we can get negative number)

P.S. sorry, didn't read posts below

`if(ans < 0) ans += MOD;`

?cout << (g-s+mod)%mod;

I feel so embarrassed :\

And still. How could it possibly be negative?

because 1000000007 mod 1000000007 is less than 100 mod 1000000007

Got it now. Thank you.

-3/2=-1 -3%2=-1 I don't like this either. It causes so many troubles...

(g-s)%mod could be negative

when u will get ans < 0 as 27^n — 7^n can never be zero

Good question. Got WA with this formula, couldn't figure why :(

I think that's the solution almost all in my room used. Check your modulo maybe?

That is what i did and it passed pretests

check overflows.

I thought too much that this required for looping and finding nCr. -_-

Logic behind formula? I failed very hard today ;_;

There are total 27 possible way to distribute coins to 3 gnomes out of which 7 will have have sum equal to 6. And in our required answer we need to exclude that case. Since there are n such combinations we will have 27 ^ n — 7 ^ n.

Thanks

I don't know why i was getting WA in 7th test case. :-(

For n=1 one triangle.

For n=2 two triangle.

and so on.

We have three positions and three number.

So total combination = 3*3*3 =27

Invalid combinations of three numbers when sum=6 is

(2,2,2) =1, (1,2,3) this will be 3! = 6 .

Invalid combination=7

Valid Combination=27-7=20

There will be no solution when all triangles have in

invalid combination.

Answer is Total ways to fill n Triangle — When all triangle uses Invalid combination

Answer is 27^n — 7^n**

It's very cool to understand some dependence or notice combinatoric, but I simly considered second test and suggested, that it could be true. In a result, I was lucky :)

Problem 2: Just 3^(3*n)-7^n ;))

27^n — 7^n : Still got wrong answer ...dont know why ...maybe becauze of MOD operation

maybe when

`(7^n)%mod > (27^n)%mod`

, then you should write:`((27^n)%mod-(7^n)%mod+mod)%mod`

ok thanks

you forgot to add MOD if the answer becomes -ve. You should write like this: (27^n — 7^n + MOD)%MOD

code by JAVA (3^(3*n)-7^n) % mod

dafuq is C pretest 9?

seriously it's killing me to know

I couldnt pass Pretest 4 only :/

I'm guessing something like this:

INPUT

5 1

baset

easej

OUTPUT

basej

Tested with my program (which failed at pretest 9), and I got the correct output for that input.

Yup Mine Passed that too :/

may be some thing like it!

4 2 abcd ebfg

How to solve problem E ?

Greedily. Problem: sort the permutation with minimum cost. Let's assume that we already sorted first

ielements(0-based). Let'sp[j] =i. Then we need to find maximumindsuch thati≤ind<jandj≤p[ind], it can be easily done by segment tree. Then swap elements at indexindandj. For each indexiyou will makeO(n) swaps. ComplexityO(n^{2logn})Are you certain this works? I submitted this and got stuck on pretest 14, and looking at your profile you didn't pass the pretests either (getting stuck much earlier than me).

I wanted to write the same but was sure that it doesn't work;)

Yes, that works. I didn't passed because I had wrong idea. I looked for maximum

indsuch thati≤ind<jandp[ind] >ind. This idea doesn't work for test: 4 4 3 2 1 1 2 3 4The minimum cost is achieved using any strategy that never moves any element further from its final location, since |

i-j| is just the distance by which each element is moved (·0.5).One way to solve this would be putting all elements that need to be moved to the right in one set, those which need to be moved to the left in another set and always swapping the first element of the latter set with the last smaller element of the former.

Can't believe E can be so simple, thanks for the explanation :D

How to solve D?

If n is prime we print 1 n

If n — 2 is prime we print 2 2 n — 2

If n — 4 is prime we print 3 2 2 n — 4

Else n = p1 + p2 + p3. We find closest prime number to n (p1). And we've got n — k = p2 + p3.

n — k ~ log(N) (Don't remember why, shame on me). And just by brute force find p2 and p3.

What's the complexity of finding the closest prime number?

1700 * sqrt(n) maximum distance between 2 primes if they are both not greater than 10^9 is 1700

Maximum prime gap less than 10^9 is 282.

As I said n — k ~ log(N). Checking whether number is prime O(sqrt(N)). So finding closest prime number is log(N)sqrt(N).

If I'm wrong correct me please.

It seems that its O(log^2(N)). https://en.wikipedia.org/wiki/Prime_gap#Conjectures_about_gaps_between_primes

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

Seriously, without knowing this conjecture, can anybody solve problem D? This kind of problem just piss me off!!!

I solved D without this knowledge:D

Then you (maybe without realizing) assumed that there is always valid p2 and p3 whose sum equals to n — p1. Problem guarantees there is a solution. It doesn't guarantee there is a valid (p2, p3) pair; that's why, you need to know Goldbach's conjecture.

Yeah, you're right... This was just guess.

You don't need to know it since the problem is simple enough to brute force. First check if n is prime, if so print. Else find largest prime smaller than n, now check if you can find one or two primes adding up to this (goes very fast since prime density is quite high), if so print. Else iterate.

You know from the problem description that there is a solution, and you know that finding multiple fitting large primes is too slow so the only way left is to just find large primes and then see if you can find one or two smaller primes adding up to the result.

This way you can solve for odd n as well since it is so easy to find a solution.

Seriously, http://www.lmgtfy.com/?q=+integer+as+sum+of+three+different+primes

I used Levy's Conjecture and Fermat's Little Theorem to solve D.

I can't solve it during the contest due to a small mistake. But i did it right after the ending of the contest :/

If n = 3, output 1 3 if n = 5 output 2 2 3 else

since n is odd, n — 3 is even, and then we can use strong goldbach conjecture to solve the problem. Every number N even, greater than 2, can be written as sum of two primes. Since n — 3 is even, we can find this two primes that added form n — 3 and then add it to 3, which is prime. output

3 3 prime[i] (N — 3 — prime[i])

I used Sieve of Eratosthenes to find primes between 2 and 10^7, and if some number K didn't fit in this interval, I test it's primality by brute force. And used binary search to try to find N — 3 — prime[i] in vector of primes;

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

Problem A and Problem B is a joke in Python

yeh! partiality with c programmer ;)

Bahut Na insafi hai

how so?

Literally 4 lines of code for either.

(Seeing as in python you can do things like print(str(A)*N) for value of A repeated N times and in the second you dont need to add the mod operation till the end because python dgaf about ints long longs and such.)

D also=)

What is The Solution Of div2 E? I tried to find symmetric group, but it seems hard to calculate the minimum step to sort the permutation

How to slove D? Damn I spend all contest to it

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

Still not sure how to do it.

It is basically coding Goldbach's weak conjecture, right?

3, and express n-3 as sum of two primes. Do you just brute force it? What about the time complexity?

No.4 cannot be expressed by your logic

The question says input is an odd number.

Then we are assuming that '3' is definitely in the answer. Can you prove it?

That is Goldbach's weak conjecture and it has been verified for numbers larger than the input in the question.

In fact, Goldbach's weak conjecture has been mathematically proven to be valid in general.

So handle small numbers manually for simplicity. (Since n is odd, n-3 is even, and you can brute for 2 remaining 2 primes numbers(other than 3) summing upto n). Handle cases of n=3, etc manually.

For larger n, always try and express it as sum of exactly 3 primes. Find a prime number g below n and close to it.This is one of your 3 primes. Since prime numbers are not too far apart, n-g is now a small even number(my bound was 50000) and you can brute for how to express it as 2 primes.

Thanks. Your gap was 50,000? According to wiki, a gap of 300 would suffice.

https://en.wikipedia.org/wiki/Prime_gap

I did not know that. Just wanted to be safe :P

There's no need of different method for larger numbers. You can always brute force to express n-3 as sum of two primes. My solution passed with this method. I think the reason for this is that even when n is around 10^9, there is a very high probability of finding a small prime p(upto which you can iterate in time) such that n-3-p is also prime.

Yes, I realized my solution during the contest failed only because my brain missed the "at most 3" condition. I ended up missing primes below 7 (3 and 5) — I thought they wouldn't be in the input since solution was guaranteed... Unfortunate error.

BTW, check this problem: http://acm.timus.ru/problem.aspx?space=1&num=1356. It's almost the same as the problem D, just a bit harder (but the solution for 1356 works here in problem D).

This problem was on National Olympiad of Kazakhstan 2013-2014, as I remember.

C pretest 9 ahhhr.

C looks straightforward but did not work out.

My thought.

My Algo was(not worked): 1) Find common chars in a & b -> x and set them in output array z[i] = a[i] 2) m = m — x 3) Place m chars of a in z(if z[i] not already set) z[i] = a[i] if z[i] == 0 4)similary set m chars of b in z(after step 3) z[i] = a[i] if z[i] == 0 5) For remaining unset chars in z[i] = char no in (a[i], b[i])

is Editorial out ?

System rating finished

Hello! I have a question at the second problem, Div 2. During the contest I printed

`(put(3,3*n)-put(7,n))%m;`

and i have got wrong answer on test 7. Now I am printing`(put(3,3*n)-put(7,n)+m)%m;`

and I have got accepted. Why the second method works? Thanks!put(3,3*n)-put(7,n) may be negative number. So first method would be incorrect (returns m minus right answer).

but why should i add m? m is 10^9 + 7. i don't understant..

put(3,3*n)-put(7,n) = Km + ans

may be less than zero. 0<=put(3, 3*n)<m ans 0<=put(7,n)<m. So -m<put(3,3*n)-put(7,n)<m

put(3,3*n)-put(7,n) + m guarantee positive. So mod operation would be correct.

I didn't know ! Thanks a lot!

You are a specialist man!!!

Well consider x < 0 and abs(x) < m. If we don't know how language will eval x%m, we simply do (x+m)%m, that way we are sure that we are moding a positive value.

Haters everywhere. F**k you too

For D, I just generated primes upto 10^6 and tried to find the answer with simple check. And it passes. Why does it pass?

Because primes are distributed pretty randomly with log(n) distance between them in average. So, there is no such number N that for all small prime numbers M up to 10^6, N — M is not prime.

Well, didn't know that. Thanks.

I don't understand.Why 2000 points for problem D??? :o :o :o It was far far easier than B and C.

Task C is more difficult than D . . . It's injustice!

why this submission get WA?

1 should not be considered prime

1 isn't prime number!

how to solve C ?

greedy . . .

Can you explain?

Codeforces should have a problem tag called "case handling"

http://codeforces.com/submissions/sameer85#

its easy to read...its simple greedy approach

thanks :)

just added the condition of a+b+c=n and D passed :( :( :( :(

Auto comment: topic has been updated by ZhNV (previous revision, new revision, compare).i forget to say :thanks for no delay

Some help on E? I can find the minimum cost but I cannot restore the swaps. I thought about going from left to right and if we see an element which is not on its place (it must go to the right) then let's say his position is i and it must go to position j. Let's first handle all elements that are greater than Ai in the interval [i+1,j] and then somehow solve for the current element. Can you please give me a hint?

can E be solved using greedy method ?

Well, the first part (minimum cost) can be called greedy, I guess. The idea is to find for each number its position in B. Then if we want A to become B, that means that some elements will go to the left and some to the right. We can make the observation that we need to consider only those elements which go to the right. Let's assume that after considering them, there is an element that must go to the left (if there is more than one, consider the leftmost). Moving it to the left means moving one element to the right. A contradiction! So if pos[k] is the position of the element with value k in B, we add to the answer max(pos[Ai]-i,0) for each i.

My solution is actually greedy. What I do is in each step I have a vector that keeps all the numbers that have to go to the right (I iterate the numbers from left to right) and whenever I find a number that has to go to the left I just swap them and move the index of my iteration back so I can start from the number I moved.

Before that I change the permutations so the second permutation is 1 2 3 ... N and the first one changes so it's the same problem but having to move a permutation to the sorted permutation.

Let's see an example:

4 4 3 1 2 1 2 4 3

The problem is the same as solving

4 3 4 1 2 1 2 3 4

Now I start with 3, it has to go to the right so my vector is (3), then 4 has to go to the right so my vector is (3,4), then 1 has to go to the left so I swap 1 and 4 now it's

3 1 4 2

And my iterator moves back to where the 1 is, now 1 still has to go to the right so I swap 1 with 3 that is the top of my vector (or stack if you want to see it like a stack). Now it's

1 3 4 2

Then I continue iterating, 1 has to stay where it is and the vector is empty, then 3 has to go to the right, 4 has to go to the right too, and 2 has to go to the left, and when I analyze 2 my vector is (3,4) so I move 2 to the left and it's

1 3 2 4

And in the last step I change 3 with 2 so it's

1 2 3 4

And it finishes the process. This is a greedy approach and it's similar to selection sort I think.

I start with 4 (it

You can maintain an ordered set (balanced binary search tree) of all elements that need to go to the left (call this set L), and all that need to go to the right of the permutation (call this set R).

In each iteration you perform one swap, that involves swapping the leftmost element in L with its closest element in R to the left (it clearly has to exist). If you store both the elements and their positions, you can efficiently maintain this structure as you go along in logarithmic complexity.

You may refer to my code: http://codeforces.com/contest/584/submission/13456405

You don't need such complicated structures as O(N^2) is ok for this problem.

The complexity of my solution is actually something along the lines of O(N^2 log N) in the worst case (something like 5 6 7 8 1 2 3 4) anyway. I try to follow the approach which is easiest for me to comprehend on a high level. If it requires complicated structures, so be it (especially if they're already part of the STL). :)

Consider the element that needs to go to the rightmost location. Lets say that element is in the ith position and needs to go to the nth position. Then, surely there must be an element from positions i+1 to n which needs to go to a position j where j <= i. If no such element exists, then there are (n-i) elements which final location is from (i+1) to (n-1), a contradiction! Find the leftmost element which matches this criteria using a pointer sweep and then swap it with position i then keep repeating until it is moved to its correct location. This is an O(n^2) algorithm.

Problem E : For the first time on codeforces, a solution didn't pass for me with cin,cout. My solution failed system tests after passing the pretests. And when I changed it to printf,scanf it passed. I think the problem setters should be careful the next time, as when crtical points and rating gets affected due to such reasons, it feels sad.

Why are you blaming the problem setters for this? It was your fault!

What should be tested is our knowledge, not whether we use fast i/o. And in fact such things have never happened on Codeforces before. Also when you get a problem wrong because of such reasons, it doesnt feel good. I'm not blaming them, but I feel if someone loses out on points for a hard problem, because they didnt use fast i/o, that is just not fair.

If problemsetter increase time limit in order cin/cout submition past, it can cause that slow solutions will past with scanf/printf! Cin/cout speed is well-known fact, be careful, when you use it

Do you use

`ios_base::sync_with_stdio(false);`

?

That line can save you from time limits if you use cin/cout

Yes I did use it, still didn't pass :(

You can add these lines to speed up cin/cout.

It is time to midnight,but still waiting for Rating.

It is almost sunrise, still waiting for Rating :P

it's night and i have n't done my homeworks! but still waiting for ratings!

Me too , it's weird how sometimes human being is not able to wait and do assignments both at once!

we have the same time midnight. already tired

MikeMirzayanov. When you declare a rating?

Happy New Year CF!!! wait(wow), rating still not updated?

Wow, my rating is changed to

`+0`

:)What is this?

Oops, it will be fixed tomorrow.

Auto comment: topic has been updated by ZhNV (previous revision, new revision, compare).