### rng_58's blog

By rng_58, history, 2 months ago,

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.

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!

• +443

 » 2 months ago, # |   +28 Will you allow one to participate (unrated/rated) on day 2 if (s)he drops below 2000 after day 1?
•  » » 2 months ago, # ^ |   -6 I think all can participate, just like how contestants under 1200 rating can participate in AGC without getting rated.
•  » » » 2 months ago, # ^ |   -7 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?
•  » » » » 2 months ago, # ^ |   +9 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.
•  » » » » » 2 months ago, # ^ |   -6 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.
•  » » » » » » 2 months ago, # ^ |   +28 They registered when they were above 2000.
•  » » 2 months ago, # ^ |   +30 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).
•  » » » 2 months ago, # ^ |   -31 does this mean that those with below 2000 rating can participate unrated during contest?
 » 2 months ago, # |   +86 You are a really execellent problem setter!We will miss you.Anyway happy Christmas rng_58!
 » 2 months ago, # |   +125 BlessRNG
 » 2 months ago, # | ← Rev. 2 →   +30 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.
•  » » 2 months ago, # ^ |   +17 Problems will be published after the contest, and everyone will be able to upsolve / participate virtually.
•  » » 2 months ago, # ^ |   +4 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
 » 2 months ago, # |   +33 Why are you leaving atcoder rng_58 ??
 » 2 months ago, # |   -29 why are you leaving Atcoder???
 » 2 months ago, # |   +677 Thanks for everything!
 » 2 months ago, # |   -37 What are you planning to do in a new year?
 » 2 months ago, # |   -43 Why are you talking in the third person? "... these contests will be rng_58's last contests".
 » 2 months ago, # | ← Rev. 2 →   -45 Goodbye rng_58, please do not commit suddoku
•  » » 2 months ago, # ^ |   +92
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +117 The sudoku is wrong. There are two digits $2$ in the fifth row :D
•  » » » » 2 months ago, # ^ |   +59 That's why he died :\
 » 2 months ago, # |   -71 My rating is 1999,can I participate in it?
 » 2 months ago, # |   +14 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 .
 » 2 months ago, # |   +155 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?
•  » » 2 months ago, # ^ |   +44 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.
•  » » 2 months ago, # ^ |   +43 Imagine having an onsite WTF anytime soon in these WTF times.
•  » » 2 months ago, # ^ |   +41 Looks like turning it into an hour-long contest isn't a bad strategy ...
 » 2 months ago, # |   0 Can unrated participants compete and is it beginner frinedly?
•  » » 2 months ago, # ^ |   0 Sorry I registered for a beginner contest. Sorry to bother everyone.
•  » » 2 months ago, # ^ |   +8 What a misfortune! xD!
•  » » 2 months ago, # ^ |   0 I didn't register before the contest. And now there isn't button to do that. Is there anyway to join the contest?
 » 2 months ago, # |   +32 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).
•  » » 2 months ago, # ^ |   +32 for me, problem A is the hardest problem in the first 4 problems
•  » » » 2 months ago, # ^ |   +15 Me too!
•  » » » 2 months ago, # ^ |   +21 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.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +33 This happens all the time in AGC for some reason :DOften 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.
•  » » » 2 months ago, # ^ |   0 Yes,this time A took me nearly 50 minutes. Comparing to A, B C D are much easier to find the direction of thinking.
•  » » 2 months ago, # ^ |   -8 It seems that the performance only depends on your rank, so it doesn’t matter.
•  » » » 2 months ago, # ^ |   +25 The performance depents on your rank and the people who participate.
 » 2 months ago, # | ← Rev. 2 →   +8 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.:(
•  » » 2 months ago, # ^ |   0 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.
 » 2 months ago, # |   +33 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: $n_{<}$: how many people with an index smaller than $i$ remain in the game, $n_{>}$: how many people with an index greater than $i$ remain in the game, $s$ (how many moves have already been made by the person to move right now), the index of the player to move right now (assuming we renumbered all remaining players by integers from $1$ to $N'$: that is, all players with original indices smaller than $i$ now have indices from $1$ to $n_{<}$, the examined player has index $n_{<} + 1$, and the players with original indices larger than $i$ now have indices from $n_{<} + 2$ to $N'$. 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$).
•  » » 2 months ago, # ^ | ← Rev. 2 →   +15 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
 » 2 months ago, # |   +121 I missed 2 years ago when problem A of AGC can be solved in 5 minutes
 » 2 months ago, # |   +74 Reminder: Thank you for participating in the first contest. Don't forget to participate in the second contest too! It will start soon.
 » 2 months ago, # |   +154 Me solving day 2 A:Anyway, it was a very cute problem, maybe one of the best easy problems this year.
•  » » 2 months ago, # ^ |   +55 Cheater, you should get banana'd permanently!
 » 2 months ago, # |   0 Why there can't be only one black cell on the sample of problem C. operations#ooo oo#o oooo o#oo -------- #ooo oo#o o### oo## -------- #ooo o#o# oooo oo## -------- #ooo o##o oo## oooo -------- #ooo ooo# o#oo oooo -------- #### o##o o#oo oooo -------- ##oo o#o# o### oooo -------- ##oo oo#o oooo oooo -------- ##oo oo#o oooo oooo -------- oooo ###o ##oo oooo -------- oooo oooo oo#o oooo 
•  » » 2 months ago, # ^ |   +10 You cannot reverse######can only reverse######
•  » » » 2 months ago, # ^ |   -8 oh,my bad.
•  » » » 2 months ago, # ^ |   +8 By the way,can this problem be solved if you can flip in two directions?
 » 2 months ago, # |   +92 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!
 » 2 months ago, # |   +42 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.
 » 2 months ago, # |   +10 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.
•  » » 2 months ago, # ^ |   0 Sierpinski triangle does better, ${\left( \frac{3}{2} \right)}^6 \approx 11.4$ with $N = 3^6 = 729$ lol
•  » » » 2 months ago, # ^ |   0 Yeah, I realized that shortly after.
 » 2 months ago, # | ← Rev. 3 →   -18 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!
•  » » 2 months ago, # ^ |   +2 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.
•  » » » 2 months ago, # ^ |   0 The FFT solution is actually the official one.
•  » » » 2 months ago, # ^ |   +18 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).
•  » » » » 2 months ago, # ^ | ← Rev. 3 →   +43 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: If the adjacency list of $U$ ends with $T$, and the adjacency list of $T$ ends with $U$, then the resulting cycle cannot be Eulerian (assume otherwise and consider the last time that $TU$/$UT$ was covered). Similarly, if the adjacency list of $U$ ends with $V$, and the adjacency list of $V$ ends with $U$, the resulting cycle cannot be Eulerian, either. Note that these two cases are independent. If neither of these cases holds, then the produced cycle is Eulerian (hint: consider the cycle produced by the algorithm and take the last time the cycle leaves $U$). 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
•  » » » » 2 months ago, # ^ |   0 $\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
•  » » » » » 2 months ago, # ^ |   +10 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?
•  » » » » » » 2 months ago, # ^ |   0 Yes, that's true and really nice (getting rid of one of the 2 theorems involved and getting better complexity)
•  » » 2 months ago, # ^ |   -20 I think they used to avoid tasks related to FFT.But this is not a case after AtCoder Library released.
 » 2 months ago, # |   -114 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: Rephrasing the statement, there should be <= N = floor(d/10) distinct values of $x$, $\le N$ distinct values of $y$ and $\le N$ distinct values of $x-y$. Then there should be many distinct values of $x+y$. Let's treat all possible values of $x$ and $y$ as the input. If we pick diagonals (values of $x-y$), we know all the points we can have. Ok, let's just find all $N^2$ possible points and pick the $N$ diagonals that contain the most. To be clear, this isn't an optimal decision, just one that should be decent, intuitively. We want a lot of points, chance is that we'll have a lot of distinct $x+y$, right? Now we calculate $d$, i.e. the number of distinct $x+y$, and the ratio $d/N$. (A few runs with different choices of $x$ and $y$ omitted.) Let's try something in between random and evenly spaced values of $x$ and $y$. Fixed seed, the $i$-th value of $x$ is $ai+rnd()\%a$ and the same formula is used for $y$. Hmm, this really gives better results. The ratio is 3+, sometimes 4+. Let's try various values of $a$, seems that a power of two works pretty well. We used $N$ around 50-100. Let's increase it. With $N = 500$, the ratio is over 12. Check if it's not a bug. Submit, AC. 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.
•  » » 2 months ago, # ^ |   +12 Read the editorial, then you will feel stupid.
•  » » » 2 months ago, # ^ |   0 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.
•  » » » » 2 months ago, # ^ |   +38 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.
•  » » » » » 2 months ago, # ^ |   -35 I thought "it has at least one much worse solution" was a reason to not pick a problem, not a reason to pick it.
•  » » » » » » 2 months ago, # ^ |   -23 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
•  » » » » » » » 2 months ago, # ^ |   +1 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.
•  » » » » » » » » 2 months ago, # ^ |   +2 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.
•  » » » » » » » » » 2 months ago, # ^ |   +16 B was solved by 283 people See, this would be a good argument but it's a 4.5 hour contest.
•  » » 2 months ago, # ^ | ← Rev. 2 →   +12 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
 » 2 months ago, # | ← Rev. 2 →   0 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.
•  » » 2 months ago, # ^ | ← Rev. 2 →   +8 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.
•  » » 2 months ago, # ^ |   +16 Indeed, AGC050 A must have scared lots of participants away. I personally couldn't find a solution in 1 hour
•  » » 2 months ago, # ^ |   0 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
•  » » 2 months ago, # ^ |   +36 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.
 » 2 months ago, # |   +24 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.
 » 2 months ago, # | ← Rev. 2 →   +6 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
•  » » 2 months ago, # ^ |   +35 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 :)
 » 2 months ago, # | ← Rev. 3 →   +33 Another solution for Day2 BSuppose 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.
 » 2 months ago, # |   +125 The editorial is updated for all $12$ tasks: https://atcoder.jp/contests/agc050/editorial https://atcoder.jp/contests/agc051/editorialSo, these two are our last contests this year. Congratulations to GP30-winners!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!
 » 2 months ago, # | ← Rev. 3 →   +11 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.
•  » » 2 months ago, # ^ |   0 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.
 » 7 weeks ago, # |   +6