maroonrk's blog

AtCoder Grand Contest 058 Announcement
By maroonrk, history, 20 months 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?
»
20 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Another maroonrk round!

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

how to do rated registration

→ Reply
  • »
    »
    20 months 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
»
20 months 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
»
20 months ago, # |
← Rev. 2   Vote: I like it +38 Vote: I do not like it

Is it me or is there a 5min delay?

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

Why is it delayed for 5 minutes?

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

start at 20:05?

→ Reply
»
20 months 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
  • »
    »
    20 months 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
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      20 months 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
»
20 months 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
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

oh god

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

another delay?!

→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

10 minutes delay!

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

oh delaycoder

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

Problem B

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

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

→ Reply
»
20 months 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
»
20 months 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
»
20 months ago, # |
  Vote: I like it +68 Vote: I do not like it

Problems as unpleasant as always.

→ Reply
  • »
    »
    20 months 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
  • »
    »
    20 months 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
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +48 Vote: I do not like it

    Problems as pleasant as always

    → Reply
»
20 months 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
»
20 months 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
»
20 months 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
  • »
    »
    20 months 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
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

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

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

      Yes.

      → Reply
    • »
      »
      »
      20 months 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
      • »
        »
        »
        »
        20 months 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
  • »
    »
    20 months 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
»
20 months 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
»
20 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

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

Where can I find the current GP30 standings?

→ Reply
  • »
    »
    20 months 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