We will hold AtCoder Grand Contest 070. This contest counts for GP30 scores.
- Contest URL: https://atcoder.jp/contests/agc070
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20241229T2100&p1=248
- Duration: 180 minutes
- Number of Tasks: 5
- Writer: Nyaan
- Tester: maspy, HIR180
- Rated range: 2000 -
The point values will be 600-1000-1000-1800-1800.
We are looking forward to your participation!
Because of some serious problems, this contest might be the last atcoder contest this year. So please treasure this precious oppotunity!
I found that it was your first time participating in AGC as a rated contestant. It showed that you actually attached importance to the contest. Wish you good luck!
Wow, very cute A! Good old $$$1/7=0.(142857)$$$ :D (but with 1/1019 this time)
B seems great too, though I couldn't figure it out even though I got a lot of good observations. I can prove that the result without forbidding anything is $$$2n^n$$$, but it still seems like a long way to go...
What made you think of decimal expansion when solving A? I OEIS'ed it :(
I brute forced when X and 2*X have a lot of digits in common, and searched the digit sequence in OEIS. Found decimal expansion of 19
It also referred me here, to try 383 after 19: magic-square-something
Then I wrote the checker to see if all multiples are present, and indeed 19 and 383 worked.
Next item on that list was 32327, which is too big. So I just guessed that maybe the first primes after 1000 would work instead. 1009 and 1013 didn't work, but 1019 worked. Proof by AC!
I just thought a number like 142857 had very good property for the problem, so I searched on Wikipedia. There, I found a link to Cyclic numbers—everything you need is on that page.
I can't imagine how to solve the problem without the Internet.
Well, I would say that the Internet is not crucial. The phenomenon of decimal expansion of $$$\frac{1}{7}$$$ was certainly fascinating to me, so it is not such a big surprise that people may understand why that happens beforehand, and even if they don't, then it is not that hard to derive on your own (I was somewhere in between). Or, even if you don't understand, you may just check expansions of $$$\frac{1}{n}$$$ for $$$n=1001, 1002, \ldots$$$ and see which one will work
who is gblaasnicse?
visit gblaasnicse in codeforces
(https://codeforces.me/profile/gblaasnicse)
Answer:The user is disabled.
Problem C can also be solved somewhat easily if you google the right keywords and dig out this paper.
Let's calculate the number of strings consisting of
(,)andX((is Alice's win,)is Bob's win andXis a draw) satisfying the conditions from the statement. Let $$$T(a, b, k)$$$ be the number of bracket sequences having $$$a$$$ opening brackets, $$$b$$$ closing brackets and $$$k$$$ occurences of((and))in total, such that on each prefix the balance is nonnegative. Afterwards, to get the answer from $$$T$$$, we have to insertXbetween all $$$k$$$ occurences of((and)), and then to distribute the remaining $$$(N - A - B - k)$$$Xs among the string which can be done with stars and bars, $$$\binom{N - (A + B + k) + (A + B)}{A + B}$$$ ways to be exact.Now $$$T$$$ can be neatly obtained from generalized Narayana numbers. If we have a bracket sequence with $$$k$$$ occurences of
(), then it has either $$$a + b - (2k - 1)$$$ or $$$a + b - 2k$$$ occurences of((and))depending on the last symbol in the sequence. In particular, if the last symbol is(, then there are $$$a + b - 2k$$$ occurences, and the number of such sequences is $$$N_{a - b - 1}(a - 1, k)$$$ since we can simply remove the last bracket and calculate the number of remaining strings. If the last symbol is), there are $$$a + b - (2k - 1)$$$ occurences, and by exclusion principle the number of such sequences is $$$N_{a - b}(a, k) - N_{a - b - 1}(a - 1, k)$$$. Thus,and
so all that's left is to enumerate $$$k$$$ in $$$\mathcal O(N)$$$ time. 61236174
Thanks for the contest!
This is probably the highest delta I've ever received for solving a single problem.I have a question for the editorial of the problem B. Suppose $$$n = 2, p_2 = 1$$$ and $$$G = \{1 \rightarrow 2, 2 \rightarrow 2\}$$$. Then $$$f(G, \emptyset) = 1, f(G, \{1\}) = 0, f(G, \{2\}) = 1, f(G, \{1, 2\}) = 1$$$ and the sum will be $$$3$$$ instead of $$$2$$$, what am I missing ? For $$$S = \{1, 2\}$$$ "consists solely of several vertex-disjoint cycles." does not work.
Thanks! The editorial has been corrected.
Thanks a lot for the round!
My screencast with mumbling and a short recap of the solutions at the end. Unfortunately my docking station stopped working about 20 minutes before the end, so there are a few minutes that are cut out, and afterwards there is no screencast, only camera.
In problem A,I use 1013 as p,but I got WA.I can't figure out why?
Submissions
Oh, it doesn't meet the requirement. I feel very upset that I only tried 1013, as the next prime 1019 is right behind it, which can be the correct answer.
In Problem C's Editorial why "(the number of ways to reach (b−1,a+1,x) with BX immediately after the diagonal crossing)." needed to be subtracted? I can understand that "BB" is to be subtracted, but why "BX"?