Zlobober's blog

By Zlobober, 7 years ago, translation,

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.

• +368

 » 7 years ago, # |   +23 First contest without saying thanks to Max Akhmedov (Zlobober) :)) ;) :D I'm really looking forward to participate in this contest ! \:D/
•  » » 7 years ago, # ^ |   +12 So we should say thanks to Zlobober :)
•  » » » 7 years ago, # ^ |   0 Special Thank's Zlobober and MikeMirzayanov
•  » » 7 years ago, # ^ |   +2 For some reason round writers never thank themselves..
•  » » » 7 years ago, # ^ |   +5 I'll show you a counterexample ;)
•  » » » » 7 years ago, # ^ |   +5 Spoiler alert!!
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 Many Many thank's Zlobober . Total contestant's about 6500+ both Div 1 and Div 2
 » 7 years ago, # |   0 Wait for a div1 round for a long time! I can't wait any more!
•  » » 7 years ago, # ^ |   0 Since the last contest, div2 were waiting the same amount of time
•  » » 7 years ago, # ^ |   0 I am div2,and I am proud.I want to become blue gay!
•  » » » 7 years ago, # ^ |   0 you can (;
•  » » » 7 years ago, # ^ |   +31 gay....do you mean "guy"?....
•  » » » » 7 years ago, # ^ |   +13 Nope, he said "blue" :D
•  » » » 7 years ago, # ^ |   0 Understand you. Yaoi manga is very nice!
 » 7 years ago, # |   0 Waiting...
•  » » 7 years ago, # ^ |   0 daiyu.
 » 7 years ago, # | ← Rev. 4 →   +7 this contest is for Iran Good Bye 1393happy new year!
•  » » 7 years ago, # ^ |   +13 actually Good Bye 1393
•  » » 7 years ago, # ^ |   +1 happy new year! :D ( 4 shanbe sooriam hast :-P )
 » 7 years ago, # |   +1 I love your contests,very nice! Zlobober ,you are my idol :P
 » 7 years ago, # |   0 I missed CF' rounds. It is good to see new round. HC && GL to everyone :)))))))))))
 » 7 years ago, # |   0 at standard time T_T...
 » 7 years ago, # |   +3 Great thanks Maxim Akhmedov Zlobober preparing the contest :D
 » 7 years ago, # | ← Rev. 3 →   +2 "Moscow SU Trinity sankear и malcolm" Please change this to "Moscow SU Trinity sankear and malcolm"
•  » » 7 years ago, # ^ |   0 Done, thanks.
•  » » 7 years ago, # ^ |   +13 All non-russian-speaker codeforces users became to know that "и" means "and" so there's no problem
 » 7 years ago, # |   0 My first Contest! Yay!
•  » » 7 years ago, # ^ |   +5 Your user name and the way you comment sounds fishy. But I'll just let it slide.
 » 7 years ago, # |   0 My first contest!:)
 » 7 years ago, # |   0 Finally ... we are so thirsty for contests. I think that I will not be able to live without codeforces.
 » 7 years ago, # |   0 This is the first time I do with contest Div.1. I hope will get some interesting in this contest.
•  » » 7 years ago, # ^ |   0 what is difference between div 1 and div 2?
•  » » » 7 years ago, # ^ |   +5 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.
 » 7 years ago, # |   -6 what is the diffeerence between div1 and div2
•  » » 7 years ago, # ^ |   0 Hey, what are FAQ for?
•  » » 7 years ago, # ^ |   +34 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
 » 7 years ago, # |   +3 Why all of these peoples speak english ?
 » 7 years ago, # |   +9 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 !! :)
 » 7 years ago, # |   -11 div2终于来了
•  » » 7 years ago, # ^ |   0 We'd better use English -_-#
•  » » » 7 years ago, # ^ |   0 oh,my god....I should get it earlier.
•  » » » » 7 years ago, # ^ |   0 Hint:comments in russian are not shows in english version.
 » 7 years ago, # |   0 Exactly on 4shanbe-soori!
 » 7 years ago, # |   +5 Thanks for contest. This contest is on our(Iranian) National celebration ( charshanbe suri).
•  » » 7 years ago, # ^ |   +5 More information can be found here
•  » » » 7 years ago, # ^ |   0 Thanks .
•  » » » 7 years ago, # ^ |   0 Is It also celebrate in your country ???
•  » » » » 7 years ago, # ^ |   0 yes it is :D
 » 7 years ago, # |   +8 "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 :)
 » 7 years ago, # |   0 Delay
 » 7 years ago, # |   0 time extended
 » 7 years ago, # |   0 Wow added 15 minut
 » 7 years ago, # |   0 15 minutes delay, why?
•  » » 7 years ago, # ^ |   0 they might be updating some infrastructure .
 » 7 years ago, # |   0 Forgot to register, why God why ? :/
•  » » 7 years ago, # ^ |   0 you can register now
•  » » » 7 years ago, # ^ |   0 no extended registration for div2 :( ????
•  » » » » 7 years ago, # ^ |   0 fixed. try again.
•  » » 7 years ago, # ^ |   0 registration is still open.
•  » » 7 years ago, # ^ |   0 You still have time to register because of the delay
•  » » 7 years ago, # ^ |   0 wow, thanks God
•  » » » 7 years ago, # ^ |   0 in fact — god reply your wish ! (like i reply to your comment khkhkhkhkh)
 » 7 years ago, # | ← Rev. 2 →   0 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!
 » 7 years ago, # |   0 The contest is not started right time.15 minutes late will be started.
 » 7 years ago, # |   0 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.
•  » » 7 years ago, # ^ |   -10 Nope, their fault i can't wait anymore
•  » » 7 years ago, # ^ |   +1 This was an old message , MikeMirzayanov forgot to change it back to "codeforces is temporary unavailable"
 » 7 years ago, # |   +5 It's too late in China. 8 hours later I have to have class...
 » 7 years ago, # |   0 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. :-)
•  » » 7 years ago, # ^ |   0 you're lucky :-)
 » 7 years ago, # |   0 The contest is not started right time.15 minutes late will be started..
 » 7 years ago, # |   +13 "We have to upgrade infrastructure...Let's do it 5 minutes before the contest!"
 » 7 years ago, # |   0 I must go to sleep because I will go to school in 5 hours later.The sadness of UTC+8.
 » 7 years ago, # |   0 tqvenii deda movtyann D amocanis 16 testis shemdgenels movutyann suyvelaperiii,2 saati tyvila gvawerinebb xalxss tqvenii suyvelaperi movtyan,mtestavidan dawyebuli mtargmnelidan damtavrebuliii,puiii
 » 7 years ago, # |   +31 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 :)
•  » » 7 years ago, # ^ |   0 We hope so!
 » 7 years ago, # |   0 It was Good contest but I wish it had more time
 » 7 years ago, # |   0 Any hints for Div2 B?
 » 7 years ago, # |   +1 Div2 C: Time Limit Exceeded in pretest 11.
 » 7 years ago, # |   0 How to solve DIV2-D/DIV1-B ?
•  » » 7 years ago, # ^ |   +6 Let's reverse a problem:Points a and b are connected only if distance between them is smaller than 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.
•  » » 7 years ago, # ^ |   0 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
•  » » 7 years ago, # ^ |   +3 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
•  » » » 7 years ago, # ^ |   0 :D This is so overkilled.
•  » » » » 7 years ago, # ^ |   +5 That's how I made it too, and it took me about 10 minutes :))
•  » » » » » 7 years ago, # ^ |   +9 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 wiAnd answer is the maximum subset of circles that doesn't intersect with each other =)
•  » » » 7 years ago, # ^ |   0 QAQ , Consider 3 points i, j, k (i > j > k). maybe it is x[i]>x[j]>x[k] ???
•  » » » » 7 years ago, # ^ |   0 Sort the point be the coordinates. Then it's the same :D
•  » » » 7 years ago, # ^ |   0 Its a lot more intuitive than converting the problem to counting non-intersecting circles, according to me.
 » 7 years ago, # |   0 Is the contest unrated for div2 participants??Really hope not!
•  » » 7 years ago, # ^ |   0 Contest is rated for Div2 participants.Contest is unrated only for those Div1 participants who write me a private message shortly.
•  » » 7 years ago, # ^ |   0 Why would it be unrated?
•  » » » 7 years ago, # ^ |   0 You can get the answer at UPD3 :)
 » 7 years ago, # |   0 Huh, 67 people did problem with FFT :o, nice.
•  » » 7 years ago, # ^ | ← Rev. 2 →   +5 I solved it with brute force. Ran max test in 1.6s in Custom test.UPD: It passed sys test.
•  » » » 7 years ago, # ^ |   0 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.
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   +5 It's not very naive. I did it with bitmasks, so runtime is T(N2 / 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 - Design Tutorial: Increase the Constraints. They feel very similar to me, with solution being FFT (which I don't really know), and looks possible to solve with bitmask stuff.
•  » » » » » 7 years ago, # ^ |   0 What is the meaning of T(), I have seen it a few times ago?
•  » » » » » » 7 years ago, # ^ |   +9 T is number of step, meaning it doesn't ignore constant factors.
•  » » » » » » » 7 years ago, # ^ |   0 Huh, funny, I didn't know this. Is it formally defined or is that auxiliary notation introduced for competitive programming purposes?
•  » » » » » » » » 7 years ago, # ^ |   0 I think I have seen them in OCW videos, though not sure :P
•  » » » » » » » » 7 years ago, # ^ |   0 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.
•  » » » » » » » » » 7 years ago, # ^ |   +16 I think that this is something different. T(n) as you described now can be equal to O(n2), it is not consistent in any way with the meaning of T(n2 / 32) you used before.
•  » » » » » » » » » 7 years ago, # ^ | ← Rev. 3 →   0 Disclaimer: I'm always confused by these things, so I may be speaking non-sense.Since O(N) is upper bound function, we can have f(N) = N = O(N) = O(N2). And in here T(N) means true value of runtime (?) So what is wrong with T(N) being equal to O(N2) ? For me, this only means that, in most cases, we should use Θ or T instead of O.
•  » » » » » » » » » 7 years ago, # ^ | ← Rev. 2 →   +8 What I'm saying is that you wrote T(n2 / 32) while you should have written sth like T(n) = n2 / 32, because n is T(n) means size of the problem and n2 / 32 ain't one.By the way I think that Θ would be more appropriate here, because for me T is used rather to write down some equations for complexities like T(n) ≤ Θ(n) + T(3n / 4) + T(n / 5) like in algorithm of finding median. T could be used as O(sth) as well, doesn't have to give strict bound.
•  » » » » » » » » » 7 years ago, # ^ |   0 Ok, I see the problem now. Thanks! :)
•  » » » » » » » 7 years ago, # ^ |   0 Thank you, and Swistakk too! :)
•  » » » » » » 7 years ago, # ^ |   0 I guess the most common notation of complexities areO for upper bound, Ω for lower bound, and Θ for strict bound
•  » » » 7 years ago, # ^ |   0 If 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.
•  » » 7 years ago, # ^ | ← Rev. 2 →   +5 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.
•  » » » 7 years ago, # ^ |   -10 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
 » 7 years ago, # |   -18 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...
•  » » 7 years ago, # ^ |   +13 What is your solution? I wrote Euler path and for my solution it doesn't matter if graph has self-loops.
•  » » » 7 years ago, # ^ |   0 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?
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   +8 Firstly, link all vertices which have odd degree. Now graph has Euler cycle. Suppose it's c1, c2, ..., cm. Then we output edges . But there is a problem when graph has odd number of edges. In that case we need to add edge .
•  » » » » » 7 years ago, # ^ |   0 Thanks :) I understood and the idea is preety cool
•  » » » » » 7 years ago, # ^ |   0 Actually, there's a bit more. Consider a test 6 4 1 2 2 3 4 5 5 6 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.
•  » » » » » » 7 years ago, # ^ |   +5 But there is only one component in the graph.
•  » » » » » » » 7 years ago, # ^ |   0 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.
•  » » » » » » » » 7 years ago, # ^ |   0 They probably meant that your orientation of the edges should not guarantee strong connectivity or something like that.
•  » » » » » » 7 years ago, # ^ |   +13 The graph is connected. The cables are put so that each computer is connected with each one perhaps through some other computers.
•  » » » » » 7 years ago, # ^ |   +31 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.
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 7 years ago, # ^ |   0 Hi, may you elaborate it a little bit?, please
 » 7 years ago, # |   0 was difficult. can't solve Div2-C, what is needed there? map?
•  » » 7 years ago, # ^ |   0 I answered queries in reversed order with disjoint set union, but I think that there is simpler solution.
•  » » » 7 years ago, # ^ |   0 it can be solved in O(W+H+N)
•  » » 7 years ago, # ^ |   0 I used multiset for distances between cuts and set for coords of cuts
•  » » 7 years ago, # ^ |   0 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?
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 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
•  » » » » 7 years ago, # ^ |   +1 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.
•  » » » » » 7 years ago, # ^ |   +2 lower_bound() is too slow for set operation because set<>::iterator ain't random access iteratoryou can first insert pos into the set, then go up and down a bit.10332363
•  » » » » » 7 years ago, # ^ |   +32 You can also change lower_bound(XXX.begin(),XXX.end(),pos) to XXX.lower_bound(pos). It will get AC.
•  » » » » » 7 years ago, # ^ |   0 Oh so my lower bound was doing a linear scan. Thanks, guys. I got it accepted by changing that :)
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 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?
•  » » 7 years ago, # ^ |   0 thanks 4your ideas.
 » 7 years ago, # |   0 First time of playing hacks, so interesting.
 » 7 years ago, # |   0 Btw you can check your div. 1 A,B,C solutions in upsolving of div. 2 contest.
•  » » 7 years ago, # ^ |   0 It's also tested almost instantly there, looks like all submissions are already tested and results are cached.
 » 7 years ago, # |   0 i know its silly -> a little hint about A-Div2 ?!? so, this is math , no programming -_-
•  » » 7 years ago, # ^ |   0 here is pseudo-code for Div2 Awhile(a>0 && b>0) { if(a>b) { res+=a/b; a%=b; } else { res+=b/a; b%=a; } }
 » 7 years ago, # |   0 It was nice. Thank you.
 » 7 years ago, # | ← Rev. 2 →   0 Div2-B — TLE54Div2-C — ACIt is sad when you can't solve easy tasks:D
•  » » 7 years ago, # ^ |   0 I also got TLE on same case.Any idea whats the test case...its pretty long to be seen...
 » 7 years ago, # |   0 I can't understand this test in Div2B: 2 xy zzWhy is the answer: 1 1 2 ?We transform strings as xy->yx and have: yx zzAnd the Hamming distance IS THE SAME!!!
•  » » 7 years ago, # ^ |   0 Test #112 xy zzOutput is 2 -1 -1
•  » » » 7 years ago, # ^ |   0 Sry(
 » 7 years ago, # |   0 My solution 10326396 is giving correct output for the pretest 9 on my machine but I don't know why output shown in result is wrong on website. Please check it.
 » 7 years ago, # |   -6 My solution 10326396 is giving correct output for the pretest 9 on my machine but I don't know why output shown in result is wrong on website.
 » 7 years ago, # |   -6 My solution 10326396 is giving correct output for the pretest 9 on my machine but I don't know why output shown in result is wrong on website.[contest:http://codeforces.com/contest/527#] My Solution: http://codeforces.com/contest/527/submission/10326396
•  » » 7 years ago, # ^ |   0 I was wrong. There is error in my program. I am sorry.
 » 7 years ago, # |   0 Hi
 » 7 years ago, # |   0 Check out my crazy div. 1 B solution, lol 10326839
 » 7 years ago, # |   0 Was this contest unrated for Div 2 ??
 » 7 years ago, # |   0 I am sorry,I was not trying to spam. I did it by mistake.
 » 7 years ago, # | ← Rev. 3 →   0 How to solve Div1 B?Update: I missed this comment where tom describes his idea.
•  » » 7 years ago, # ^ | ← Rev. 3 →   +1 Suppose we're comparing two points and x1 ≤ x2, then x2 - x1 ≤ w1 + w2, which can be transformed to x2 - w2 ≤ x1 + w1. So, build a pair array with the values {x - w, x + w} for all points. Sort that array. Let 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 index i, we do a binary search to find the first element j such that xj - wj ≥ xi + wi, and set DP[i] = max(DP[j] + 1, DP[i + 1]). The answer will be DP[1]. Sadly, it took me an hour and a half to figure what to do with the values x + w and x - w (the last step)...
•  » » » 7 years ago, # ^ | ← Rev. 3 →   0 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... :)
 » 7 years ago, # |   0 will you post the editorial ?? the problems were really hard for me :3
 » 7 years ago, # | ← Rev. 2 →   +1 In problem 527B - Error Correct System, what would be the correct output for the case: 4 dbea bddb 10318065 this Accepted submission gives: 3 1 3 Is it ok? Zlobober
•  » » 7 years ago, # ^ |   0
•  » » » 7 years ago, # ^ |   +1 We will add investigate this test and probably add it, thanks.
•  » » 7 years ago, # ^ |   +5 I also thought on this problem, too.Didn't realize why 10315968 got accept until reading this thread. My test case is: 4 acbc bbaa I thought the correct output should be: 2 1 3 But the below output also passed: 3 2 3 The problem says it must be "as small as possible" not just "reducing some".
•  » » » 7 years ago, # ^ |   0 Will system testing run again with more comprehensive test cases?
•  » » » » 7 years ago, # ^ |   0 Never, for sure! past is past! Codeforces always thinks about future! :D
 » 7 years ago, # | ← Rev. 2 →   +8 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.
•  » » 7 years ago, # ^ |   +38 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.
•  » » » 7 years ago, # ^ |   0 You are right. Russian statement was very clear.
•  » » 7 years ago, # ^ |   +25 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
•  » » 7 years ago, # ^ |   0 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.
•  » » 7 years ago, # ^ |   0 I agree with 1st point. I misunderstood problem statement of C and tried to solve a different problem, until I saw the announcement :(.
•  » » 7 years ago, # ^ |   +5 Like! But I really don't wanna this contest to be unrated. I believe many contestants having the same idea with me.
 » 7 years ago, # |   +24 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
•  » » 7 years ago, # ^ |   0 Hah, yes, that one was pretty confusing, I needed to read this many times too :P.
 » 7 years ago, # |   0 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.
•  » » 7 years ago, # ^ |   0 I think that the unrated option is only in case the test for Div1 D affected you and the code for Div1 D cannot be submitted in Div2.
•  » » » 7 years ago, # ^ |   0 If my ab are wrong and I have submitted d using fft, then I will certainly try to be unrated
 » 7 years ago, # |   +40 Finally I know my program of finding Euler's circuit used several times is O(nm). What a sad story.
 » 7 years ago, # |   0 Zlobober why my rate still the same .. is it unrated contest
•  » » 7 years ago, # ^ |   0 Give me a treat, your rating is increased! Your rating change
 » 7 years ago, # |   +14 What a fantastic round for Poland! Never seen such performence earlier! :)
 » 7 years ago, # |   0 Thanks Dear happyBirthDayBeni ... ^_^ I was really surprised ... I love U ... :D/
 » 7 years ago, # |   0 Thanks Dear happyBirthDayBeni ... ^_^ I was really surprised ... I love U ... \:D/
 » 7 years ago, # |   0 Thanks Dear happyBirthDayBeni ... ^_^ I was really surprised ... I love U ... \:D/
 » 7 years ago, # | ← Rev. 2 →   +7 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.
 » 7 years ago, # |   +33 I was afraid to become orange when I finished debugging C 30 seconds after the contest has finished.
•  » » 7 years ago, # ^ |   +8 Indeed a close call :D
 » 7 years ago, # |   0 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
 » 7 years ago, # |   +5 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......
 » 7 years ago, # |   +30 I still can't understand what's the meaning of div1C...
 » 7 years ago, # | ← Rev. 3 →   0 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 1000so my output matches the system output yet i was given verdict of wrong answer...
•  » » 7 years ago, # ^ | ← Rev. 2 →   +3 I believe it means the 524 doesn't match with 1 2Although you give the correct answer, but the index of i and j are 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)
•  » » » 7 years ago, # ^ |   0 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.
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   +5 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
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 yeah i see now.. thanksthe error did not show up in all those 18 pretests lol
•  » » » » » » 7 years ago, # ^ |   0 You can look at my submission 10333076
•  » » » » » » » 7 years ago, # ^ |   0 thanks again
 » 7 years ago, # |   +17 Editorial?
•  » » 7 years ago, # ^ |   0
 » 7 years ago, # |   0 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..
 » 7 years ago, # |   0 some1 needs to do something about these fake winners,i mean unrated
•  » » 7 years ago, # ^ |   0 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?
 » 7 years ago, # |   0 Now that I read one solution to Div.2 C , it seems so easy. Why didn't it click earlier? :(
•  » » 7 years ago, # ^ |   -18 Because your account is fake!!
 » 7 years ago, # |   +27 When will the tutorials be available for div2 problems?Especially for C,D,E problems.
 » 7 years ago, # |   0 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.
•  » » 7 years ago, # ^ |   0
•  » » » 7 years ago, # ^ |   0 Oh, thanks. Silly me didnt notice those posts above.
 » 7 years ago, # |   0 can't see the editorial :( who can help me explaining the DIV2-B case 1&2 ,why both of the output is 1.
•  » » 7 years ago, # ^ |   +1 You can see Here
 » 7 years ago, # |   0 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?
•  » » 7 years ago, # ^ |   0 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.
 » 7 years ago, # |   0 where are the editorials
•  » » 7 years ago, # ^ |   0