rng_58's blog

AtCoder Grand Contest 018
By rng_58, history, 7 years ago, In English

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

Contest Link

Contest Announcement

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

Let's discuss problems after the contest.

  • Vote: I like it
  • +79
  • Vote: I do not like it

Comments Comments (63)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will there be a beginner contest as well ?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In AGC's week there's only AGC.

    We will hold ABC in the next three weeks.

    → Reply
»
7 years ago, # |
  Vote: I like it +33 Vote: I do not like it

[reminder] The contest starts in 25 minutes.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    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)

    → Reply
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

is the queue stuck for everyone else as well?

→ Reply
»
7 years ago, # |
  Vote: I like it +28 Vote: I do not like it

How to solve problem C:Coins?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    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.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +57 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Can you please elaborate more on its correctness part,I am not able to get that!

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it +6 Vote: I do not like it

        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.

        → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +50 Vote: I do not like it

      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.

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    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.

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can anyone help me figure out, why this approach is wrong? Code

    I 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.

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

I'm surprised at 400+ AC in problem B. Is it really that easy?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    Start with all the events and get the most popular one. Now remove that maximum and repeat until no events are left.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Can you give me an example? I don't really understand what you mean by 'popular'.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        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.

        → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You can use binary search on answer as well.

    It is easy to write check function for it

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to write the check function?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        On every step, remove that sports which appears more than mid and ban that sport

        CODE

        → Reply
»
7 years ago, # |
  Vote: I like it +128 Vote: I do not like it

Die, ScarletFirebolt.

The trouble happened because of this hacker. We are sorry for inconvenience.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

    What did he do ?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +51 Vote: I do not like it

      Submit one-line infinite loop every second. We'll add some submission limit next time...

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When will be the queued submissions judged?

    → Reply
»
7 years ago, # |
  Vote: I like it +194 Vote: I do not like it

After solving A, D, E, F and calculating the score carefully, I submmited.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I felt today's problems are very easy to get wrong for whatever reason.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Jealous xD?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +70 Vote: I do not like it

      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).

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +23 Vote: I do not like it

        tourist style

        → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it +46 Vote: I do not like it

        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 jqdai0815'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)

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +35 Vote: I do not like it

          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 purposes
          1) training
          2) having fun
          3) 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.

          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it +41 Vote: I do not like it

            Sirlin explains it best: http://www.sirlin.net/articles/playing-to-win

            On 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.

            → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

            I think having the opportunity to tell someone "haha u jelly bro, this strategy gave me so much win" is totally fun.

            → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

http://agc018.contest.atcoder.jp/submissions/1449854

Someone 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.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved the 300 after submitting 8 guesses, and I don't know why it worked.

Can someone please explain the solution?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Editorial is available here. (There's always an editorial 1-2 minutes after contest)

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You have very weak test data on A. I've got AC with totally wrong idea... http://agc018.contest.atcoder.jp/submissions/1445462

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I really do not understand how this solution is related with the task :D At least that you asked imam[ p[i] — k ] :D

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    apiad's solution is wrong as well :)

    fails on

    2 12

    6 15

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    ANIMAL, but trivial mistake your solution could be corrected with bitset Check this for further explanation http://codeforces.net/blog/entry/53168

    → Reply
»
7 years ago, # |
  Vote: I like it +42 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Interesting. Two consecutive AGCs with non-original ideas.

    (By saying last round, I'm referring to this task)

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 11   Vote: I like it +4 Vote: I do not like it

      [deleted]

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +40 Vote: I do not like it

          You are right. I was pretty irrational just now. Actually I am pretty surprised at what I just said. Sorry.

          → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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.net/contest/730/problem/I (with smaller constraints but some people solved it in a faster way).

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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)

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +33 Vote: I do not like it

        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?

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +20 Vote: I do not like it

          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.

          → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a combinatorial interpretation of formulas for problem E?(I mean formulas in the first part of editorial)

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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.

    → Reply
»
7 years ago, # |
  Vote: I like it +46 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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!

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    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.

    → Reply