rng_58's blog

AtCoder Grand Contest 038 Announcement
By rng_58, history, 5 years ago, In English

We will hold AtCoder Grand Contest 038. This contest counts for GP30 scores.

The point values will be announced later.

We are looking forward to your participation!

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

»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

So B, C, D are all worth $$$700$$$ points O_o, interesting!

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

How to solve A?

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

    https://atcoder.jp/contests/agc038/submissions/7635895

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

    Use some picture like this:

    $$$ 1 1 0 0 0$$$ (here $$$A$$$ ones)

    $$$ 0 0 1 1 1$$$

    ($$$B$$$ times repeat this pair)

    and then just:

    $$$ 1 1 0 0 0 $$$

    for all remainings

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

    Loop over the amount of rows you'll assign a ones to (n), and the amount of columns you'll assign b ones to (m), until you find n, m such that both give the same amount of ones for the whole array. If you find no such n, m, output -1

    For the first m columns, set their need to b. For the other columns, set their need to h-b.

    For the first n rows, put a 1 at the a columns with maximum need, and decrement their need.

    For the next h-n rows, put a 1 at the w-a columns with maximum need, and decrement their need.

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

      I've been thinking this way but couldn't prove that it works. In general if you are given degrees of the vertices the fact that sum of both parts is equal is not enough for a simple graph to exist. I couldn't find any criterion. Does anybody know it?

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

        You can model it as a flow network. Criterion that it doesn't exist translates to existence of some cut.

        EDIT: Quoting you from below: "typical flow problem" :D

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

          Well, $$$O(n)$$$ flows seemed too slow. And too hard for A.

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

            Yeah, I didnt mean that it was supposed to be solved like that. Intended way of solving A was "cout<<(i<A)^(j<B);" (I completely agree it's very hard to come up with, took me a lot of time to notice this), but the solution to the problem with fixed degrees in bipartite graph is flow.

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

    At least it seems that A is so complicated nobody can explain it. So no need to be mad for not solving it :)

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

How to solve C

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

Editorial

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

Thanks for the cool F! However, C is very typical.

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

    F also seemed like a typical flow problem to me.

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

      I've solved thousands of flow problems and still have no idea how to solve this one even though friends are explaining it to me for like 10 minutes already xd.

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

        You have some cycles, for each cycle you either make all $$$a_i = i$$$(first type) or $$$a_i = p_i$$$(second type), the same for $$$q$$$. The obvious idea would be to find a mincut between the cycles of the first type and the second type. But all our penalty edges are between the cycles of the same kind, so it doesn't work. But the graph is bipartite so we flip one of the parts: we take cycles of the first type in $$$p$$$ and cycles of the second type in $$$q$$$ and need to find min cut between cycles that we take and don't take.

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

    Yes C is typical, and in fact, it was not intended to set this problem. We were preparing another hard problem (which should have been F) but a significant issue arose form that task and we had to remove it. Then this C was inserted to the problem set and old CDE was moved to new DEF.

    I will try my best to avoid such cases in future contests. Anyway, thank you for taking part in the contest!

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

C: ORIGINAL PROBLAM DO NOT STEEL

A, B, D were pretty nice. D could have benefited from a bit more points (900?), it wasn't hard to implement but there's a lot of things to consider.

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

How to solve B?

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

    I believe this is the intended solution : For all subarrays in A of size L, see to it that the left element of leftmost element and right element of current subarray is lesser and larger than all the elements of current subarray, because if it is so, then we have a repeating subarray, think about it, it's just the same as previous subarray considered after sorting ? But are those all the repetitions? No! Repetitions could occur if 2 subarrays are already sorted right? To check a subarray of being sorted, check largest length till which subarray is sorted starting at that position(2 pointers kind of deal). But remember to keep 1 instance of the permutation where this kind of repetition occurs,ie,when 2 or more subarrays are sorted.

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

Failed to implement B with the sliding window so I implemented segment tree with hashes (2 bases was needed) :D

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

    +

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

    I implemented it with set, was thinking of deque before, but even after that, failed 2 test cases ☹️ out of 32

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

Can someone explain the PIE idea on E? I'm pretty confused by the editorial.

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

    As for how inclusion-exclusion is applied:

    Let's pretend we generate an infinite sequence, and find the expected value of the number of turns before all $$$B_i$$$ are reached. A turn counts toward our expected value if at least one of the following is true: before the turn, the number of $$$i$$$ in our sequence is less than $$$B_i$$$.

    Now for each turn, we can use inclusion-exclusion using these statements as events, to calculate the probability that it counts toward our sum.

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

Task C — LCMs is probably standard for a lot of people but it was new for me and I wasn't able to figure out the intuition behind the approach. The editorial is pretty unintuitive (atleast for me , like from where does those wi come from ? ) . Can someone explain the intuition behind it ?

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

I believe C can be done much simpler than in editorial, by simply determining what is $$$f(d) = \sum_{gcd(a_i, a_j) = d} a_i a_j$$$ for every $$$d$$$ explicitly. The trick is to consider values of $$$d$$$ in descending order and noting that $$$f(d) = g(d) - \sum_{k \ge 2} f(kd)$$$, where $$$g(d) = \sum_{d|a_i, a_j} a_i a_j$$$.

$$$g$$$ can be trivially determined, so can be $$$f$$$.

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

    Got it. Thanks a ton ! Btw the functions 'f' and 'g' you defined are pretty clever. I was wondering that this way we can even avoid doing mobius inversions at a lot of places if we define a such recurrences , is this true ? Are there any helpful resources to learn these or links to similar problems ? How did you learn this stuff ?

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

      I learn this stuff the hard way, by solving the same problem but with gcd instead of lcm on high school workshop and then presenting my solution with that inclusion-exclusion stuff, mobius inversion bullshit etc. and after 0,5h of explaining where all the people stopped listening long ago one guy came to board after me and showed this trick within a minute and I was like :oooo

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

        Hah, I remember trying and failing to solve this or something very similar. I didn't realise it was so simple back then, but I remembered not to make the same mistake now.

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

    Can you please explain what is g used in calculating the g(d) above. Also what do sum1, sum2 and sum_p represent in your submission your submission and how do they help in calculating sum_prods[g].

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

      I added a newline in my previous post, does that answer your first question :D?

      When my loop is at x, sum_1 is sum of a_i for a_i's divisible by x, sum_2 is sum of a_i^2 for a_i divisible by x (I use $$$2 \sum a_i a_j = (\sum a_i)^2 - \sum a_i^2$$$). sum_p is g(x) and from these I derive f(x) which is sum_prods[x]

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

Are there any updates on WTF? Are you planning to increase the number of advancers? How many AGCs (or similar) are yet to be in 2019? Can you update the scores? rng_58

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it 
    'Are there any updates on WTF?'

    Probably on February next year. What information do you want to know in advance?

    'Are you planning to increase the number of advancers?'

    No, sorry, this year the number of advancers will be 8 again.

    'How many AGCs (or similar) are yet to be in 2019?'

    We are planning 12 per year, so 4 more I hope.

    'Can you update the scores?'

    Updated.

    → Reply