Hello, dear participants of Codeforces community!

Starting from Codeforces Round #327 I'll be the new coordinator and will manage preparation process for all regular Codeforces rounds and other contests held on this platform. I'll do my best to increase the quality of contests we offer you, though Zlobober already raised this bar high. Let's cheer him once again, for all the great job he had done!

Tomorrow round will be held using the problems of Moscow team olympiad for high-school students. Do not be tricked by the word "school" — there will be a gold medalist of IOI 2015 participating and some candidates to this year Russian IOI team, meaning the level of the problems will be appropriate. I am sure everyone will find an interesting problem to enjoy.

The problemset was prepared by the team of Moscow authors (list is incomplete): Zlobober, romanandreev, meshanya, wilwell, glebushka98, timgaripov, thefacetakt, haku, LHiC, Timus, Sender, sankear, iskhakovt, andrewgark, ipavlov, StopKran, AleX leaded by your humble servant GlebsHP and the chairman of the jury Helen Andreeva.

Special thanks to Delinur for translation and stella_marine for correction.

Five problems will be offered in both divisions and the scoring distribution will be announced later (good traditions should live).

**UPD.** Round time. Please note that Russia is not changing the timezone this night, while about 100 countries do so. Be sure to check when round starts in your timezone!

**UPD2.** Please note, that the distribution motivates you to read all the problems! Div1.: 750-1000-1250-1750-2500 Div2.: 500-1000-1750-2000-2250

**UPD3.** The results and the editorial will be published later, after the closing ceremony of the official competition.

**UPD4.** The system testing is over, results are now final. Feel free to upsolve and read other contestants code. Congratulations to Div. 1 top-5:

**UPD5.** Problem analysis is now available.

Nice... :/ A school contest that lots of students can't join in it...Cause we are at school that time :/

Your profile picture is dank my friend.

On Sunday o_0?

Schools are open Sunday in Iran.

TIL

Is Friday the only day of the weekend? I hear it also used to be so here in Turkey back in the day.

in Egypt also schools are open in sunday

Good luck!

Scoring distribution?

Also, gotta love weekend contests. ;)

What's the duration of the round? It is 2 hours on the list of upcoming contests, but the email says it will be 2.5 hours.

My bet — somebody forgot to change contest duration in that email, and 2.5 stays from previous round :)

Welcome aboard! Great deeds await us.

Good luck GlebsHP

and Good Job dalex !

It will be good job if I bring back my yellow.

Actually I'm surprised that nobody noticed that, I was just looking through recent actions and saw that Gleb had edited Mike's blog...

Now Zlobober will enter the contribution list. BOOM straight to the top.

I think that he will not enter the list for awhile

I realise that number of contest that made in this time increase why??? some of us have school and others have a work some times i missed lectures to enter the contest i think it is good to make it around 7 , 8 o'clock after finishing our work in order not to be busy

Tomorrow round will be held using the problems of Moscow team olympiad for high-school students.Obviously, at the same time.

thanks for clarification I think that the contest made by codeforces XD

How come AleX's contribution be minus when all his blogs and comments got no downvotes?

Some of his comments in Russian got negative votes.But I still think it's unreasonable because most of them got positive votes.

Sorry, I just know that comments in Russian won't show in the English format. Thanks for the answer.

Maybe he deleted some of his blogs...

http://codeforces.com/blog/entry/8963 I think this explain why

Heartily Welcome & All d Best GlebsHP

Thank you Zlobober for the great job u have done! :-)

Now it is time to rest,but start to brain storming. Good Luck for every one.

very long questions :(

Omg it started on 9AM not on 10AM local time.

After Mathematics and Physics problems in codeforces rounds...

coming soon: chemistry problems in codeforces

I hate math and physics problems too but the one about Chip and Dale is easily solvable by binary search + calculating distance between two points.

I had to solve triangle using cosine theorem and then use ternary search (search for minimum of function). Does the problem have simplier solution?

Here is my solution:

if it is possible to reach to the destination point at some time T1, then it is possible to reach there for any T2 > T1, since you can just stay where you are (you are always faster than wind so it can't force you to leave your position). So with binary search you just have to check whether it is possible to reach the destination in exactly T seconds. To check that at first calculate the position to which wind will bring you if you will not move at all and then check whether you can get to destination from that point in T seconds (sqrt(dx * dx + dy * dy) <= T * u).

LOL, me so noob %)

I've solved the triangle and found O(1) solution for the case wind doesn't change, and then used search among angles of movement before wind changes :)

Also, I'm quite sure, that it is possible to find O(1) solution for whole problem, but it requires mad_math_skillz*long_time

Also my current solution gives information about direction to fly before and after wind changes. It would be pretty if problem required it in output %)

btw, thank you, aram90

I'm pretty sure I have an O(1) solution. Coded after the end of the contest, working for the samples. Waiting to be able to submit it. Anyway, the idea:

First solve it without wind change. Basically, you need to set your direction so that your net velocity points straight to the target. If you draw some vectors, you'll see that you have two sides and the angle opposing the longer sides in a triangle and you need to figure out the third one. As sur said, you can do this with the cosine theorem (or you can forget easy solutions and instead find the intersection of a circle and a line like me...).

If solving this for the first wind velocity results in a time needed that is greater than the given T, you know you'll reach the target after the wind change.

For this case, consider a coordinate system "fixed to the air", i.e. consider a system where the wind's effect is replaced by the goal point moving in the direction opposing the wind's velocity. Now look at the path of the goal point. Before time T, it's moving with some velocity, reaches some point, then changes its velocity, and somewhere after this change is the time when you can reach it.

But at this point, the weird movements at the start don't really matter. It's the second movement you want to calculate with. But it only starts this after T. So how do you make it simpler? You pretend that it was moving in the same straight line before T.

So you move the goal position by the distance it would cover with the first velocity until T, then "wind back the clock", pretending it had the SECOND velocity all along. You set the goal position to this new point. Take care when considering the direction of the wind, its opposite, and subtraction of the opposite... If you have the V and W vectors as given in the input, and G goal position, its new position is G + (T*-V) — (T*-W) = G + T*(W-V).

This problem will be equivalent to the original, because if you consider it as the "goal point moving", it's in the same position at the same time when you can reach it. And now you can solve it with the previous method.

And yup, got AC for O(1) after some debugging: 13860359

Solving it for no wind change by intersecting a circle and a line using an ugly quadratic equation. The interesting part is the rest — modifying the parameters to find the intersection when the wind does change as described in the long comment.

Lovely soln :)

Please tell me how. My binary search solution have got WA on pretest 4.

Cool, looking forward to it.

Chip has two recessive genes for blue eyes and Dale has heterozygous brown eyes. Meanwhile Dale has the gene that makes it impossible to roll his tongue on the same chromosome.

Dale and Chip have a litter of little rodents together. Take as input the name of their baby chipmunks and the probability of DNA crossing over during meiosis. Give as output the chances that a mutation in any given codon will switch an amino acid and give the baby chipmunks purple fur.

`Div2 B`

was exactly same problem came inACM ICPC Dhaka Regional 2014. That's why people from Bangladesh could solve it earlier.However, Problem set was very much enjoyable! Thanks to the setters! :)

hahaha !! that's right !!! the only difference was we had to replaces a with b in ICPC Dhaka regional 2014 and today we had to swap.

This

`swap`

is equivalent to two`replace`

. So, it has no difference except doubling the number of query.:P

yep

Does it actually matter?If the problem was C/D then it would matter.I think none of the coders could use their previous code.And problem B is never that much difficult.So it doesn't effect that much because most of the coders who can solve B always they will take just few minutes to solve it.

well, I got really stuck on that Div2 C.... Probably sohuld have just started to solve next problems

Div 2 B WA in pretest1?

I solved it with O(26*m+n) complexity...

Here is my code... Div 2 327 B

Thanks Mayank! Elegant solution. :)

C has very weak pretests

Is a nightmare.

I thought the nightmare was something like:

Those are the easy cases for the correct solution. The tricky corner cases are when the 3 paths intersect on a tile such that it contains '1', '2' or '3'.

Isn't there just two cases?:

— Connect any 2 pairs of components with shortest routes

— Connect all 3 components to the same free cell with shortest routes

The answer is 0.right?

Right, I had to resubmit twice due to this case (my solution was printing 1).

Oh come on, I said to myself "I will handle the 0-case at the very end", and forgot it, of course. Nightmare.

"It is guaranteed that initially it is possible to reach any cell of any state from any cell of this state, moving only along its cells."

I hacked with this test, so it must be according to the statement. And my common sense tells me it obeys what you said as well.

Ohh never mind, I thought the two 3s on the top were part of the map, sorry.

Not sure if I'm the only one who didn't like the problems :)

Pretty sure you're not alone. I don't like it either but that's just because they are quite difficult for me. The problemset itself is quite nice.

My C also failed the system tests.. now I totally hate the problemset :P

How to solve Div. 2 C?

by coding of course

Brilliant sir

My solution was based on the following observations:

a_0 and a_n are always stable.

b_i = a_i if at least one of the adjacent values is the same as a_i. Consequently, b_i = 1 — a_i if both of the adjacent values are different (for i in [2,n-1]). Moreover, a_i will be stable if it is part of a continuous subsequence of the same values.

Let A be the string of values given. In this string, there exist at least two stable values (namely the end points). Let S be a substring of A such that the end points (p and q) of S are the only stable points in it. Without loss of generality, assume that p = 1. Then, the substring S' formed by removing the these two points must be alternating (either of the form 0101...0101 when q = 0, or 0101...010 when q = 1 ). In the first case, S' will eventually become 1111...111 as consequence of the previous observation. In the second case, S' will become 111...000, where the amount of 1's and 0's are the same.

I almost did the same.But i don't understand why i got WA in pretest 6.Can you check what did i miss here? My Code By the way,is there any case for which the answer will be -1 ?I didn't find anyone!

It can't be -1 , others have proved it.

Try this test case: 4 0 1 0 1

The answer should be 1 0 0 1 1

yes

The longest alternating sequence is the answer. If it starts and ends in same digit, then every digit in between becomes that digit. Else, if it starts and ends in different digit, then there are equal numbers of 0's and 1's serially.

Basically there are stable and unstable intervals. If anywhere in the segment you find

`00`

or`11`

, then they are not going to change, but any segment such as`010`

or`101010`

is going to change, depending on what stable intervals they are surrounded by.Finding the intervals is a nice application of regular expressions,

This splits something like

`110010101110100`

(I added doubled the ending coordinates, as they are stable too) into`[('', '11'), ('', '00'), ('1010', '111'), ('01', '00')]`

. From there you just have to change the unstable`'1010'`

into`'0011'`

and`'01'`

into`'10'`

and you're done...and another way with regexes using lookaround: if repetition

`"1 - NUMBER_1, NUMBER_1"+`

is surrounded with`"NUMBER_1,NUMBER_1"`

from left and with`"NUMBER_2"`

from right, then it changes to`"NUMBER_1" * (length_of_repetition / 2) + "NUMBER_2" * (length_of_repetition / 2)`

. e.g. 13873903For Div2 D can anyone show me how sample case #2 works? Cant understand how 11.547005383792516398 come out. I think it should be 20/sqrt(3);

20/sqrt(3) is 11.547005383792516398, isn't it? :P https://www.google.co.in/webhp?sourceid=chrome-instant&ion=1&espv=2&ie=UTF-8#q=20%2Fsqrt(3)

wtf im so noob :( my mental calculation become worse and worse after high school

I think we will see a lot of WA on the fourth task.

Div2 C....I thought its my lucky day when reading till second last paragraph of a problem

Haha me too :P

Can you find any case that answer "-1"?I puzzled it for a long time

My solution without "-1" case was accepted on pretests. Final sequence always exists.

Thanks

You shouldn't consider that fact a proof.

I ran my slow solution for all binary sequences from 0 to 2^20, not a single one got stuck. Enough of a proof?

Of course it is not enough for a proof, it may work to feel save in the middle of a contest, but it wasn't a demonstration at all. BTW, the proof is not hard.

Thank you very much!This is my first contest in CF.I really have a happy time!Expect next contest!

When will the closing ceremony finish?

Yeah I too is waiting for Editorials.

Please feed us with editorials so that I can go back to sleep!

Why Div.1C is C ?

Why in the previous contest div1 D was D?

why "why" is why ?

problem c ,, div 2 , when the answer would be "-1" ,, i think there is no possible case where the answer is "-1" ,, is it ?!!

I puzzled it too

The answer is never "-1". It can be shown easily by induction (

a_{1}never changes, and if numbersa_{1}, ...a_{k}never change afterksteps, thena_{k + 1}cannot change afterk+ 1 steps).When is the closing ceremony of the official competition? (How many hrs from now?)

How to solve Div2 C other than simulating?

Notice that any substring containing more than one consecutive zeroes/ones will remain as it is, so the only case we have to think about is 10101... If you notice carefully, after each move the leftmost and the rightmost digit of this substring will become safe (it will become equal to whatever is beyond it), so you can easily come up with a O(N) solution. So we just have to update cnt as max(cnt,(length of unsafe substring+1)/2))

Div-2 C >>>> The Great Wall Of China..(for my rating) :-( When can I cross it?

Hey decoder123 check you inbox

Looking at the hacks, looks like DIV2D / DIV1B will give many WAs..

What was the hack that dreamoon_love_AA used four times?

I think many competitors didn't consider, that tau-corss-shape road may be shorter, than two roads connecting two pair of countries

Oops, sorry, my comment applies to Div2E/Div1C

If you write something like while(hi-lo > 1e-9) and using variable with double, or you set hi < 5e7, you will fail in following testcase:

10000 10000 -6470 -10000

969 1000

616 748

616 748

And what is the output of this test case?

My program give 50211053.368784316000000000.

O.o? Why does while(hi-lo > 1e-9) break? Does it time out?

What is wrong with while(hi-lo > 1e-9), exactly? I used long double there.

I guess long double will pass it.

I have used float..should I expect a WA? UPD: I have used double..I forgot..got AC

Yes.

Of course. I believe we should never use float.

precision killed me...

Tasks were ok, the idea for the second is pretty standard, the third task is cool, the fourth is good, but I couldn't solve it on the time. The fifth task I didn't understand.

But the texts were awful. In the first task we have one not important part, in the thrid task the main thing wasn't on the right place ( ai=0 or ai=1) and samples in the fifth task weren't explaned...

Thank you for the contest GlebsHP, I am waiting your new round !

I solved Div2 A and Div2 C easily, but for some reason I had quite a lot of trouble with Div2 B. The only way I could think of in the end was to keep swapping integer arrays to denote swap of two letters. Does anyone have a better way ?

How do you solved Div2 C?

You have to find all alternating sequences. The longest alternating sequence will provide the first answer.

My algorithm is based on the followings:

1) If the alternating sequence has odd length , then the sequence has same bits on both the side (You can easily prove how). So this sequence will eventually be consumed by those bits to become stable.

2) If this sequence has even length , then the sequence has different bits in each side (Again, the proof is easy). First half of the sequence will be consumed by the bit on the left and the second half will be consumed by the bit on the right.

3) Step required is ceil(length/2). The answer is the maximum of them.

Solution passed the pretests. I am a little bit worried about the -1 case though. I am pretty sure this case doesn't exist. But I couldn't prove it.

yeah, passed system test. So -1 case doesn't exist (Proved) :v 8-)

You can make temporary mapping array 'a' -> 'a' ... 'z' -> 'z', simulate on it for O(26*m) and apply it to string for O(n)

you can use a array f[] to store the letter's meanings.

and for every swap operation , you can updata your f[] array in O(26) Time.

Please use update instead of "updata". There is no such word.

Besides, I don't like your avatar.

Me neither.

How long till the closing ceremony?

Results will be approximately at the 19:17 GMT+3 25.10.2015

Really?How did you know?

Great problems ! I would have loved to spend more time solving problem D during the contest, lost so much time to understand that I needed "cin.ignore()" in problem B :(

Thanks for the contest.

At least are we going to be allowed to check others submission's ??

Is there any information on when the closing ceremony will finish?

A round announcement without thanking MikeMirzayanov :D

Why should we wait with the results until the closing ceremony's end?

This is to keep up the excitement of the on site contestant until the declaration of the winner names at closing ceremony.

*Pending system testing

More than 1 hour and even system testing not started. So, how its 1 hour rating system :P

When the closing ceremony will end ?? :(

No sign of closing the closing ceremony.

What is wrong with Div 2 B solution? Both fail on testcase 1.

Brute force — https://ideone.com/YvASbz Runtime Error — https://ideone.com/cy83S0

Do you start the testing?

what's happen in the codeforces??

Why kill the time? plz start the system testing. Every one waiting for system testing.

I think it is because of the onsite events. They cannot start system test now. If they did, there would not be much fun in the closing ceremony(or something like this).

Please notify us with any comments. What causes this delay?

UPD3. The results and the editorial will be published later, after the closing ceremony of the official competition

Seems like contest is not of 2 hours but of entire day ;)

System testing started. Feeling emotional :P

Finally system testing started !!!! -_- :D

why TLE?

System testing finished but practice mode is not enabled! Why?

UPD.It's now fixed.still not able to see testcases and submissions :(

Why is there so much delay? 1. there was delay in testing 2. now practice mode is not enabled 3. there is no editorial uptil now. 4. I can't see other's submissions.(What is the point of making submissions invisible until system testing is over)

Please do it quickly.

5)Rating has not changed yet

Was worried about plateauing for a while but it seems like I'm still improving!

Feel free to upsolve and read other contestants code. Yes, i'm feel free while the others codes are blocked <3I am a Div 2 participant. My submission for question 1 was processed by the server twice. Hence there were two submission both at the same timestamp. Also, I was penalised 50 points as resubmission. Why did this happen? Can something be done regarding this?

Why rating change is so delayed ??

Why only Div. 1 winners ? What about Div. 2 winners (or top 5) ??

Is this round even rated ? !

Ah i wish it is unrated. :-P

Hope it too.

UPD4. The system testing is over, results are now final. Feel free to upsolve and read other contestants code. Congratulations to Div. 1 top-5:How?.

By asking the other contestant to share his/her code via ideone (feel free to ask them to share their codes :P )

Then how can we see the test cases? :D

who told you to feel free to see the test cases? :D

Still unable to "read other contestants code"

"I give you A you give me B"... this won't be considered as cheating now :P

Rating — time limit exceeded.

these people have no idea what theyre doing

Was this round rated? Or is the rating change delayed for some reason?

I have been starting to wonder the same thing. And it was my first time solving C too :/

well this problem C was the only problem C in these recent contest which needed a bit of thinking :) others were just brute force and corner cases (we call it tof in persian )

Actually, I need to rephrase. It was my first time solving 3 problems. And yes, I think you are right. In some of the previous contests, I somehow found B harder than C.

lol be happy u still have some coffee mine is finished :/

Editorial?

*waiting

(irony of a meme: there is no edit option to correct spelling or grammar)

We can't "read other contestant's code" yet GlebsHP :P

Atleast make the testcases public. Can't wait to see where i went wrong in Div2 C.

try this :) 101010

Getting output:-

2

111000

correct try this 5 1 0 1 0 1 and 5 0 1 0 1 0 and 5 0 1 0 1 1

2

1 1 1 1 1

2

0 0 0 0 0

1

0 0 1 1 1

correct ! I have no idea then :) what is the order of ur algorithm ?

It's O(n) Finally found out the mistake. Implemented it in the wrong way. Thanks for your help.

ur welcome

I am quite disappointed in today's problemset, especially since there was like 20 people involved in preparing the contest. For me ideas for B, C, D are quite old and standard (and I'm guessing many people feel the same way, as there are 45 people passing all 4 problems, and much more passing pretests). And did authors know that D has observation that s < 6000? How can it worth 1750 points?

It is impossible to have five problems with new idea every round. What we try to achieve is to offer something new to everyone. The result is that for almost everyone there will too easy and too hard problems, but at least one problem will be the right challenge to his\her solve\write abilities. Problem E was your challenge yesterday.

Zlobober back maybe ? :D

Looks like GlebsHP is counting rating manually :)

or maybe code that computes rating is like this:

hi first thank GlebsHP for prepare The Contest, the problems are very nice and creative:) but system rating... :(

For those interested, here is a much easier version of three states. http://www.usaco.org/index.php?page=viewproblem2&cpid=88

The problem is very simple anyway :)) In my opinion, it was the easiest div1 problem from the contest

Finally we can see submissions. I hope ratings will be updated soon. :)

Never had such bad experience before. Everything seems messed up. :( system testing has finished 3.5 hours ago but, no rating change. Still can't see others code and test cases !!

Now you can.

They should change Codeforces' logo for this blog to something like

13849187 , what is wrong with this code? Why is the output blank? It runs fine on my compiler

http://codeforces.com/contest/591/submission/13860498

Don't use gets(). Try it with cin.

Never use both c++ io and c io while you have closed the synchronization of them using "ios_base::sync_with_stdio(false)".

Finally rating change. o_o Waiting for saturday contest. :)

waiting for solutions for the contest...

Editorial in Russian will be published in approximately 10 minutes. Unfortunately, English one will be published only tomorrow.

How to solve problem D? I used ternary search to find the best angle we have to move until time t and them go directly to destination. (or go to destination under t seconds). but my code couldn't even answer the first test case. here's my code http://codeforces.com/contest/591/submission/13852036

You don't have to care about the angle, all you need to care about is the time taken. Say that you're making a guess that the trip will take h seconds, and the other variables are as given in the problem statement. That means that during that trip you will be moved to the direction vx,vy for min(h,t) seconds and to the direction wx,wy for max(h-t,0) seconds. When you know this, you can move your starting position to x = vx*min(h,t) + max(h-t,0)*wx + x1 and y = vy*min(h,t) + max(h-t,0)*wy + y1 to compensate for the wind, and pretend there's no wind. Then you can just check whether you can get to the destination from your new starting position in h seconds. Now that you can check if the trip can be made in time h, you can just make a binary search.