This weekend, we will hold two AGC contests: AtCoder Grand Contest 050 (Good Bye rng_58 Day 1) and AtCoder Grand Contest 051 (Good Bye rng_58 Day 2). Both contests count for GP30 scores.
For these contests, we use problems that were originally prepared for the postponed World Tour Finals, plus some new problems, divided into two sets. Since we change the admin from next year, these contests will be rng_58's last contests as an author.
- Contest URL: https://atcoder.jp/contests/agc050 and https://atcoder.jp/contests/agc051
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20201226T2100&p1=248 and http://www.timeanddate.com/worldclock/fixedtime.html?iso=20201227T2100&p1=248
- Duration: 210 minutes (Day 1), 270 minutes (Day 2)
- Number of Tasks: 6 each
- Writer: rng_58
- Rated range: 2000 ~
The point values will be:
- Day 1: 500 — 800 — 1000 — 1300 — 1800 — 2000
- Day 2: 500 — 800 — 1300 — 1800 — 2000 — 2400
Even though this is an online contest, we want to make it a special event like an onsite finals. Thus, we decided to make the participation right to this contest a special prize for those who reached 2000 in AtCoder. We are looking forward to your participation!
Will you allow one to participate (unrated/rated) on day 2 if (s)he drops below 2000 after day 1?
I think all can participate, just like how contestants under 1200 rating can participate in AGC without getting rated.
we decided to make the participation right to this contest a special prize for those who reached 2000 in AtCoder. We are looking forward to your participation!
Not all can participate in this AGC. Ones below 2000 rn cant even register for these (and hence cant even read problems). So the question arises will they deregister people who drop below 2000 after day 1 so as to stop them from participating on day 2. If they allow registered people below 2000 on day 2 then will it be rated for them?
Yeah I just realised that I could not register for the contest :/
Looking at the participants list, it seems that anyone who was once AtCoder orange could be registered for the contest currently, I do not know if they would be excluded from participation when the contest starts.
Currently there are few less than 2000 rated participants registered. I'm not sure if allowing them is intentional or they registered much before any limits were set. I'm not sure about "once AtCoder orange" part as well since I couldnt register few days ago when I was below 2000 (even though my peak was above 2000).
who reached 2000 in AtCoder is a bit ambiguous as well. Does it mean current rating or it means atleast once. I took the former and I have reasons to believe this.
They registered when they were above 2000.
You can register if your rating is >= 2000. I won't unregister people even if they drop under 2000 (but they will be unrated then).
You are a really execellent problem setter!
We will miss you.
Anyway happy Christmas rng_58!
BlessRNG
Will those with below 2000 rating be able to participate unrated, or participate virtually after the contest? If not, can they read/submit the problems for practice?
For me, I believe I am certainly capable of reaching 2000, but the scheduling of AtCoder rounds (in my time zone and within my schedule) meant that I had few opportunities to participate, and I did poorly on a contest once.
Problems will be published after the contest, and everyone will be able to upsolve / participate virtually.
I had similar experience. Last week, I joined in Panasonic Programming Contest (AtCoder Beginner Contest 186) and my rating was $$$1906$$$ before that contest. It seemed impossible to reach $$$2000$$$ through only one contest and I even performed badly in that contest so that my rating changed into $$$1958$$$.
I wished that I would be able to join in AtCoder Grand Contest 050 and 051 as rated contests but I failed. Then I tried to tell myself that don't mind it and just join in the contests as unrated contests. But as you see, I have already known that I can't even join in the contests. I am a little sad for that. o(╥﹏╥)o
Why are you leaving atcoder rng_58 ??
Thanks for everything!
Why are you talking in the third person? "... these contests will be rng_58's last contests".
Goodbye rng_58, please do not commit suddoku
The sudoku is wrong. There are two digits $$$2$$$ in the fifth row :D
That's why he died :\
My rating is 1999,can I participate in it?
Ain't Allowing everyone will be better , you can keep unrated people testing secondary . That is judge their solution only if no rated submission is available .
Hi Makoto,
I'm looking forward to the contests (even though 3.5 and 4.5 hours is quite grueling for old people like me :))!
And of course, best of luck in whatever you plan to do next. Looking forward to competing against you on AtCoder ;)
I'm wondering: in case maroonrk qualifies to the WTF, are you going to come back to set the problems for it, or is there another plan?
I'm looking forward to your participation :)
maroonrk knows all problems submitted to AtCoder now, so unfortunately, he can't participate in WTF regardless of his result.
Imagine having an onsite WTF anytime soon in these WTF times.
Looks like turning it into an hour-long contest isn't a bad strategy ...
Not even read access to the problems :'(
What a misfortune! xD!
Problem is too hard so that many people give up without a submission.
The people who do(comparatively) better would drop their rating.
That sounds sad and need to change(I think).
for me, problem A is the hardest problem in the first 4 problems
Me too!
When the simplest solution is to add edges from $$$i$$$ to $$$2i$$$ and $$$2i+1$$$ modulo $$$N$$$, with vertices indexed from $$$0$$$...
However, I did find it way less straightforward than B, C or D.
This happens all the time in AGC for some reason :D
Often A is some simple to write but unique construction (but it can be quite hard to come up with — it doesn't matter that it is "just $$$2i \bmod n$$$" if I don't come up with it). Meanwhile the other problems are more typical. For example BCD are all some form of DP that's not very hard to formulate after some reasonable observations.
I don't like this style of setting As — I believe that problem A should be easily solvable for everyone in the rated range. Otherwise people will give up like the parent comment states. Later problems can be much harder.
Yes,this time A took me nearly 50 minutes. Comparing to A, B C D are much easier to find the direction of thinking.
It seems that the performance only depends on your rank, so it doesn’t matter.
The performance depents on your rank and the people who participate.
Does anyone know what testcase 35 was for problem B?
My solution runs in 330 ms on all other testcases, but TLEs on that one. I'm even more confused as my solution doesn't even branch at all (ie. runtime should only depend on n), and it works fine locally on testcases of size 500.
JK, I found my bug. I set a default value of -1 in my memo table and somehow this value was an actual value, so I just recomputed it everytime.
:(
Maybe there's some cache peculiarities hidden behind the runtime? There was a recent blog complaining that accessing positions $$$p, p+2^k$$$ in memory too often causes very bad runtime.
Day1D in $$$O(n^4)$$$:
If a player to move didn't win yet, they have made $$$s$$$ moves so far, and there are $$$N'$$$ people remaining in the game ($$$N - K \leq N' \leq N$$$), then the probability the player wins in the current turn is $$$\frac{K - (N - N')}{K - s}$$$. (This is because the player already knows $$$s$$$ reserved cards out of $$$N - N'$$$.)
Let's compute the probability that the $$$i$$$-th player wins. Throughout the gameplay, we only need to know the following information:
The probability that the current player wins in their current move can be easily deduced from this information. Hence, we can implement a rather straightforward DP computing the sought probabilities for all possible states. It has $$$O(n^4)$$$ states, and it can be computed in $$$O(n^4)$$$ time.
Now, for each player $$$i$$$, the probability that this player wins overall is computed in one of the states of DP ($$$n_{<} = i-1$$$, $$$n_{>} = N - i$$$, $$$s = 0$$$, $$$\mathrm{index} = 1$$$).
Yes I've got the same solution during the contest.
I asked many friends and they all got O(n^4) solution instead of n^6......
And quite surprising that my solution to B is also O(n^4) but it passed n=500 within 600ms
I missed 2 years ago when problem A of AGC can be solved in 5 minutes
Reminder: Thank you for participating in the first contest. Don't forget to participate in the second contest too! It will start soon.
Me solving day 2 A:
Anyway, it was a very cute problem, maybe one of the best easy problems this year.
Cheater, you should get banana'd permanently!
Why there can't be only one black cell on the sample of problem C.
You cannot reverse
##
##
##
can only reverse
###
###
oh,my bad.
By the way,can this problem be solved if you can flip in two directions?
Pure awesomeness of the problems by far offsets the fatigue and frustration after only solving AB after 4.5 hours. Very much willing to skip the editorial for a while and extend the joy of thinking about them. =)
Thank you for brilliant problems throughout all the years, hope to see them again sometime!
Thanks for the awesome problems once again!
My solution to D does not involve any FFTs: let's iterate over how many times we "wrap around" the circle (this number can be negative). Then we know how many times we pass each edge in each direction, so we can use the BEST theorem to count Euler circuits.
That feeling when in problem B my ratio $$$\frac{d}{max(a, b, c)}$$$ was ~$$$9.988$$$ XD (more specifically $$$(\frac43)^8$$$. Fortunately it was easy to patch it up by adding some random points.
Sierpinski triangle does better, $$${\left( \frac{3}{2} \right)}^6 \approx 11.4$$$ with $$$N = 3^6 = 729$$$ lol
Yeah, I realized that shortly after.
A little bit disappointed by task D which seems like an absolutely not Atcoder-style task. Don't remember any task in AtCoder like "Straightforward FFT approach like in plenty of team contests".
Problems A and B were very cool for me though :)
Thanks for the awesome contests!
Could you describe your approach to D? Solution that Petr described is the definition of AtCoder problem and might have been what authors intended, but I would be interested in hearing FFT solution as well.
The FFT solution is actually the official one.
I'm not sure about the official solution (the one with FFT), but I did the same as Petr. It's worth mentioning that solution works for a cycle on K nodes in O(K^3*maxVal*logMod), so that makes it even clearer that this wasn't intended (why not let K=5 or something less approachable by particularities). In particular, that is quite a straight forward application of a rather obscure theorem (I didn't know it and had to look it up). I think that's really not what AtCoder is about, and I guess the intended solution involved more creativity (I spent a lot of time trying to approach it in some other way and failed, so it was certainly not a straight forward FFT to me).
I didn't know about the theorem, so here's what I did:
Like both of you, iterate over how many times we wrap around the cycle; from this, we get how many times each edge is traversed in each direction; call these values $$$n_{ST}$$$, $$$n_{TS}$$$, $$$n_{TU}$$$, $$$n_{UT}$$$, $$$n_{UV}$$$, $$$n_{VU}$$$, $$$n_{VS}$$$, $$$n_{SV}$$$. Assume that the graph is Eulerian.
Consider a poor man's version of Euler's cycle algorithm: for each vertex, order its adjacency list arbitrarily (this can be done in $$$\binom{n_{ST}+n_{SV}}{n_{ST}}\binom{n_{TU}+n_{TS}}{n_{TU}}\binom{n_{UV}+n_{UT}}{n_{UV}}\binom{n_{VS}+n_{VU}}{n_{VS}}$$$ ways for all vertices). Then, the $$$i$$$-th vertex on the adjacency list of any given vertex states the direction the Euler cycle should go when we enter this vertex for the $$$i$$$-th time. We follow the links, stopping when we get back to $$$S$$$ with no more available outgoing edges, and we keep our fingers crossed that the cycle we construct covers all the edges of the graph.
But the cycle doesn't have to cover all the edges of the graph. Since the original graph is Eulerian, we get that all edges incident to $$$S$$$ must have been covered. Hence, either some of the edges $$$TU$$$/$$$UT$$$ weren't covered, or it was the case for $$$UV$$$/$$$VU$$$. Now, note that:
Hence, we only need to discount invalid cases from the formula above; this can be easily done by formulas very similar to the product of the binomials above.
To be honest, when I finally figured out the solution, I was absolutely sure that this was an official solution — it's quite tricky but very easy to code. So I was a bit surprised that a wild FFT appeared. :o
$$$\mathcal O (k \min A \log \mathrm{MOD})$$$ actually, as you can eliminate this special $$$k \times k$$$ sparse matrix in $$$\mathcal O (k \log \mathrm{MOD})$$$ time
Wait guys, isn't it true that there are only $$$k-1$$$ possible shapes of arborescences (one or two directed paths of some lengths), so the total number of arborescences can be computed in $$$O(k)$$$ time using simple prefix/suffix sums?
Yes, that's true and really nice (getting rid of one of the 2 theorems involved and getting better complexity)
I think they used to avoid tasks related to FFT.
But this is not a case after AtCoder Library released.
I wanna complain (what did you expect 11) about B. It's just a bad problem when my solution is "let's do something to get a feel of the problem... oh hey it's done". When a problem has an easy solution you might stumble into without thinking, it's neither hard (has an easy solution) nor easy (can be coincidentally much harder).
Here's what I did:
rng_58 was something dumb like this tried in testing? Just generating points based on some random that limits $$$a, b, c$$$? Usually B requires some idea or at least writing some DP (standard, therefore simple), but this is just type type, oh luk a hat.
A and C are nice. D is finding the right representation and some formula bashing, ok why not.
Read the editorial, then you will feel stupid.
My problem isn't that, as the editorial says, "the solution is very simple, but it may be hard to come up with". It's that I didn't come up with anything and didn't manage to even begin solving the problem — and I still got AC.
It's a very different kind of simple than one solution that's very short LOC-wise, but you need to find the solution or you have no chance.
The problem may admit some solutions you will not be proud of, but it also admits some nice ones and the statement seems very attractive to me, so I think that is sufficient to warrant it a B spot on AtCoder.
I thought "it has at least one much worse solution" was a reason to not pick a problem, not a reason to pick it.
If it is the case for a hard problem then it becomes more of an issue, but for easier ones I think beauty takes over
Easier relative to what? AGC A-B are harder than CF div1A most of the time, these contests had high problem scores and a lot of time indicating even higher difficulty than usual. We're not talking about ABC problems here.
Of course AGC AB are far harder than CF Div1A, but are still on the easier side of the AtCoder difficulty spectrum. B was solved by 283 people and I bet that majority of them got legit easily provable solutions, so some that could have squeezed in a less enlightening solutions are not such an issue compared to a hypothetical case when the top places are decided because, say, 3 out of 4 ACs to the hardest problem are some stupid heuristics.
See, this would be a good argument but it's a 4.5 hour contest.
I have deterministic solution for B:
If we ignore C for now we get the following construction:
(1,1),(1,2),,,,,,,,(1,10)
(11,1),(11,2),,,,,,,,(11,10)
.
.
(91,1),(91,2),,,,,,,,(91,10)
now If we want to include C we can take the previous solution 10 times adding 1000i to each x,y coordinate the ith time
https://atcoder.jp/contests/agc051/submissions/19016443
Nice problems.Thanks a lot!
On a sidenote I think problem ratings on kenkoooo are messed up(I don't understand how 50A is 1973 ,51A is 1495 and 51B is 1759) I think this has happened because lots of people don't submit anything.Like if you compare these problems to ABC/ARC problems of similar ratings they are much much harder.
I imagine problem ratings can't be very low if the round itself had a lower bound on rating. I don't know how exactly they are calculated but if all solvers are 2000+ then the rating will also probably be relatively high.
Indeed, AGC050 A must have scared lots of participants away. I personally couldn't find a solution in 1 hour
because of this lots of people gained lesser rating than they should/lost more rating than they should.I don't understand how solving only 1 problem in AGC51 gives a 1037 performance(green)
https://atcoder.jp/contests/agc051/results
I am the author of the difficulty estimator on kenkoooo (AtCoder Problems). I think the rating estimate is biased due to lots of people who didn't submit, as you explained. In addition, the contest had extremely longer duration compared to ABC/ARC. Longer duration reduces the difficulty because people are able to solve more problems with it.
Duh, in E you have this classic thinking pattern you should go through "First you need to observe a problem for your solution and then you need to realize why it isn't one". I was coding the right solution before I have even done the first step, but after coding the hardest part of the problem I finally realized an issue with my thinking and didn't realize why it is not an issue xD. Very nice problem anyway.
rng_58, do you remember the mapping between the original WTF problemset and this weekend's problems? I want to see how badly I would have performed if the onsite had taken place in March :P
Originally I half-prepared 8 problems for WTF (but didn't fully finish the preparation). Then I improved lots of problems (for example changing path to tree in 1F) with a help of maroonrk and inserted four new problems (1B, 1F, 2A, 2D). I made lots of changes, so I guess you can't estimate the results of WTF :)
Suppose we already have some set of points $$$S$$$ such that $$$\frac{d}{\mathrm{max}(a, b, c)} = k$$$, and such that the set fits into the square with vertices $$$(0, 0)$$$, $$$(0, x)$$$, $$$(x, 0)$$$, and $$$(x, x)$$$.
Then we can create another set of points, by creating 3 copies of each point — one at the old location, one translated by $$$(2x+1, 0)$$$, and one translated by $$$(2x+1, 2x+1)$$$. Notice that afterwards, $$$d$$$ is multiplied by 3 (if a point is visible to D before, all 3 copies of it will be visible afterwards), while $$$a$$$, $$$b$$$, and $$$c$$$ are multiplied by 2 (the number of distinct x-coordinates, y-coordinates, and differences are all doubled). The result is that $$$\frac{d}{\mathrm{max}(a, b, c)}$$$ would be multiplied by $$$\frac{3}{2}$$$. Also notice that the set still fits into a square (with side length $$$3x + 1$$$).
We can thus start with a single point at the origin, and repeat this process over and over until $$$\frac{d}{\mathrm{max}(a, b, c)}$$$ reaches 10.
My code: https://atcoder.jp/contests/agc051/submissions/19021430
The editorial is updated for all $$$12$$$ tasks: https://atcoder.jp/contests/agc050/editorial https://atcoder.jp/contests/agc051/editorial
So, these two are our last contests this year. Congratulations to GP30-winners!
tourist Um_nik ecnerwala Benq Petr mnbvmar Radewoosh Endagorion
There is a rumor that two WTFs (for qualifiers in 2019 and 2020) will be held back to back, but not decided yet. See you when the world gets better!
Another solution to day 1 A https://pastebin.com/njXQfYQX for every point i (other than first and last) take jump position as median of left and right part i.e (1+i)/2 and (n+i+1)/2
I haven't proved it yet, it was my first thought when I saw the problem.
Why the downvotes? because I solved with observation and testing some example and didn't have a solid proof?, meh, I was just sharing that this worked, might someone who thought in this direction can share the proof for this.
I have a (somewhat handwaivy) proof. First note that you always make a jump of $$$(i+1)/2$$$ and then optionally jump an additional $$$n/2$$$. This means that in two steps, you always jump some fixed amount, then optionally an additional $$$n/4$$$ (halved from the optional part of the first jump) and then optionally an additional $$$n/2$$$ (from this jump). Repeating this pattern, after $$$x$$$ steps, you can be in any of $$$2^x$$$ evenly spaced positions.