rng_58's blog

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

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

The point values will be announced later.

We are looking forward to your participation!

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

Comments Comments (49)
| Write comment?
»
5 years ago, # |
  Vote: I like it +90 Vote: I do not like it

I really hope rounds would be announced a bit earlier in the future. Otherwise keep up the great work you are doing :)

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

    Usually I announce it around 24 hours before the match. What time is the best do you think?

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

      I mean not announcement per se. This match was not on the calendar right until today, I think, and I like to play my week in advance

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

        I think the contest was listed on the website for at least 48 hours now.

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

          And 72 hour notice is a bit too short, that's all I am saying

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

          I know I checked the website "a few days ago" and there was nothing. Very different timeframes can feel like a few days. People are sometimes very busy during the week and don't think about checking if there will be a contest on the weekend, it's happened to me a few times.

          Something like a 6-day notice is reasonable. Not an announcement, but just having the contest on the calendar, so if you check it approximately once per week, you can always take it into consideration.

          It doesn't matter when contests are frequent enough that you can always expect one, but Beginner Contests don't count.

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

            Sorry for slow notification... There will be an ARC-equivalent round next Saturday (for sure), and then two AGCs on September I hope (but not quite sure now).

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

        I dunno if you use the calendars from clist.by (I do), but they were down (not updating for either Atcoder or Codeforces) for the past couple days until today.

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

D

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

    I struggled for some years now with that problem on Timus and did managed to solve it now. I even skipped it on the round because I recognized it.

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

    Task on Timus seems much harder, as simple finding matchings one by one does not work. But yes, if you solved that task before it would not be hard to solve D.

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

    D was also on one of the Polish onsite competitions...

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

What is solution for B?

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

    greedy i would say. just keep track of 7 states.. count of people having no color, R, G, B, RG, RB and GB. Then if you encounter a color give it to someone who can complete his set.. if not possible then to someone who already has a ball of different color... if still not then give it to a person who is empty.. keep multiplying your answer with the number of people. https://atcoder.jp/contests/agc037/submissions/6957970

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

    Consider all subsets of the string "RGB", let's call "RGB" a closed group, and other subsets open, if you loop from left to right and construct the groups, for each letter you will have at most one group of each size where you can add it. If there is a group of size 2 that needs this letter, it is clear that you should add it there and close that group.

    You can't have two open groups of the same length, like "RG" and "RB", because either "G" or "B" came second and you could have closed one of the groups using it. Also you can't have two groups with a single letter as you could have joined them and minimized the difference, since you will open the second group later.

    So try to close a group using the current letter, if that's not possible, try to add it to a group with a single letter, if no open group needs this letter, create a new group with it.

    To count the number of ways, multiply the answer with the frequency of the optimal group, and update the frequencies.

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

      Yikes. Big oof. /twitter

      This seems harder than A, C, D or E to me.

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

      this greedy approach gives us the optimal answer, but what is the proof that this covers all the distributions where the final answer comes out to be optimal?

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

        The way we construct the solution can cover all distributions (non-optimal too) if we try adding each letter to all groups that need it and print all combinations. The fact that each time during the construction we have one optimal option makes our solution cover all optimal distributions. Adding a letter to a different group than the optimal one will result in one of the following:

        • Delaying the end of a group, by opening a new group early or extending another group.

        • Having two open groups while they can be merged into one.

        In both cases, we have more contribution to the cost than necessary.

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

How to solve C?

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

    Just do reverse process. In each step decrease largest one with two neighbours as much as you can. In one moment you will get first array or it is impossible.

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

      Why is it true ? How can you prove that ? I did the same but I picked any element not largest.

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

        As all the elements are positive your last operation would have made the element largest in his vicinity. Therefore going backwards works.

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

      Can you elaborate "as much as you can"? I have decreased it while it is still bigger than max(a[i], b[i - 1], b[i + 1]), but this takes WA.

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

        It should be just >= a[i].

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

          Why should this work? (Actually, it doesn't work, If I understood what you said sumbission)

          And the brute force solution, will be to pick ALWAYS the biggest element in the array. What if we can decrease an element 5 times, but after the first decrease it is not the biggest on the array anymore? Is it still ok to decrease it? This is what I don't understand

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

            In the reverse process if you decrease B[i] it becomes B[i] — B[i — 1] — B[i + 1] and since all the numbers are positive B[i] > B[i — 1] + B[i + 1]. Since B[i] > B[i — 1] and B[i] > B[i + 1], you can't perform an operation on (i — 1) or (i + 1) so you should decrease B[i] till it becomes equal to A[i] or <= B[i — 1] + B[i + 1].

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

Slightly late but D by sufficiently random but sufficiently smart swaps.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +5 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

F is K from this year GP of Xian?

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

    It looks similar. But I think the solutions are quite different.

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

      Actually, the definition of level was originally the same as that problem from opencup :D The admin taught me that it could be solved easily, but I had a different solution, so I changed the definition into the current one.

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

English editorial will be posted later, sorry.

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

I think this is an $$$O(n^2)$$$ solution for C: https://atcoder.jp/contests/agc037/submissions/6965165

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

i don't understand a guide for problem A if string is 'aa' then s[i]=s[i+1]

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

    To my stupidity, I didn't read the problem statement properly. And directly jumped to solving the problem. A life lesson today learnt that never jump to code directly without understanding the problem in hand very clearly and having a working solution in mind.

    I thought the problem is about finding the maximum partition size of unique substrings of s. And I solved this problem using DP. Only later to realize that is not the case. The actual problem asked is to partition input string into a sequence of substrings such that TWO consecutive partitioned substring should not be equal.

    So if two consecutive characters are not equal in the input string (you can check with s[i] == s[i+1]) then you can safely partition those two consecutive characters into two substrings of 1 character each, else you have to merge them or count the two as 1.

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

      untill reading ur post , i was in the same illusion...couldn't make the problem in the contest ... now did it.

      YES it's a life lesson indeed.

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

Solution for D:

UPD: Lol just realized I've done more work than necessary and I think we can just do the matching thing directly smh

My idea is to solve recursively for subrectangles. First, replace the numbers $$$a_{i,j}$$$ by $$$\lfloor\frac{a_{i,j}-1}{m}\rfloor$$$. Now, we want to rearrange each row such that each column contains all numbers from $$$0$$$ to $$$n - 1$$$.

WLOG, the top-left corner is 0. Now, move all the 0s to the left of the top row. If all 0s are already present in the top row, recurse on the remaining rows. Otherwise, suppose there are $$$A$$$ 0s on the top row. We claim that we can always find $$$A$$$ elements from each of the remaining rows such that their union contains $$$A$$$ copies of $$$1, 2, ..., n-1$$$ each. If we can do that, then we can move all of them to the left and recurse on the left and right part.

Construct a bipartite graph with parts $$$L, R$$$. $$$L$$$ contain $$$A$$$ copies of vertices labelled $$$2$$$ to $$$N$$$, denoting the rows while $$$R$$$ contain $$$c_{i}$$$ copies of the vertex $$$i (1 \le i \le N - 1)$$$, where $$$c_{i}$$$ is the number of times $$$i$$$ appears among the last $$$N - 1$$$ rows. Note that $$$c_{i} \ge A$$$ for all $$$i$$$ (or else > M — A of them will be in the first row, a contradiction).

For each cell from the $$$i \ge 2$$$-th row that contains $$$x \neq 0$$$, draw an edge from $$$i$$$ to $$$x$$$ from left to right (for every possible pairs of copies). We can easily see that the condition for Hall's Theorem is satisfied in this graph, so a matching that saturates the left hand side exists. It remains to find this matching using Dinic (we can compress the graph to make it only contain $$$N - 1$$$ vertices on each side) and we're done.

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

My solution to D:

In the array after we first order rows, we need to have every column contain exactly one number from every row in the final array. To achieve this, build the columns left to right. Note that if we have chosen which numbers to sort into the first $$$k$$$ columns, the remaining subproblem is still the same as it originally was, just with width $$$w - k$$$. Therefore, since the problem statement claims the problem can always be solved, it is still solvable. Therefore, we can pick any values for the column such that the column contains at most one value from every row in the original and final array.

Selecting some values for the column can be done with a simple bipartite matching, which is guaranteed to have a solution, since otherwise the problem would not be solvable. Let nodes $$$1, \dots, h$$$ represent the $$$h$$$ different rows we want the values to be from in the final solution, and nodes $$$h+1, \dots, 2h$$$ represent the current rows. Add an edge between nodes $$$i$$$ and $$$j + h$$$ if some value $$$v$$$ is currently in row $$$j$$$ (and not used up in the first k columns), and in row $$$i$$$ in the final solution. Then find the matching, and swap the pairs found to the column you just constructed.

Code

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

I have found a submission of problem C: https://atcoder.jp/contests/agc037/submissions/6962412 This code only uses brute force and it has nothing to do with finding the maximum value.Can anyone explain the strategy behind this code? Thanks.

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

    Solutions finding maximum value are equivalent to finding some value $$$b_i$$$ that is greater than its neighbors and $$$a_i$$$. Maximum value is just an easy way to satisfy such criteria.

    This solution indeed does that, but it finds such values in $$$O(n)$$$. I guess it fails in time the following TC:

    100000
1 1 1 ... (100000 ones) ... 1 1 1
1 3 5 ... (first 100000 odd numbers) ... 199995 199997 19999

    This is the generator:

    generator.py

    In my PC it runs in over 40 seconds. This solution just got lucky.

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

when will the English editorial be released?

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

    Added DEF, I'll add ABC on Tuesday. EDIT: ABC added too.

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

[Deleted]

→ Reply