We will hold AtCoder Grand Contest 058. This contest counts for GP30 scores.
- Contest URL: https://atcoder.jp/contests/agc058
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220814T2100&p1=248
- Duration: 180 minutes
- Number of Tasks: 6
- Writer: maroonrk
- Tester: HIR180, satashun
- Rated range: 1200 -
The point values will be 400-700-900-1000-1400-2000.
We are looking forward to your participation!
Another maroonrk round!
how to do rated registration
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
Can you please consider upgrading the kotlin compiler? The standard library improved a lot within two years passed since 1.3.72.
Is it me or is there a 5min delay?
Why is it delayed for 5 minutes?
start at 20:05?
A misconfiguration was found and the contest is delayed by 10 minutes.
I'm super sorry for the inconvenience.
That's okay. Just adds more anticipation to the to-be amazing contest :)
I love maroonrk rounds.
Now that the contest has ended, what was the misconfiguration?
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.
The contest delay for 5 minutes and we have only 175 minutes. upd: The contest start at 20:10 and end at 23:10.
oh god
another delay?!
10 minutes delay!
oh delaycoder
Problem B
Oooooooooooooooops, I get AC in C at 23:12. TAT
In A we can just look at numbers on even positions and swap with maximal of their neighbours if needed.
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.
was about to say the same! my solution perhaps can be hacked by the same test case as well!
Thanks. It's now uploaded as after-contest-001.txt.
Problems as unpleasant as always.
LOL
do you know how much effort Author make for such a good problemset :(
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.
Problems as pleasant as always
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]?
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.
Cool, Thanks!
In problem D, the multivariate generating function to the answer is
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...
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
Wow, very cool! Thanks!
Can you explain how did you come up with this formula?
Yes.
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
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.
Yes, you're right, I forgot about walks that end in the middle of an edge. After fixing it, I get the same formula.
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.
In problem C, how to prove that if there's adjacent 1 2, then we can immediately delete 1?
What's $$$O(n\log^2n)$$$ solution of B?
Where can I find the current GP30 standings?
We are now preparing official standings.
Meanwhile, Clist has an unofficial one.