Hi everybody! There will be a Codeforces Round for both divisions today at standard time set up by me.

My teammates from ICPC team Moscow SU Trinity sankear and malcolm helped me a lot while preparing this round, also there were lots of useful tips and advices from MikeMirzayanov, applause for them. English translation was made by our veteran translator Delinur.

As usual, there will be five tasks for two hours. The scoring will be announced later.

See you on the round! I hope that each contestant will be able to find something nice in ongoing problems.

**UPD**: Scoring is standard.

**UPD2**: Due to technical issues the round is delayed by 15 minutes. We are sorry for an inconvenience.

**UPD3**: We are sorry for an inconvenience with the task Div1-D. The pretest #16 wasn't satisfying the constraints n, m, k <= 200000. The system testing for the first division will be delayed. If you think that you were affected by this test, you may write me a message and we will make this round unrated for you.

The system testing for the second division will happen shortly, as usual.

**UPD4**: System testing is complete. Congratulations to the winners!

Div1:

Div2:

**UPD5:** the English editorial was added.

First contest without saying thanks to Max Akhmedov (Zlobober) :)) ;) :D I'm really looking forward to participate in this contest ! \:D/

So we should say thanks to Zlobober :)

For some reason round writers never thank themselves..

I'll show you a counterexample ;)

Spoiler alert!!

Wait for a div1 round for a long time! I can't wait any more!

Since the last contest, div2 were waiting the same amount of time

I am div2,and I am proud.I want to become blue gay!

you can (;

gay....do you mean "guy"?....

Nope, he said "blue" :D

Understand you. Yaoi manga is very nice!

Waiting...

daiyu.

this contest is for Iran Good Bye 1393

happy new year!

actually Good Bye 1393

happy new year! :D ( 4 shanbe sooriam hast :-P )

I love your contests,very nice! Zlobober ,you are my idol :P

I missed CF' rounds. It is good to see new round. HC && GL to everyone :)))))))))))

at standard timeT_T...Great thanks Maxim Akhmedov Zlobober preparing the contest :D

"Moscow SU Trinity sankear

иmalcolm"Please change this to

"Moscow SU Trinity sankear

andmalcolm"Done, thanks.

All non-russian-speaker codeforces users became to know that "и" means "and" so there's no problem

My first Contest! Yay!

Your user name and the way you comment sounds fishy. But I'll just let it slide.

Finally ... we are so thirsty for contests. I think that I will not be able to live without codeforces.

This is the first time I do with contest Div.1. I hope will get some interesting in this contest.

what is difference between div 1 and div 2?

If your rating is >= 1700, you will compete in Division 1. Else, in Division 2.

Both divisions have 5 problems but Division 1 has harder problems. In fact, usually the first 3 problems of Division 1 are same as the last 3 problems of Division 2.

Here's more information regarding rating.

what is the diffeerence between div1 and div2

Hey, what are FAQ for?

lets define function F — number of different characters between two strings, then we could do something like that:

difference = F("div1", "div2") // should be 1

Why all of these peoples speak english ?

I missed many CF rounds becoz of internet & load-shedding problem..Thanks @Zlobober for this round. Hoping for nice problems..Wishing Good Luck & High Rating to everyone !! :)

div2终于来了

We'd better use English -_-#

oh,my god....I should get it earlier.

Hint:comments in russian are not shows in english version.

Exactly on 4shanbe-soori!

Thanks for contest. This contest is on our(Iranian) National celebration ( charshanbe suri).

More information can be found here

Thanks .

Is It also celebrate in your country ???

yes it is :D

"Before contest" countdown actually doesn't correspond to the time on the timeanddate.com, the difference is about 2 minutes. (I noticed because I realized that my PC time is not equal to the codeforces one, but I have synchronization enabled :)

Delay

time extended

Wow added 15 minut

15 minutes delay, why?

Forgot to register, why God why ? :/

you can register now

no extended registration for div2 :( ????

fixed. try again.

registration is still open.

You still have time to register because of the delay

wow, thanks God

in fact — god reply your wish ! (like i reply to your comment khkhkhkhkh)

Hi, I could not register in time because of the technical issues (and i logged in late). It says div 1 registration is still open but div 2 is closed? Edit: its open, thanks!

The contest is not started right time.15 minutes late will be started.

Some people might have thought that "in at most an hour" means at least half an hour. I would suggest postponing it further to start at 19:00, so that no complaints can be made.

Nope, their fault i can't wait anymore

This was an old message , MikeMirzayanov forgot to change it back to "codeforces is temporary unavailable"

It's too late in China. 8 hours later I have to have class...

I was late to join contest. Therefore I entered into the codeforces to see about the condition of my friends. But now I can see it is 15 minuets late again!!! Now I can participate to the contest. First time the delay of codeforces becomes good for mine. :-)

you're lucky :-)

The contest is not started right time.15 minutes late will be started..

"We have to upgrade infrastructure...

Let's do it 5 minutes before the contest!"

I must go to sleep because I will go to school in 5 hours later.The sadness of UTC+8.

tqvenii deda movtyann D amocanis 16 testis shemdgenels movutyann suyvelaperiii,2 saati tyvila gvawerinebb xalxss tqvenii suyvelaperi movtyan,mtestavidan dawyebuli mtargmnelidan damtavrebuliii,puiii

Usually after contest there are lot of guys who complain —

Why there were no maxtest among pretests?And today, in order to prevent such comments, authors decided to put into pretests not only maxtest, but even test

larger than maxtest:)It was Good contest but I wish it had more time

Any hints for Div2 B?

Div2 C: Time Limit Exceeded in pretest 11.

How to solve DIV2-D/DIV1-B ?

Let's reverse a problem:

Points

aandbare connected only if distance between them issmallerthan sum of their weights.In this case, we can imagine one point as interval [

x-v,x+v].When two intervals overlap, corresponding points are connected.

To find a result, we need to find the largest subsets of intervals that are not connected (in original problem — the largest where every two are connected).

Why do we need reverse problem? Because it makes everything much more easier. Every point correspond only with one interval (in original problem — with two) and simple sweep from left to right will do whole job.

First of all, if x_a < x_b < x_c and a connected to b and b connected to c then a connected to c, so if we have connected sequence of points it's a clique. Now we should find largest connected sequence of points. Let us consider the points with weights as segments with length as two weights and centered in point. We are looking for max set of non-intersecting segments. Here we get events: starts end ends of points. Sort them and go from left to right. When segment starts, answer for this segment (size of the max set of non-intersecting segments from segments from most left segment to segment under review) is max from already closed segments plus 1. It's just a variable, which is updating then segments closes. 10322276

Sort the point by the coordinate. Consider 3 points i, j, k (i > j > k). If there are edges (i, j), (j, k) then there'll be also edge (i, k). Because:

x[i] -x[j] > =w[i] +w[j]x[j] -x[k] > =w[j] +w[k]< = >

w[i] -w[k] > =w[i] + 2w[j] +w[k] >w[i] +w[k]<=> there is edge (i, k)

That means if we add i to the clique which contains j, when we'll have a new clique.

Now everything left is a simple DP with Fenwick tree :D You can check my submission for more detail :D

:D This is so overkilled.

That's how I made it too, and it took me about 10 minutes :))

I also spent a long time thinking about the meaning of that formula. Suddenly I realize that they are just circles center at xi with radius to be wi

And answer is the maximum subset of circles that doesn't intersect with each other =)

QAQ , Consider 3 points i, j, k (i > j > k). maybe it is x[i]>x[j]>x[k] ???

Sort the point be the coordinates. Then it's the same :D

Its a lot more intuitive than converting the problem to counting non-intersecting circles, according to me.

Is the contest unrated for div2 participants??

Really hope not!

Contest is rated for Div2 participants.

Contest is unrated only for those Div1 participants who write me a private message shortly.

Why would it be unrated?

You can get the answer at

UPD3:)Huh, 67 people did problem with FFT :o, nice.

I solved it with brute force. Ran max test in 1.6s in Custom test.

UPD: It passed sys test.Yyyy, seriously xd? Just check every occurence naively xd? I hope it's not offensive, but I really hope that this won't pass :p.

It's not very naive. I did it with bitmasks, so runtime is

T(N^{2}/ 32). This solution does not depend on any property of the test, so unless custom invocation runs faster or I made some stupid mistake, it'll pass.This problem reminds me of 472G - Уроки дизайна задач: увеличиваем ограничения. They feel very similar to me, with solution being FFT (which I don't really know), and looks possible to solve with bitmask stuff.

What is the meaning of T(), I have seen it a few times ago?

T is number of step, meaning it doesn't ignore constant factors.

Huh, funny, I didn't know this. Is it formally defined or is that auxiliary notation introduced for competitive programming purposes?

I think I have seen them in OCW videos, though not sure :P

T(n) is used as running time on problem of size n in "Introduction to Algorithms", so I think it's not limited to CP purposes.

I think that this is something different.

T(n) as you described now can be equal toO(n^{2}), it is not consistent in any way with the meaning ofT(n^{2}/ 32) you used before.Disclaimer: I'm always confused by these things, so I may be speaking non-sense.

Since

O(N) is upper bound function, we can havef(N) =N=O(N) =O(N^{2}). And in hereT(N) means true value of runtime (?) So what is wrong withT(N) being equal toO(N^{2}) ? For me, this only means that, in most cases, we should useΘorTinstead ofO.What I'm saying is that you wrote

T(n^{2}/ 32) while you should have written sth likeT(n) =n^{2}/ 32, becausenisT(n) meanssizeof the problem andn^{2}/ 32 ain't one.By the way I think that Θ would be more appropriate here, because for me

Tis used rather to write down some equations for complexities likeT(n) ≤ Θ(n) +T(3n/ 4) +T(n/ 5) like in algorithm of finding median.Tcould be used asO(sth) as well, doesn't have to give strict bound.Ok, I see the problem now. Thanks! :)

Thank you, and Swistakk too! :)

I guess the most common notation of complexities are

Ofor upper bound, Ω for lower bound, and Θ for strict boundIf you used the bitmasking optimisation, it's not really brute force. It's as if you said you ate pancakes: yes, the meal is called that, but pancakes themselves usually make up just a small portion of the meal :D. That you used a clever trick to make a brute force algorithm run fast, it doesn't mean you solved it just with brute force.

I am surprised that this problem was used for today's contest; its solution is described at e-maxx.ru

(one of most popular sites with algorithms for competitive programming in russian)in article about FFT, so it should be well-known for russian-speaking participants.As for me, it's completely unclear how the problem is related with FFT... So existance of solution on the internet does not help much

Div1.D was FFT, right? I don't know FFT but knowing what problems can be solved using it, I think so.If no, how to solve it? :)) all the problems were nice except of div1C which would be nice if it hadn't had the case with self loops.I solved it fot the tests which didn't have that case but, of course, I didn't get any points...

What is your solution? I wrote Euler path and for my solution it doesn't matter if graph has self-loops.

Woow, it seems that you have a very nice solution.In this case, C was very nice too :)) My solution was some strange thing, sth like this: I was making a bfs, building the tree and the edges out of the tree were chosen random(or from x smaller to y bigger) and I than, using these edges, I was fixing juste the sense of the edges of the tree, from leaves to the top.Can you please explain your solution?

Firstly, link all vertices which have odd degree. Now graph has Euler cycle. Suppose it's

c_{1},c_{2}, ...,c_{m}. Then we output edges . But there is a problem when graph has odd number of edges. In that case we need to add edge .Thanks :) I understood and the idea is preety cool

Actually, there's a bit more. Consider a test

Here 1, 3, 4, 6 have odd degree. If you connect 1-3, 4-6, then you'll have to add two more edges to deal with components with odd number of edges. However, 3-4, 1-6 yields a single component of size 6, so this is better.

In general, it is optimal to connect all odd-degree vertices in such a way that all components involved merge into a single component.

But there is only one component in the graph.

Indeed, it was easy to miss something in this kind of statement. Also, the announcement said something about "the construction should not be connected in any sense", which I fail to understand in this case.

They probably meant that your orientation of the edges should not guarantee strong connectivity or something like that.

The graph is connected.

`The cables are put so that each computer is connected with each one`

`perhaps through some other computers.`

Other possible solution, without Euler cycle, after linking verticles with odd degree: in DFS tree, make all edges that are not in the tree go up (towards the root). Then, for each verticle, starting from the bottom, direct the edge to the parent either up or down, such that # of incoming and outgoing edges is even. The only possible case where we need to add a loop is the root.

Yes solution for Div1.D is FFT.

1) Iterate over 'A', 'G', 'T', 'C'

2) Let's denote current letter c. Construct new string a' and b': a'[i] = [exist a[j] = c and |j — i| <= k], b'[i] = [b[i] == c].

3) Now lets apply b' to a' with offsets 0, 1, ..., n — m and calculate scalar product for each offset. If the value of scalar product is not equals to the number of ones in b' than offset is bad.

4) If offset is not bad for all four letters than it's good.

Third step can be processed in O(n * logn) time: let's duplicate string a', reverse string b and multiply them. Now in positions from m — 1 to m + n — 2 we have the scalar products that we need. Multiplying we can do using FFT.

Hi, may you elaborate it a little bit?, please

was difficult. can't solve Div2-C, what is needed there? map?

I answered queries in reversed order with disjoint set union, but I think that there is simpler solution.

it can be solved in O(W+H+N)

I used multiset for distances between cuts and set for coords of cuts

I used segment tree to solve it, I hope it will pass. The idea is for each column to store the maximum width of a rectangle using this column. It is the same for the rows. When I was reading the codes of people in my room, I saw solutions with sets or priority queues. Can somebody explain such solution?

My solution:

set HCut, WCut — coords of cuts (at first (0, h) and (0, w))

multiset DistancesH, DistancesW — distances between adjacent cuts (at first (h) and (w))

If we've got query (H x), we:

Search in HCut iterators, pointing at two elements which less and greater than x (We always can do it). Suppose, we found it1 and it2 (*it2 > *it1).

We delete from DistancesH (*it2) — (*it1) and add (x-(*it1)) and ((*it2)-x)

Print max(DistanceH)*max(DistanceW)

Add to HCut x

Hi, can you please tell me whats wrong with what I've done? I got a TLE on this: http://ideone.com/SHyKGR

My algorithm is the same as what you've suggested. Thanks for the help in advance.

lower_bound() is too slow for set operation because set<>::iterator ain't random access iterator

you can first insert pos into the set, then go up and down a bit.

10332363

You can also change lower_bound(XXX.begin(),XXX.end(),pos) to XXX.lower_bound(pos). It will get AC.

Oh so my lower bound was doing a linear scan. Thanks, guys. I got it accepted by changing that :)

The smartest solution I saw someone using was using DSU.

You could solve the problem backwards by merging X-axis and Y-axis intervals and updating the largest intervals if the merged interval is larger than the current one.

The algorithm itself is

O(nα), isn't it?thanks 4your ideas.

First time of playing hacks, so interesting.

Btw you can check your div. 1 A,B,C solutions in upsolving of div. 2 contest.

It's also tested almost instantly there, looks like all submissions are already tested and results are cached.

i know its silly -> a little hint about A-Div2 ?!? so, this is math , no programming -_-

here is pseudo-code for Div2 A

while(a>0 && b>0) { if(a>b) { res+=a/b; a%=b; } else { res+=b/a; b%=a; } }

It was nice. Thank you.

Div2-B — TLE54

Div2-C — AC

It is sad when you can't solve easy tasks:D

I can't understand this test in Div2B: 2 xy zz

Why is the answer: 1 1 2 ?

We transform strings as xy->yx and have: yx zz

And the Hamming distance IS THE SAME!!!

Test #11

2 xy zz

Output is 2 -1 -1

Sry(

Check out my crazy div. 1 B solution, lol 10326839

How to solve Div1 B?

Update:I missed this comment where tom describes his idea.x1 ≤x2, thenx2 -x1 ≤w1 +w2, which can be transformed tox2 -w2 ≤x1 +w1. So, build a pair<int,int> array with the values {x-w,x+w} for all points.DP[i] be the maximum clique we can build using points with indices ≥i. Let's iterate the elements from the new array from the last one to the first one (from N to 1) then if we're processing indexi, we do a binary search to find the first elementjsuch thatx_{j}-w_{j}≥x_{i}+w_{i}, and setDP[i] =max(DP[j] + 1,DP[i+ 1]). The answer will beDP[1].Sadly, it took me an hour and a half to figure what to do with the values

x+wandx-w(the last step)...Thank you, this idea seems to be similar to tom's. Instead of DP, a priority queue can be used. Sort the segments by their left coordinate and the queue's top element will be the one with the smallest right coordinate. At each step, pop the top element while it's right coordinate is less that the current's segment left coordinate. Then, insert the current segment and compare the size of the queue to the answer(I just described the algorithm that I always use to find the number of maximum segments that intersect).

Unfortunately, I didn't figure out the {x-w ; x+w} representation of the points... :)

will you post the editorial ?? the problems were really hard for me :3

In problem 527B - Система коррекции ошибок, what would be the correct output for the case:

10318065 this Accepted submission gives:

Is it ok? Zlobober

sankear, malcolm, MikeMirzayanov

We will add investigate this test and probably add it, thanks.

I also thought on this problem, too.

Didn't realize why 10315968 got accept until reading this thread. My test case is:

I thought the correct output should be:

But the below output also passed:

The problem says it must be "as small as possible" not just "reducing some".

Will system testing run again with more comprehensive test cases?

Never, for sure! past is past! Codeforces always thinks about future! :D

This contest is just a disaster. Problem C in div1 is written so badly. I am just shocked how could the author write such a long dummy boring story instead of just a few lines?

And the problem D has a wrong pretest, which lead to few people passing, and more contestant are scared and won't read the problems at all!

Because such failure in both C and D, I suggest an unrated contest for all div1 contestants.

The storyline is okay. The world would be boring if every problem has a description like "Given blahblah, you need to find blahblah". The real problem is the key point was hidden in one or two unremarkable phrase, make it difficult to understand.

I (blindly) guess that the original problem statement was written in Russian and this is a translation issue.

You are right. Russian statement was very clear.

Unrated contest because of long statement? Isn't it too forward? Indeed some people were affected by wrong test, but that is a small amount and most of them ended up with a decent position, so it is not helpful for them to make contest unrated :P

I strongly disagree:

1) "And the problem D has a wrong pretest, which lead to few people passing, and more contestant are scared and won't read the problems at all!" — problem D is expected to be pretty hard and most people in Div1 know it, those who decided to try it and actually got a solution are very small amount of all Div1 participants, and those who didn't try it — didn't even realize that there was a wrong pretest. Of course it's unfair for those who've tried it, but an option to unrate their participation is available, so why make other people (like me) who didn't even attempt the problem unrated?

2) Problem C while a little bit confusing had an amusing story and the pictures cleared it up for me. I think if you read it carefully you would also find it understandable. The problem is very nice actually and I enjoyed coming up with a solution for it even though I couldn't debug it.

I agree with 1st point. I misunderstood problem statement of C and tried to solve a different problem, until I saw the announcement :(.

Like! But I really don't wanna this contest to be unrated. I believe many contestants having the same idea with me.

I used to think 40 minutes is the longest time for me to understand a problem...until I spent almost one hour in reading problem C again and again

Hah, yes, that one was pretty confusing, I needed to read this many times too :P.

Why you finished testing div2 before starting test div1? We can self test by submitting div2cde and we can message you to unrated if there's something wrong in the programme.

I think that the

unratedoption is only in case the test for Div1 D affected you and the code for Div1 D cannot be submitted in Div2.If my ab are wrong and I have submitted d using fft, then I will certainly try to be unrated

Finally I know my program of finding Euler's circuit used several times is O(nm). What a sad story.

Zlobober why my rate still the same .. is it unrated contest

Give me a treat, your rating is increased! Your rating change

What a fantastic round for Poland! Never seen such performence earlier! :)

Thanks Dear happyBirthDayBeni ... ^_^ I was really surprised ... I love U ... :D/

Thanks Dear happyBirthDayBeni ... ^_^ I was really surprised ... I love U ... \:D/

Thanks Dear happyBirthDayBeni ... ^_^ I was really surprised ... I love U ... \:D/

I have a question about the next contest:

"VK Cup 2015 — Round 1 (online mirror, Div. 1 only)"

Can a Div. 2 contestant take part in this contest?, at least 'out of the competition'?. Thanks.

I was afraid to become orange when I finished debugging C 30 seconds after the contest has finished.

Indeed a close call :D

can i have some help on Div 2 D it gives WA, first sort due to coordinates then the idea is to run dfs from (n-1, ..., 0) considering that (i, j) is connected if (x[i] — x[j] >= w[i] + w[j]) and we know that if (i<j<k) & (i, j), (j, k) are connected then (i, k) is connected and maximize the counter this is my code where is the wrong part ?!

During the contest, I thought bitset couldn't be used to solve problem D. Its complexity is , and I thought it would take at least 10s.

However, after the contest, I found it could pass system test actually and took about only 1.5s.

How can it be so fast......

I still can't understand what's the meaning of div1C...

http://codeforces.com/blog/entry/16996 the problems were nice but the pretest 19 for Div 2 problem B was glitchy. for pretest 19 I got the answer(output) for the minimum hamming distance to be 524. The output given by the codeforces system too is shown to be 524. but then next line i am shown this error :

"wrong answer value presetned by contestant is different from the actual hamming distance: contestant = 524, actual = 526"

even though before this the pretest logs show this:

Test: #19, time: 46 ms., memory: 32 KB, exit code: 0, checker exit code: 1, verdict: WRONG_ANSWER Input 1000 bbabbaabbabbabababaabbabbbbbaabbaaaabbababbaaabbabbbabaaaabbabaaaaa....

Output 524 1 2 Answer 524 999 1000

so my output matches the system output yet i was given verdict of wrong answer...

I believe it means the

524doesn't match with1 2Although you give the correct answer, but the index of

iandjare wrongEDIT: changing

`print i+1, j+1`

to`print ind[i]+1, ind[j]+1`

will correct the problem, but result in TLE. The double for-loop makes this approach very slow. The complexity is O(N^2)i checked other peoples code too they have given answer 524 but the second answer is different from what the system has given but even then their answers have been corrected.

The second line can be different because multiple answers could exist.

In your case, you answer is wrong. I have corrected it for you in the last post.

EDIT: To be specific, the minimum value after at most one swap is indeed 524, but exchanging the letter at index 1 and 2 won't achieve the minimum, it was 526

yeah i see now.. thanks

the error did not show up in all those 18 pretests lol

You can look at my submission 10333076

Editorial?

http://codeforces.com/blog/entry/17020

For div2 C, I just used priority_que and set to simulate cuttings, and got AC.10325360 But I made a data: 200000 200000 199999 V 1 V 2 ... V 199999 I run it locally, write the output to a file and got nearly 4 seconds..(turn off the output, and got 1.9 seconds) 199999 pops and 399998 pushs in total.. So that was really lucky..

some1 needs to do something about these fake winners,i mean unrated

I am waiting to be able to solve at least two out of Div.2 C/D/E . Then I will submit. What do you mean by fake?

Now that I read one solution to Div.2 C , it seems so easy. Why didn't it click earlier? :(

Because your account is fake!!

When will the tutorials be available for div2 problems?Especially for C,D,E problems.

I am still stuck on Div.2 E:

Idea so far: Start with the original graph. I. While there is a pair of nodes with odd degree add an edge between them. (Observation: because of the pair of cables condition we need at least that many new edges.) II. Find an eulerian tour. Create the graph defined by that tour. III. Follow the tour and whenever we leave a node with odd indegree / odd outdegree reverse the current edge to fulfill the pair condition on the node we left. IV. When we are back at the start node it's in/out degree might have become odd. In that case add a self edge to that node.

And here I am stuck: Does this give an solution or might it have one edge more than a solution? Maybe trivial and I just don't see it.

Here's a nice explanation

Oh, thanks. Silly me didnt notice those posts above.

can't see the editorial :( who can help me explaining the DIV2-B case 1&2 ,why both of the output is 1.

You can see Here

I really enjoyed the problems although I was to noob to manage to solve C,D,E div 2. A friend told me that in order to solve them I required to know FFT. Can anyone explain me the solutions to these problems based on that algorithm?

Indeed, your friend was right. Here you can find some applications of the algorithm called "Fast Fourier Transform" http://en.wikipedia.org/wiki/Fast_Fourier_transform .I hope this helps.

where are the editorials

http://codeforces.com/blog/entry/17020