maroonrk's blog

AtCoder Grand Contest 058 Announcement
By maroonrk, history, 2 years ago, In English

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

The point values will be 400-700-900-1000-1400-2000.

We are looking forward to your participation!

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

Comments Comments (41)
| Write comment?
»
2 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Another maroonrk round!

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

how to do rated registration

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

    You have to be a cyan or above to register for AGC which makes sense as it is supposed to be a Div 0.8 round

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

Can you please consider upgrading the kotlin compiler? The standard library improved a lot within two years passed since 1.3.72.

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

Is it me or is there a 5min delay?

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

Why is it delayed for 5 minutes?

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

start at 20:05?

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

A misconfiguration was found and the contest is delayed by 10 minutes.

I'm super sorry for the inconvenience.

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

    That's okay. Just adds more anticipation to the to-be amazing contest :)

    I love maroonrk rounds.

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

    Now that the contest has ended, what was the misconfiguration?

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

      The scores of problems were set to wrong values. It's on my checklist, but I somehow skipped the check. Again, sorry for the inconvenience.

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

The contest delay for 5 minutes and we have only 175 minutes. upd: The contest start at 20:10 and end at 23:10.

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

oh god

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

another delay?!

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

10 minutes delay!

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

oh delaycoder

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

Problem B

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

Oooooooooooooooops, I get AC in C at 23:12. TAT

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

In A we can just look at numbers on even positions and swap with maximal of their neighbours if needed.

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

Hi,I think the testcases of A maybe a little weak.

A wrong way to solve the problem is to compare every adjacent element one by one. Here is the link of the wrong solution my wrong code

As you see, it only get WA*1.

When I was chatting with my friend Pineapplello after contest, I found his AC solution is this wrong way! his code

This testcase can hack him.

6 8 1 9 2 10 3 11 4 12 5 6 7

He gives 6 1 3 5 7 9 11 instead of 5 1 3 5 7 9

Hope there will be after contest hacks.

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

Problems as unpleasant as always.

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

    LOL

    do you know how much effort Author make for such a good problemset :(

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

    For some function defined as a lexicographically minimum permutation of $$$S(x)$$$ find the existence of inverse. My brain is already exploding. If I tried this, I will definitely miss or flip some words and solve a different problem :)

    For C, I just wrote brute-force and found the rule.

    But I don't think it's unpleasant. I just think "why I have to use my time on this?", but for somebody it should be good.

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

    Problems as pleasant as always

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

Hi, can anyone explain logic behind B's DP more clear than in editorial? I understand where we get from the interval [l,r) for each a[i], but have absolutely no idea why do we add dp[i]+=dp[i+1]?

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

This is probably similar to the editorial for D, but I think it's more natural.

For any string S, divide it into maximal groups such that each group has size >= 3 and is a substring of ABCABCABC... For example, when S = ABCABBCABCACBACABBCA, we have the partition [ABCAB][BCABCA]CBA[CAB][BCA]. Within each group (e.g. [ABCAB]), mark the first 3 letters. So, we have [(ABC)AB][(BCA)BCA]CBA[(CAB)][(BCA)]

Now, we use inclusion-exclusion on the number of ()s we choose. We just need to compute for each k, the number of ways to choose a string S and choose k ()s from it. It turns out that this is easy to compute! The main observation is that once we determined the letters outside the ()s, the number of ways to determine the letters inside the brackets is of the form 2^a*3^b (with b=0 or 1).

e.g. Suppose we know S = ()AB()BCACBA()() with the initial () stuck to the beginning of the string. Then, the number of ways to choose the letters in () is 3*2^3. If the initial () is not stuck to the beginning, the number of ways is 2^4.

We can enumerate those 2 cases and in each case, the answer is 2^a*3^b*some binomial coefficient.

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

In problem D, the multivariate generating function to the answer is

$$$ \large F(a,b,c) = \frac{ab+ac+bc-a-b-c}{a+b+c-2abc-1} $$$

In particular, it means that the answer is $$$[a^A b^B c^C] F(a, b, c)$$$ and that it follows the recurrence

ans[A][B][C] = ans[A-1][B][C] + ans[A][B-1][C] + ans[A][B][C-1] - 2*ans[A-1][B-1][C-1]

Unfortunately, I don't know how to solve the problem further with this, as multivariate genfuncs are hard...

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

    To find $$$[a^Ab^Bc^C](1 + 2abc - a - b - c)^{-1} = \sum_k[a^Ab^Bc^C](a + b + c - 2abc)^k$$$, one can see that all monomials of the right hand side look like $$$a^ib^jc^k(-2abc)^l$$$, and try all possibilities for $$$l$$$, deducing the other exponents from it along with $$$(A, B, C)$$$. To find $$$[a^Ab^Bc^C]F(a, b, c)$$$, one just find some coefficient of the denominator inverse for each summand of the numerator

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

    Can you explain how did you come up with this formula?

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

      Yes.

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

      Alright, I found how to eliminate $$$(1-abc)$$$ in my calculations and I got a similar function now. I think that the correct expression is

      $$$F=\frac{3abc-a-b-c}{a+b+c-2abc-1}$$$

      and my guess would be that you forgot to sum up functions corresponding to having two correct symbols in the end, but... My method involved solving a system of 6 linear equations (3 after simple substitutions) and it took me almost an hour :( So I still would like to hear the method.

      My idea was to kind of build Aho-Korasik on forbidden substrings, then for each node in AK create a GF, then get linear equations from transitions in AK and then solve the system.

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

        Yes, you're right, I forgot about walks that end in the middle of an edge. After fixing it, I get the same formula.

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

    Amazing approach.

    By the way, after I observe your recurrence I think there is a more simple way to explain it .

    Let F[A][B][C] be the answer of "a=A,b=B,c=C". Then consider add a character after the current string , ignoring the influence of the last three characters F[A][B][C] can be written as F[A-1][B][C]+F[A][B-1][C]+F[A][B][C-1] .

    But you need to subtract the cases that last three characters are "abc"/"bca"/"cab" and these string has never appeared in all but the last three.

    If A=B=C=1 ,then you need to subtract 3.

    If A+B+C>3 then the restriction is "The fourth-to-last character cannot be the third-to-last character -1" , there are two possibilities to choose the third-to-last character . So you need to subtract F[A-1][B-1][C-1]*2.

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

In problem C, how to prove that if there's adjacent 1 2, then we can immediately delete 1?

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

What's $$$O(n\log^2n)$$$ solution of B?

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

Where can I find the current GP30 standings?

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

    We are now preparing official standings.

    Meanwhile, Clist has an unofficial one.

    → Reply