### halin.george's blog

By halin.george, history, 6 years ago, translation,

Hi everyone!

Codeforces Round #381 will take place tomorrow on the 23rd of November at 19:35 MSK.

The problems were prepared by Alexander Alexandr_TS Tsaplin, Maxim HellKitsune Finutin and me. I hope you will enjoy it.

I'd like to thank Gleb GlebsHP Evstropov, Nikolay KAN Kalinin and Yevhen MrDindows Zadorozhnii for helping me in preparing problems, Mike MikeMirzayanov Mirzayanov for the great Codeforces and Polygon platforms.

There will be five problems and two hours for solving them. The scoring distribution will be announced later.

UPD

Scoring for both divisions: 500-1000-1500-2000-2500

UPD

Congratulations for winners.

Div 1:

Div 2:

A special congratulations to Petr for being the only contestant to solve the problem D in div. 1.

UPD

The editoral in english will be published tomorrow, but you can read it now in russian

UPD

The editoral was added for the first five problems.

UPD

The editoral was added for the Div.1 D and Div1. E.

• +234

 » 6 years ago, # | ← Rev. 3 →   -166 Dont know why got downvote but hope it will be rated and fast judging
•  » » 6 years ago, # ^ |   -100
•  » » » 6 years ago, # ^ |   -71 That's because I'm not Mike?:) (downvotes)
•  » » » 6 years ago, # ^ |   -62 It is not for that "you are not mike" It is for this Click and see everyone ! :| -_- :P :P
•  » » » » 6 years ago, # ^ |   -61 Can you pls tell me whats wrong with this revision?
•  » » » » » 6 years ago, # ^ |   -19 because you are not mike :P
•  » » » » » 6 years ago, # ^ |   0 What did you revise anyway?
•  » » » » » 6 years ago, # ^ |   0 Say good luck to yourself.
•  » » » 6 years ago, # ^ |   +3 Oh yeah it's rated! :( Really, guys, stop it.
•  » » » » 6 years ago, # ^ |   0 (It's a meme)
 » 6 years ago, # | ← Rev. 3 →   -59 Obligatory comment: Is it rated???
•  » » 6 years ago, # ^ |   -42 yes.
•  » » » 6 years ago, # ^ |   -60 Is it rated ?
•  » » » » 6 years ago, # ^ |   0 Stop the "Is it rated?" Got that?
 » 6 years ago, # |   +39 Finally usual five problems two hour contest in a usual start time :D
•  » » 6 years ago, # ^ |   +108 This time is no longer considered usual :D
•  » » 6 years ago, # ^ |   +33 Congrats! you didn't get downvotes
•  » » » 6 years ago, # ^ |   +5 I have a lot of friends :D
 » 6 years ago, # |   -77 Is it rated?
•  » » 6 years ago, # ^ |   0 Yes
•  » » 6 years ago, # ^ |   +90 After thousands of "joky" comments about "is it rated?" I think we all need motto "Yes, it is f*cking rated".
•  » » » 6 years ago, # ^ |   -11 yeah, I don't think anybody should comment about: 'Is it rated?' I'm pretty sure most people do it to get a high contribution. It's not so fun anymore.
 » 6 years ago, # |   +34 Your graph is really inspirational halin.george :)
 » 6 years ago, # |   -87 Will you put Greedy problem?
•  » » 6 years ago, # ^ |   -56
 » 6 years ago, # |   -13 I think Six or Seven problems in Two and Half hours is more interesting. Because there at least four solvable problems to an Expert.
•  » » 6 years ago, # ^ |   -17 there is only half an hour between the time for the contest with 5 problems and the time for the contest with 7 problems and this is not enough to solve the extra 2 tasks
 » 6 years ago, # |   +27 I hope I can become red after this round. (Maybe a little bit difficult)
•  » » 6 years ago, # ^ |   +12 and maybe MiracleFaFa :)
•  » » » 6 years ago, # ^ |   0 Haha... Interesting ^_^
 » 6 years ago, # |   -65 is it rated...! where is this guy there is one each time?
•  » » 6 years ago, # ^ |   -20 Did you read like the first 5 comments?Also, what is the deal with you guys anyway? You see 3 "is it rated" questions being downvoted to oblivion, do you think the 4th time is the charm or something? What the fuck is wrong with you?
•  » » » 6 years ago, # ^ |   +38 Please don't swear on Codeforces. Someone said their ISP blocks websites with these phrases so they wouldn't be able to access the site if their ISP blocks Codeforces. Please continue making the world a greater place ;)
•  » » 6 years ago, # ^ |   -16 Yes!!!!! Yes, it is obviously rated aboodxxx8!
 » 6 years ago, # |   +12 Wish interesting problems and more ratings :)
•  » » 6 years ago, # ^ |   0 Seems too difficult for me
 » 6 years ago, # |   +1 finally no "usual" word in the statement
•  » » 6 years ago, # ^ | ← Rev. 2 →   +16 Which means it is an unusual statement.
 » 6 years ago, # |   +15 Score Distribution? Its 16 minutes to start
•  » » 6 years ago, # ^ |   +3 Your wish has been granted
 » 6 years ago, # |   +34 I'm freezing now , it's just a little bit hard to code with a blanket on your whole body maybe some hard problems can make me warmer
 » 6 years ago, # |   -6 I think it's going to be a hacking contest. specially problem A div 2.
•  » » 6 years ago, # ^ |   +23 Yeah, It will be. This is the first time I've seen my live rank bouncing up and down so frequently.Also once you lock in and check others programs, you can easily identify a mistake if you made one and then start hacking others who did the same as you.Here's an example of it happening to someone in my room:
•  » » » 6 years ago, # ^ |   +31 That was a nice revenge bro!
•  » » » » 6 years ago, # ^ |   0 Agreed, a person hacks your code, but then you attack that person! Awesome!
 » 6 years ago, # |   -10 The great "System testing" is waiting for you, guys. problem A DIV 2. the work that hackers could not do will be done by GREAT "System testing" in time
 » 6 years ago, # | ← Rev. 4 →   0 really bad Problems statement
 » 6 years ago, # |   +2 Hackable contest
 » 6 years ago, # | ← Rev. 2 →   +4 I wonder why so many people don't write bruteforce instead of dealing with lot of cases in div2A. Also, will mo's algo pass in problem D(O(N * sqrt(n) * log(n)))?
•  » » 6 years ago, # ^ |   +9 we love complicated Solutions
•  » » 6 years ago, # ^ |   0 My solution was O (NlogN) in the problem D Div 2, or can say O (N) with lower_bound
 » 6 years ago, # |   +15 it's a great feeling when you find your problem in a Codeforces round link you own me ECPC participants
•  » » 6 years ago, # ^ |   0 thank you <3
•  » » 6 years ago, # ^ |   0 Also Div2C/Div1A is similar with F from some russian contest.
 » 6 years ago, # |   +3 Finally, I suffer from the problem that std::set has no way to count the number of elements < k ...
 » 6 years ago, # |   +6 Hacks for Div2A7 50 2 100ans=507 50 100 1ans=37 100 1 1ans =2Fingers crossed. Finally Blue. Maybe. :)
•  » » 6 years ago, # ^ |   0 Dang I wish someone in my room hacked me.
•  » » 6 years ago, # ^ |   +4 You are now blue! Yaaay
 » 6 years ago, # |   +33 Problem div1 B looks very similar to Problem J in the last ACM-ICPC Egyptian national contest.
•  » » 6 years ago, # ^ |   +1 Actually it is that problem, I have just ctrl+c ctrl+v the code.
•  » » » 6 years ago, # ^ |   0 i did the same but the log^2 idea that passed in the ECPC didn't pass now :D karma...
•  » » » » 6 years ago, # ^ |   0 i have log^2 pretests passed .....
•  » » » » » 6 years ago, # ^ |   0 o.o
•  » » » » » » 6 years ago, # ^ |   0 maybe you copied the slower log^2 :3
•  » » » » » » » 6 years ago, # ^ |   0 actually i didn't know that return make_pair() returns in O(n) also copying is in O(N) and SOMEHOW this code got ac in the national problem , great testing O_O
•  » » » » » » » » 6 years ago, # ^ |   0 What does this mean? Anything related to make_pair ?
•  » » » » » » » » » 6 years ago, # ^ |   0 if u returned a vector with make pair it'll call the copy constructor
•  » » » 6 years ago, # ^ |   +1 i got solutions skipped because i ctrl_c and ctrl+v the code i want that status removed right now... not my fault they decided to ripoff the problem
•  » » » » 6 years ago, # ^ |   0 :V
•  » » 6 years ago, # ^ |   0 Also similar is http://usaco.org/index.php?page=viewproblem2&cpid=576
•  » » » 6 years ago, # ^ |   0 That's an LCA problem, and is completely different from div2D...
•  » » » » 6 years ago, # ^ |   0 What I mean, is that techniques are very similar. Binary jumping and the prefix sums are both used in this problem, the only thing not included is the rewriting of the condition, but even that is a common theme in these tree query problems. This D was pretty much a subset of the usaco problem.
•  » » » » » 6 years ago, # ^ |   0 Oh whoops my solution to D was pretty different but I guess you're right ;)
 » 6 years ago, # |   +3 Please, someone who passed C but had WA #4 before that, tell me what you have changed :)
•  » » 6 years ago, # ^ |   +9 Stupidly forgot to use long long instead of int in one of the variables... cost me 50pts.
•  » » » 6 years ago, # ^ |   0 Shit, my lazy array should be long long! Thank you! :)
 » 6 years ago, # | ← Rev. 2 →   +1 Harder version of Div.2 D/Div.1 Bdist(v, u) ≤ Au => dist(v, u) ≤ Av
•  » » 6 years ago, # ^ |   +61 I misunderstand problem and solve the harder version in contest :(
•  » » » 6 years ago, # ^ |   +6 Me too. :|By the way how did you solved the harder version? ( Merging Treaps? )
•  » » » » 6 years ago, # ^ |   0 I did it too -______-I used segment tree with value compression...
•  » » » » 6 years ago, # ^ |   0 Just realize I read the problem wrong after implementing it. :'(
•  » » » » 6 years ago, # ^ |   +15 O(n log n) with BIT.Let di be the distance from i to root. Precalculate all value of ci = di + ai and sort these values. Then visit tree with dfs order. When we visit a vertex x, we can know it will contribute answer to which vertices by by binary search on sorted array c.Please see my code for the detail: http://codepad.org/Q2NDUqDi
•  » » » » 6 years ago, # ^ |   0 Simply by doing the dfs order, the problem reduces to finding the number of values <= x in a range, which has a nice known solution using BIT in increasing order of values.
•  » » » » » 6 years ago, # ^ |   0 How do you find the number of values <=x in a range using BIT? Can you please explain?
•  » » » » » » 6 years ago, # ^ |   0 Sort the array values and queries values, together, then if an array value comes (v,0,index) update(BIT, index, +1). Else, for (v,1,index) query [l,r] answer = read(BIT, r) — read(BIT, l-1). This is a well known solution to this problem.
•  » » 6 years ago, # ^ |   +13 when I first saw the problem, I think it is the difficult version, and it takes me 20 minutes to realise
 » 6 years ago, # |   +2 Can somebody explain C to me? I assume that mex is always length of the smallest subset + 1, but I have no idea how to make the array. Can someone explain? Also, hacks on A saved me, would've had a terrible result otherwise :D
•  » » 6 years ago, # ^ |   +1 Div2. Of course
•  » » 6 years ago, # ^ |   +14 Denote M = mexMake array like this : 0 1 2 ... M — 1 0 1 2 ... M — 1 and so on. Any consecutive subarray of this array contains all numbers from 0 to M — 1
•  » » » 6 years ago, # ^ |   +1 Ah, damn now I feel stupid. Thank you!
•  » » 6 years ago, # ^ |   +6 Let l be the smallest length of the subarrays. Then a[i]=i%l. It's pretty easy to prove
•  » » » 6 years ago, # ^ |   -6 So cool solution!! my god
 » 6 years ago, # |   +1 I can feel the power of Alyona's mother
 » 6 years ago, # | ← Rev. 2 →   0 -
 » 6 years ago, # |   +7 I think it would be better if in div2 B : n, m <= 1000*1000by the way thanks for contest.
•  » » 6 years ago, # ^ |   +5 True , O(n^2) shouldn't be allowed.
 » 6 years ago, # |   +26 Div1 B is exactly the same with ECPC 16 J.
•  » » 6 years ago, # ^ | ← Rev. 3 →   +18 B — rewrite the condition and apply well-known tehniqueC — apply Maximum subarray problem for segments but with another combine function.
•  » » » 6 years ago, # ^ |   +4 How to solve DIV1B? What's the well-known technique (Atleast I am unaware of it).
•  » » » » 6 years ago, # ^ |   0 Yeah these comments are driving me crazy because half the discussion is about Div1b/Div2d but noone explaining how it works :)
•  » » » » » 6 years ago, # ^ | ← Rev. 3 →   +3 For a given node i, let's find what's the closest node to the root that still controls node i. In other words, we need to find the closest node j such that i is in j's subtree and dist(j, i) <= A_i. This sounds like a job for binary search. I implemented the process of finding j using skip-lists. The lowest node that controls i, is i's parent. The farthest node from i that still controls i, is j. So every node that lies on the path between j and i's parent control i, or in other words parent[i], parent[parent[i]], ...., j. This can be calculated using the same technique as in partial sums' updates. If for a node x, parent[i] is in its subtree res[x] += 1. If parent[j] (first node that doesn't control i) is in its subtree as well, then res[x] -= 1.
 » 6 years ago, # |   +145 Petr using C++, what has the world come to???
•  » » 6 years ago, # ^ |   +226 Free CLion evaluation ends in 5 days, will switch back to Java soon :)
•  » » » 6 years ago, # ^ |   +135 Petr, I'm happy you've solved D. It was my idea of the problem.Codeforces has hosted Kotlin Unknown Language Round and got few licences for free. I'll be glad to make you a gift: one year 100% discount for any JetBrains product. Each time in a year if I'll see your "Accepted" on C++ I'll be glad to think that there is small part of our contribution there :)
•  » » » » 6 years ago, # ^ |   +51 Well, I think they pay enough in Google so that issue is not in having the license :)
•  » » » » » 6 years ago, # ^ |   +12 We are going to end up with battle between Egor and riadwaw for users with their respective products CHelper and JHelper :)
 » 6 years ago, # |   0 some hints for problem C?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Check this comment .
•  » » 6 years ago, # ^ | ← Rev. 2 →   +6 find minimum length interval len = (r - l + 1) obviously answer can not be more than that. So just print 0, 1, ...len - 2, len - 1, 0, 1... you can see that for every interval mex will be equal to len
•  » » » 6 years ago, # ^ |   0 It was not "obviously".
•  » » » » 6 years ago, # ^ |   0 Maybe you are right, but at least it's something which does not require too many steps in thought process. Either you see it or you don't, it's not like you have to think of A then B and then come up with conclusion as in many harder problems.
•  » » » 6 years ago, # ^ |   0 Shit !! I used binary search on mex! :P Shame on me... But got AC... This Shouldn't be allowed ! :)
 » 6 years ago, # |   0 Div:2-C WA on pretest-test 4. any hint ?
 » 6 years ago, # |   0 OMG!!! I had two bad performance in two contests, I think i should take a break for a while :(
•  » » 6 years ago, # ^ |   +3 Or the other way around — train more intensively before the next contest, which will be in this sunday :)
•  » » » 6 years ago, # ^ |   0 Too much pressure is not good...
 » 6 years ago, # | ← Rev. 2 →   +3 Maybe codeforces's computers are too fast! Div1. E:22443543 This submission just uses an O(n^3) and passes !
•  » » 6 years ago, # ^ |   +17 Lesson learnt: brute force even the obvious solution looks a bit too slow :(
 » 6 years ago, # |   0 is similar to today's div. 2 D. I got AC in Gym, but the same code didn't pass today's system test. :'(
•  » » 6 years ago, # ^ |   0 shame on me I've prepared it's tests very well can your please give me your code ?
•  » » » 6 years ago, # ^ |   +3 hello i did this problem J one time and i just did the same process as that time i solved J since i already solved the problem, i used my own code as a guidline (since is gym obviously i am basically guiding myself) and send it , now i got skipped obviously because you guys are flagging me as cheating, remove it. If you are going to ripoff a problem without any twist don't expect us to do something different if we already solved it before. Thanks.
 » 6 years ago, # |   0 When system testing will start ?
 » 6 years ago, # |   +5 it's nearly not fair that the people who solved the ECPC problem j only paste their code in problem D div2 and got accepted
 » 6 years ago, # |   0 By-by blue.... :(
 » 6 years ago, # |   0 so hacking :)
 » 6 years ago, # | ← Rev. 2 →   +31 Omg, D is so tedious. If I'm not mistaken it can be simply solved by linear greedy, but that requires big amount of ifs and a lot of stupid boring code.EDIT: Okay, I was wrong. So easy to get head messed up at this one.
•  » » 6 years ago, # ^ | ← Rev. 3 →   +27 Hmm, I had similar thoughts initially, then I realized I was wrong. The solution I came up with uses maximum matching.EDIT: After getting it accepted, I can safely say that even though it isn't greedy, the solution still requires a shit-ton of special cases :D Or maybe I just lost my touch...
 » 6 years ago, # |   +12
 » 6 years ago, # |   +5 How to solve problem E (Div2) ?
•  » » 6 years ago, # ^ |   +3 Probably seg tree + lazy propagationFor each interval, keep the left hill, the right hill and the answer. When you merge 2 intervals, the answer will be:max(new left hill elements, new right hill elements, hill in the middle (you merge the right hill of the left and the left hill of the right), max answer of the smaller intervals)merging the hills needs a bit of time to code but it's not hard to think about the answer. You will need to save the left number, the right number, whether it has reached a peak, whether it is decreasing/increasing, etc.
 » 6 years ago, # |   +1 can Anyone describe the solution of problem D in Division 2? i got nothing other than O(n^2) solutions.
•  » » 6 years ago, # ^ |   +9 I can tell you how I solved it.Build sparse table on a tree. You have every 2^kth parent and for every 2^k parent sum of all edges on path.Now, for every vertex we want to find the farthest parent such that our node is controlled by this parent. Notice that sum along path can only increase, so it's binary searchable. In this part we use 2^k parent, which we have from sparse table. Let's call that farthest node V.All nodes on path [V -> our node] controlls our node. Then we use little trick: add 1 to parent of our node and -1 to parent of V. Now with standard DFS we can finally make answer.Of course, I've omitted implementation details.
•  » » » 6 years ago, # ^ |   0 I was working on this problem but got stuck on how to add +1 to those nodes that control the current node, how does the "little trick" work it's not clear at all? Thank you.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 We have an array where we want to sum v on intervals l<=i<=r.Let's first process the intervals and then get the array. The array "a" first starts with all 0's and there will be an auxiliar array "aux". When we want to update the range, we make aux[l]+=v and aux[r+1]-=v.But why? If we consider the cumulative sum of all elements of aux until i, we will get exactly the value that we added on i. So to get the answer we do aux[i]+=aux[i-1] and a[i]+=aux[i]. Why does this work? Because on the range l<=i<=r, you will have v on the sum and from r+1 onwards, you will have excluded that v, as needed.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Can you help in figuring out the mistake ? (the test case is big) . My approach is exactly same as yours. http://codeforces.com/contest/740/submission/22459911
 » 6 years ago, # |   0 I had a greedy solution for Div1 C but it was splitting into a large number of cases. How to improve the solution?
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 Segment tree. Updates don't really affect the individual answer of that very range, but do so for the rest of the ranges. Keep information like answer, maximum value, minimum value and whether the range is strictly increasing, strictly decreasing or a hill. Then combine can be done easily, but implementation is still a pain.
•  » » 6 years ago, # ^ |   -17 For problem c:find the minimum gap among all the l and r ranges...val=min(val,r-l+1) run this for all m subarrays and now just start off with a variable x=0 and print it modulo val and then increment x after each iteration
•  » » » 6 years ago, # ^ |   0 div1 C :)
 » 6 years ago, # |   +17 super fast system testing
 » 6 years ago, # |   -13 Hack-round
 » 6 years ago, # |   0 Hello, why in the world my submissions are "skipped"? , it is not my fault that you decided to ripoff a problem from the Egyptian ACM contest, my solution is exactly that , you can't argue i cheated in the contest. If i solved the problem the same way i did in that contest is not cheating, so please remove the "skipped" flag on my submissions... thanks.
 » 6 years ago, # |   -58 My name disappeared from the final standings and I found my submissions transformed to skipped on my profile. MikeMirzayanov why did this happened?
•  » » 6 years ago, # ^ |   +150 I see cheatCount=9 in database in your profile. So I simply even do not want to answer. Same solutions: 680A: Joe_Pacha/18303346, just_fuck_you/18303475 Same solutions: 682B: Joe_Pacha/18550753, _underr/18552489 Same solutions: 697A: Joe_Pacha/19113420, _underr/19114661 Same solutions: 699B: Joe_Pacha/19238676, zackblick1234/19239332 Same solutions: 699A: Joe_Pacha/19235514, zackblick1234/19235986 Same solutions: 706C: Joe_Pacha/19799607, BaiBatyr/19802891 Same solutions: 716B: Joe_Pacha/20688209, pashka921/20688382 Same solutions: 724A: Joe_Pacha/21281037, humblecool/21281540 Same solutions: 740A: pashka921/22428017, Joe_Pacha/22428028 
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +26 Hello can you check mine? you can even check on the GYM the solution my team and i did for problem J sadly the setters decided to do the same exact problem, so i just used that solution which is ours. But got flagged as "skipped" , sir i never ever cheat on this contests, i beg you to check i don't want to miss my chance to get back to blue and be treated as a shady contestant which i am not.Contest is ACM Egyptian Collegiate Programming Contest 2016
•  » » » 6 years ago, # ^ | ← Rev. 2 →   -75 I opened the profile of "_underr" and couldn't find a submission with ID "18552489". Also user "just_fuck_you" logged in 4 months ago, so how does this relate to me and to the contest? Please give me more details about why this happened. MikeMirzayanov I appreciate if you could give credit back to my solutions, as seriously the solutions you mentioned don't belong to me and I don't know anything about them. I've been competing actively for many contests and I never cheated.You can re-check my submissions, and for example, I submitted the 'A' problem very early from first time (maybe after 3 or 4 minutes from the contest) so it's not logical that I was cheating. Thank you.
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   +19 He implies you are cheating from a long time. See in this contest : http://codeforces.com/contest/740/submission/22428017 , http://codeforces.com/contest/740/submission/22428028 Can, you give me phone number of pashka921? I want to ask him if he is your father or mother? Also, your post should be downvoted to hell and oblivion. Also, don't make white lies — _underr's submission is here: http://codeforces.com/contest/682/submission/18552489
 » 6 years ago, # |   0 For Div1 A, a[i] = i % ans did not strike me. So I thought of removing the intervals which subsume at least one interval. Now, sort the intervals according to the left end. Now, you can fill in O(nlogn) by only checking for those elements which do not overlap with the just previous interval. Did somebody go down this line?
•  » » 6 years ago, # ^ |   0
•  » » » 6 years ago, # ^ |   0 Can you please explain little more in detail. I was thinking in similar lines. Thanks :)
•  » » » » 6 years ago, # ^ |   0 Triveni sir, if you remove all the intervals that subsume another interval, then it would not matter, because the smaller interval will have all the numbers from 0 to ans — 1. So, step1, remove such intervals.Step2, sort intervals by left end;Let the intervals be a1, a2.....Then you have to understand that ai.l <  = aj.l and ai.r <  = aj.r for all i < j. So, when filling ai you check for overlaps with ai - 1 and fill the part only in ai with elements only in ai - 1. In this way, you fill each position at most once, so O(n). We need O(logn) to check if an element is already in the interval or not, so O(nlogn).TLDR: we fill part of each interval that is not contained in the previous interval.
 » 6 years ago, # |   0 DIV 2, B, Failing at test case 14
 » 6 years ago, # |   0 Can someone provide a hint on how to solve Div2 D?
•  » » 6 years ago, # ^ |   +4 dist(v, u) <= a[u] <=> dist(u) — dist(v) <= a[u] <=> dist(u) — a[u] <= dist(v)
 » 6 years ago, # |   0 TooSimpIe beats Petr!
 » 6 years ago, # | ← Rev. 2 →   0 Please update the ratings with the same speed as the system testing so i get to know how much will my rating decrease :(
•  » » 6 years ago, # ^ |   +164 For you -12. You are welcome!
 » 6 years ago, # |   0 When will be editorial?Nice contest :D
 » 6 years ago, # |   +90 Ehhh, out of seven ACed solutions to E, four are obvious O(n^3). Will this ever stop? Give me my deserved TOP5 :<.
•  » » 6 years ago, # ^ |   +64 Give me my deserved TOP2 :<
 » 6 years ago, # | ← Rev. 2 →   +39 Problem C was a mess to implement. Problem D was worse, as far as I saw. Problem E seemed the cutest one, but could be squeezed with N3 complexity. I'm not blaming anyone, I just hope the next rounds will be more balanced.Here is proof: http://codeforces.com/contest/739/submission/22452983By the way, what is the solution for problem E?
•  » » 6 years ago, # ^ |   +33
•  » » 6 years ago, # ^ | ← Rev. 2 →   +8 I used min-cost flow to solve the linear program: http://codeforces.com/contest/739/submission/22454812 I feel like it should be O(n^2 * log n) if implemented efficiently (mine uses Bellman-Ford, hence probably isn't theoretically fast enough)
 » 6 years ago, # |   0 Can anyone tell me why this code for Div1 A gets WA but this code gets AC?
•  » » 6 years ago, # ^ |   0 int a[n][2]; 
•  » » » 6 years ago, # ^ |   0 O my bad! Anyway thanks.
•  » » 6 years ago, # ^ |   -8 a[n][2] — m>n