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

Автор maroonrk, история, 2 года назад, По-английски

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!

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

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

how to do rated registration

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

    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

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

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

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

Is it me or is there a 5min delay?

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

Why is it delayed for 5 minutes?

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

start at 20:05?

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

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

I'm super sorry for the inconvenience.

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

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

    I love maroonrk rounds.

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

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

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

      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.

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

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

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

oh god

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

another delay?!

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

10 minutes delay!

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

oh delaycoder

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

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

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

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

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

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.

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

Problems as unpleasant as always.

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

    LOL

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

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

    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.

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

    Problems as pleasant as always

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

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]?

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

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.

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

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...

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

    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

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

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

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

      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.

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

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

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

    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.

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

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

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

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

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

Where can I find the current GP30 standings?