### rng_58's blog

By rng_58, history, 16 months ago, ,

AtCoder Grand Contest 018 will be held on Sunday (time). The writer is maroonrk.

Contest Announcement

The point values will be 300 — 700 — 800 — 1100 — 1600 — 1700.

Let's discuss problems after the contest.

•
• +79
•

 » 16 months ago, # |   0 Will there be a beginner contest as well ?
•  » » 16 months ago, # ^ |   0 In AGC's week there's only AGC.We will hold ABC in the next three weeks.
 » 16 months ago, # |   +33 [reminder] The contest starts in 25 minutes.
•  » » 16 months ago, # ^ |   +34 seriously guys? does this comment deserve so much downvote? I know people are probably annoyed with some other comments, but hating on him is not cool. I feel comments like this helpful as I tend to forget about contest and downvoting it would only make him afraid of commenting. (you don't have to reply to me as you will probably just get downvoted)
 » 16 months ago, # |   +10 is the queue stuck for everyone else as well?
•  » » 16 months ago, # ^ |   0 I'm stuck in queue too
•  » » 16 months ago, # ^ | ← Rev. 2 →   +5 Me too. I hope my submission for C will be counted.PS: It failed T_T
 » 16 months ago, # |   +28 How to solve problem C:Coins?
•  » » 16 months ago, # ^ |   +35 if there were 2 types instead of 3 , then the solution is just sort according to A[i] — B[i] , take the max X of them as A and the rest Y of them as B For 3 , sort According to B[i] — C[i] in descending order , now the optimal solution looks like BBABAABABABAAB|ACACACACACAACCC (a prefix consists of B and A and the suffix C and A) . Among the prefix and suffix , the problem is now for 2 coins .so this can now be done with a segtree.
•  » » 16 months ago, # ^ |   +57 Another solution. Let's choose any distribution. For each two colors, we will put in set most good move from one color to other. While there exists two colors, such that best moves are positive in sum — do this swap. Also, if there is cycle of length 3 of best moves with positive sum — so this cycle. If not — finish, we are best solution.Correctness can be proven because it is finding MinCostMaxFlow by negative cycles cancellation. But, probably time bound is not obvious. Also, more standard MinCost algorithms can be adopted, to exploit only three colors in similar way. PS. I think solution described by rajat1603 is much simple.
•  » » » 16 months ago, # ^ |   +5 Can you please elaborate more on its correctness part,I am not able to get that!
•  » » » » 16 months ago, # ^ | ← Rev. 2 →   +6 Consider the following flow problem.Each person is a vertex connected by free edge of capacity 1 to source. There are three othere vertex, corresponding to colors, which are connected by free edges to sink, of capacity X,Y,Z corresponding. Also, there is edge of capacity one and cost -A_{i,j} between person and color.MinCostMaxFlow in this network — is solution to our problem, but it's two slow, so we need to exploit the fact, that there only three colors.One of the way of solving MinCostMaxFlow is to get any MaxFlow, and then while there is negative cycle — push flow over it. This approach is just finding this cycle fast.
•  » » » 16 months ago, # ^ |   +50 I used a similar solution, but instead of cancelling negative cycles I went for normal MCMF with flow pushing. To decrease the number of cases to consider, I added C[i] to the answer and subtracted C[i] from A[i] and B[i] and ignored the third coin type from now on, so I had only two vertices corresponding to coin types.I agree the solution by rajat1603 is simpler. On the other hand, it looks like our solution can be adapted and still be fast enough for 4-5 coin types.
•  » » 16 months ago, # ^ |   +29 First, we think the problem that "there are X+Y+Z pairs(a[i], b[i]), we get X a[i]s and Y b[i]s, maximize sum".There is upper bound that is "we calc c[i] = max(a[i], b[i]), sort c[i], sum X+Y c[i]s from greater".We think "we decide offset, calc c[i] = max(a[i], b[i] + offset), sort c[i], sum X+Y c[i]s from greater — offset * (# of use b[i])", it is upper bound of Y = (# of use b[i]).If offset = -INF, we use X+Y a[i]s. If offset = INF, we use X+Y b[i]s.So, we can binary search with offset, and check (# of use a[i]) >= X.
•  » » 16 months ago, # ^ | ← Rev. 2 →   0 Can anyone help me figure out, why this approach is wrong? CodeI sorted elements with A[i] - B[i], then in the sorted order the first X elements cannot be part of A in final solution and also last Y elements cannot be part of B in final solution.I use similar idea for A[i] - C[i] and B[i] - C[i]. then I remove all those for whom there is single possibility left. and repeat the entire procedure till I remove all of them.I am not sure about the exact complexity of the program but it seems to be getting finished in time for all cases.
 » 16 months ago, # | ← Rev. 2 →   +18 I'm surprised at 400+ AC in problem B. Is it really that easy?
•  » » 16 months ago, # ^ |   +31 Start with all the events and get the most popular one. Now remove that maximum and repeat until no events are left.
•  » » » 16 months ago, # ^ |   +5 Can you give me an example? I don't really understand what you mean by 'popular'.
•  » » » » 16 months ago, # ^ |   +6 I meant the event with the most participants. In sample input 1, 3 people are initially participating in event 2, so we remove that event first.
•  » » 16 months ago, # ^ |   +1 You can use binary search on answer as well.It is easy to write check function for it
•  » » » 16 months ago, # ^ |   0 How to write the check function?
•  » » » » 16 months ago, # ^ |   +5 On every step, remove that sports which appears more than mid and ban that sportCODE
 » 16 months ago, # |   +128 Die, ScarletFirebolt.The trouble happened because of this hacker. We are sorry for inconvenience.
•  » » 16 months ago, # ^ |   +39 What did he do ?
•  » » » 16 months ago, # ^ |   +51 Submit one-line infinite loop every second. We'll add some submission limit next time...
•  » » 16 months ago, # ^ |   0 When will be the queued submissions judged?
 » 16 months ago, # |   +194 After solving A, D, E, F and calculating the score carefully, I submmited.
•  » » 16 months ago, # ^ |   0 I felt today's problems are very easy to get wrong for whatever reason.
•  » » 16 months ago, # ^ |   +12 Jealous xD?
•  » » » 16 months ago, # ^ |   +70 And what is purpose of submitting on last minute? Not participate if you are not good enough today?Don't you think it's a bit against spirit of competition (totally ok by rules obviously).
•  » » » » 16 months ago, # ^ |   +23 tourist style
•  » » » » 16 months ago, # ^ | ← Rev. 2 →   +46 When tourist does this he is praised by Petr for his creativity, but when Swistakk does this he is accused of being against spirit of competition, I guess that's called "double standards" :D.On a more serious note, yes, you're right, I agree this is kinda against spirit of competition. However I am not sure whether somebody participates after he clicks "Join AGC XY" or after he makes his first submit and I couldn't find answer in any kind of rules etc, can somebody answer this? In first case, it is completely fine and brings almost no profit, so for the sake of this reply I will assume that second case holds. I think something should be done in system to prevent this kind of thing. Maybe treat user as participant if he opened at least one problem? And moreover, such strategy is connected to some unavoidable risk. If you fail at least two problems you can end up having no time to debug any of them while when following typical strategy you will have more time to debug them and end up having more points. If you fail just last problem and will not be able to debug it in time you will end up with same number of points as when following typical strategy but it will be not big number of points with significantly higher time what will cause a big fall in standings either way. As you can see such strategy is connected to significant risk of failing (look up moejy0viiiiiv's pic and think what would he achieve if he had followed typical strategy), so maybe that's not that bad? My opinion is that it is still kind of cheating but because of what I told significantly less cheaty than it seems :P. And as I told before, something should be done to prevent this. (As a shitty justification for myself, I am currently sick and wanted to compete, but was afraid of getting really poor result)
•  » » » » » 16 months ago, # ^ |   +35 I'am not Petr so it's probably called "different opinions", not "double standards".Well, to be honest, I don't really thinks it is something bad. But I always thought, for most people such contest have three main purposes1) training2) having fun3) comparing yourself to other people, you will compete in more official contests, like ICPC. And i just don't understand what is fun for such strategy, and really thinks that it's making training and comparing worse.
•  » » » » » » 16 months ago, # ^ |   +41 Sirlin explains it best: http://www.sirlin.net/articles/playing-to-winOn the one hand, the strategy is clearly not the way you would want people to compete. On the other hand, the strategy clearly gives the user an advantage. The only reasonable course is to ask AtCoder (and Codeforces, to a lesser extent) to change their contest formats and patch this loophole.
•  » » » » » » 16 months ago, # ^ |   +10 I think having the opportunity to tell someone "haha u jelly bro, this strategy gave me so much win" is totally fun.
 » 16 months ago, # |   0 http://agc018.contest.atcoder.jp/submissions/1449854Someone tries to use this code to make judging very slow.At nearly the end of the contest, I spend 10 minutes to get feedback.That's too bad.
 » 16 months ago, # |   0 I solved the 300 after submitting 8 guesses, and I don't know why it worked.Can someone please explain the solution?
•  » » 16 months ago, # ^ |   0 Editorial is available here. (There's always an editorial 1-2 minutes after contest)
•  » » » 16 months ago, # ^ |   0 Oh, that's nice! Thank you for telling me.
 » 16 months ago, # |   0 You have very weak test data on A. I've got AC with totally wrong idea... http://agc018.contest.atcoder.jp/submissions/1445462
•  » » 16 months ago, # ^ |   0 I really do not understand how this solution is related with the task :D At least that you asked imam[ p[i] — k ] :D
•  » » 16 months ago, # ^ |   +10 apiad's solution is wrong as well :)fails on2 126 15
•  » » » 16 months ago, # ^ | ← Rev. 2 →   0 Isn't apiad's username on AtCoder simply apiad xd?EDIT: I don't get something here xd. AtCoder seems to distinguish user name (mjy something) and user id (apiad). What is the logic behind it? It is confusing.
•  » » 16 months ago, # ^ |   0 What the heck? You're checking if k=pi+pj or k=pi and k<=max(pi) o0. Why did you think it is a good idea to submit it if it can't even handle "k=1, p1=2, p2=3" xD? It would be more natural to check if k=pi-pj, I see no logic that can lead one to coming up with such a solution :P. And even more surprisingly, why did it pass xD? It is so incredibly easy to break that with small random cases.
•  » » 16 months ago, # ^ |   +10 ANIMAL, but trivial mistake your solution could be corrected with bitset Check this for further explanation http://codeforces.com/blog/entry/53168
 » 16 months ago, # |   +42 By the way, problem A uses the same idea as 346A - Alice and Bob.I was inspired by this problem to set 773F - Test Data Generation for VK Cup 2017 Round 3.
•  » » 16 months ago, # ^ |   0 Interesting. Two consecutive AGCs with non-original ideas.(By saying last round, I'm referring to this task)
•  » » » 16 months ago, # ^ | ← Rev. 11 →   +4 [deleted]
•  » » » » 16 months ago, # ^ | ← Rev. 2 →   0 [deleted]
•  » » » » » 16 months ago, # ^ | ← Rev. 2 →   +1 [deleted]
•  » » » 16 months ago, # ^ |   +12 Sorry for spamming so many posts. I was not in a good mood recently, and today I was feeling a little bit sick. It was very hot outside and I just got in so I was not feeling pretty comfortable.Downvoting or Upvoting is up to you. If you don't like my posts or comments, just downvote it. I shouldn't be so emotional. Sorry.
•  » » » » 16 months ago, # ^ |   +18 Why do you care about contribution? And how is your "high" rating could be related to that?Yes,I know that you're much stronger than me (if that makes the sense). But why are you talking about this?If your posts/comments are getting so many downvotes, it means that community hasn't liked it
•  » » » » » 16 months ago, # ^ |   +40 You are right. I was pretty irrational just now. Actually I am pretty surprised at what I just said. Sorry.
•  » » 16 months ago, # ^ |   +15 The idea of problem C is also used in the past more than once. https://www.hackerrank.com/contests/blackrock-codesprint/challenges/audit-sale/problem and http://codeforces.com/contest/730/problem/I (with smaller constraints but some people solved it in a faster way).
•  » » » 16 months ago, # ^ |   +10 Dammit, I could have copied our fast solution from cf problem based on parametric search xD (better known as "trick from aliens") (I didn't solve today's C) (but that wouldn't change my place either way xD)
•  » » » » 16 months ago, # ^ |   +33 By the way, speaking about the trick from aliens.I've tried to apply it yesterday in the TopCoder hard problem. However, I couldn't even make it pass one of the samples. Now it seems to me that it was not applicable at all, because the function "cost if we have K segments" is not a convex function of K. Is that a good criterion for the applicability of the trick? Is there a thread/editorial where I can learn more?
•  » » » » » 16 months ago, # ^ |   +20 Hah, I and krismaz also independently tried to use this trick yesterday :). And yeah, we didn't give much thought to its correctness, it doesn't work :). Convexity is exactly the condition that is needed. However if convexity is not strict then sometimes additional care needs to be taken if result needs to be restored.
•  » » » » » » 16 months ago, # ^ |   +15 What is "trick from Aliens"?
•  » » » » » » » 16 months ago, # ^ |   +37
 » 16 months ago, # |   0 Is there a combinatorial interpretation of formulas for problem E?(I mean formulas in the first part of editorial)
•  » » 16 months ago, # ^ |   +18 Identity we want to prove: 1D version of this identity is well known (as golf club or Christmas stocking identity) and it's combinatorial explanation is that every path going up or right (denoted as U and R) from (0,0) to (a,b) has a unique form (U + R) * RU *  (as regular expression). I tried to generalize this idea to 2D and observed that (almost) every such path has unique form (U + R) * RU + R *  (and number of such expressions is clearly our LHS). Only path that has no such form is UbRa what stands for this subtracted one.
 » 16 months ago, # |   +46 There's an interesting way to interpret the second part of the solution for problem E.Let's consider Stokes' theorem. It says the integral over a region can be computed as some integral over its boundary.For problem E, we can think of it as replacing a sum over some grid cells in a region with a sum over its boundary. In fact, this technique seems to work for arbitrary shaped regions, even ones with holes in them.I'm wondering if there is some way to formalize this connection, or if I'm just imagining things and this is all just a notorious coincidence.
 » 16 months ago, # |   +10 I couldn't get why the author's solution for Problem F (Two trees) meets all the constraints.Could someone explain it to me?Thanks!
•  » » 16 months ago, # ^ | ← Rev. 2 →   +5 Consider an eulerian cycle in the graph described in the editorial. Each cycle consists of alternating paths in the first tree and second tree with edges joining endpoint of a path of previous tree with startpoint of path of current tree. Now according to the method described in editorial , for each path , each of the path's nodes subtree sum either increases / decreases by 1 except the LCA of the endpoints. Now for each node , the only time its subtree sum will change is if a path coming to this continues upward which can happen exactly once(Because each node has exactly one parent edge only) So this prove that any node which has a path passing from it will have subtree sum as +1 or -1 and since all nodes has a degree of atleast 2 , all nodes will have atleast one path passing from it and hence we are done.