Блог пользователя rng_58

Автор rng_58, история, 7 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +79
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Will there be a beginner contest as well ?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    In AGC's week there's only AGC.

    We will hold ABC in the next three weeks.

»
7 лет назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

[reminder] The contest starts in 25 minutes.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +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)

»
7 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

is the queue stuck for everyone else as well?

»
7 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

How to solve problem C:Coins?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
        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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +31 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    You can use binary search on answer as well.

    It is easy to write check function for it

»
7 лет назад, # |
  Проголосовать: нравится +128 Проголосовать: не нравится

Die, ScarletFirebolt.

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

»
7 лет назад, # |
  Проголосовать: нравится +194 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    Jealous xD?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +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).

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +23 Проголосовать: не нравится

        tourist style

      • »
        »
        »
        »
        7 лет назад, # ^ |
        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 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)

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится +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 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.

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится +41 Проголосовать: не нравится

            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.

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится +10 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

Can someone please explain the solution?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    apiad's solution is wrong as well :)

    fails on

    2 12

    6 15

    • »
      »
      »
      7 лет назад, # ^ |
      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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Interesting. Two consecutive AGCs with non-original ideas.

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

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 11   Проголосовать: нравится +4 Проголосовать: не нравится

      [deleted]

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +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.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +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

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится +40 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +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).

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +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)

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +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?

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится +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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +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.

»
7 лет назад, # |
  Проголосовать: нравится +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.

»
7 лет назад, # |
  Проголосовать: нравится +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!

  • »
    »
    7 лет назад, # ^ |
    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.