We will hold AtCoder Grand Contest 078. This contest counts for GP30 scores.
Submitting a recording will be required in order to earn a GP30 score. Click here for details.
- Contest URL: https://atcoder.jp/contests/agc078
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20260927T2100&p1=248
- Duration: 210 minutes
- Number of Tasks: 3
- Writer: yosupo
- Tester: maspy, sigma425
- Rated range: 2800 -
The point values will be 1500-1500-1500.
The problems in this contest are exceptionally difficult, so as a special exception, we set the lower bound for rated participation to 2800.
We are looking forward to your participation!
Rated lowerbound = $$$\color{red}{2800}$$$ is REALLY CRAZY.
The GP30 rules state, “In case of a tie, the average score will be used. For example, if three people are tied for first place, each will get (100 + 75 + 60) / 3 points.”
How is this handled if fewer than 30 people score 1500 points or more? It seems possible that an unlimited number of people could submit videos of themselves doing nothing and end up tied at 0 points.
In that case, would our GP score be eps(>0)?
Thank you for the notice. We don't give GP30 scores to participants with a score of 0. I've added a clause to the rule.
Fell down from 2800+ rating in the last ARC++ :)
:(
Now, I understand the reason behind the lower bound.
agc++?
Do I understand correctly that you just don't want to go over a lot of screencasts
What was the reasoning behind only using "very hard" problems and not adding any other problems? In terms of the rating system this contest seems not very balanced, IE too many rated participations get grouped into the bucket $$$0$$$ solves, and there's no way to distinguish those people. I enjoyed thinking about B, but I didn't solve it. At the end I tried to find some dumb ways to pass the problem with some bad approaches, but the testcases were quite strong :).
Actually I expected there would be ties of 0 solves and I knew it wouldn't be a good thing for the rating system, but for this contest I liked the problems very much and wanted participants to tackle on them. If I added easier problems most people would first try to solve them and that means they have less time to challenge hard tasks, so I thought it's better to go with the current problem set.
I guess I'm very different than editorial to C, so I'll share:
We'll do a bunch of reductions to the sequence and prove each of them by comparing the results of the algorithm with the brute force, because proving stuff sucks and is for primitives. In other words, the evolving "solution" still applies the brute force, but only after applying reductions to the sequence in a loop. In a while loop, as long as the sequence isn't "trivial enough", we look for the following:
Start by noticing that if the sequence contains substring ABABA or BABAB, then we could reduce the first one to A or the second one to B.
Next notice that if the sequence contains substring ABA or BAB then they (only God knows why, but we don't care) are always a valid first move and we can reduce them to a single character but remember that now the other player is supposed to start (we keep track of the parity).
The above can be extended: if we have a sequence of As of length x, then sequence of Bs of length y, then sequence of As of length z, then if $$$x \geq y \leq z$$$ holds, we can erase all those Bs and y of the remaining As.
Now the length of the sequence of lengths of constant intervals is bitonic (it firstly increases, then it decreases). Surely that has some extra properties, that I'm scared to even start thinking about.
Now we start by noticing that if the sequence begins (or ends) with ABBA or with BAAB then we could remove this prefix and the answer won't change. This has something to do with the winning player ignoring these characters, because he would be able to counter the other player if he uses them.
The above can be extended (in a super random way obviously): if the sequence starts with x As, then y Bs and then z As (obviously x <= y <= z holds) (the same holds if we swap As and Bs or look at the end instead of the beginning) and if $$$y \leq 2x$$$ (lol), then we can remove one of x As, two of y Bs and one of z As. I was unable to find such a rule for any place other than the beginning/end of the sequence.
Otherwise, if the sequence starts and ends with the same character,so for example at the beginning we have block of As, followed by block of Bs and at the end we have block of As proceeded with a block of Bs, we can remove one character from each of those 4 blocks and the answer won't change (awesome problem). I believe this again has something to do with the winning player ignoring those 4 characters, because he'll be able to counter the other player with them anyway.
Otherwise, the sequence starts and ends with a block of As followed by block of Bs (possibly swap A and B). I guess in this case pairs AB both from the beginning and from the end are somehow reserved for the first player and he will play them anyway. So we can move one such pair from the last two blocks to the first two blocks (we subtract one from last two blocks and add one to first two blocks).
We keep it going until the sequence has only two blocks of equal characters, or three maybe if you want, doesn't matter, awesome problem.
To be less toxic and a bit more productive: I find the editorial to C kinda useless — it explains the proof to some random formula that so far, from what I see, can only be guessed — I'd love to hear about a "stable" way to solve this problem (by "solve" I don't mean what the solution needs to do, but what I'm supposed to do to arrive at the solution), because I don't know a way to do that (possibly skill issue) and I'm genuinely curious to learn it.
And tbh, I have the same issue with many atcoder problems and their editorials — I think that sharing the logic that stands behind arriving at the solution instead of just pure facts might look less "professional" in the editorial (if that's what the admins are afraid of), but I think I'm not the only one that would find it very useful and beneficial — codeforces usually does that and that works well.
So, if anybody wants to share (possibly qwerty787788?) the way to solve this problem I'd appreciate it. What questions am I supposed to ask myself? What am I supposed to find interesting? What should I be looking for? Maybe something should've catch my eye (like some invariant) but didn't?
Unfortunately, can't help much... I just knew this exact problem before (and decided not to propose it anywhere because it is yet another problem where you need to notice some magic pattern that somehow works).
I regret to say that I also don't know the stable way to solve C. We had two kinds of solutions (one is explained in the editorial and the other is similar to yours) but for both solutions we need a miracle guess.
Regarding the general style of AtCoder editorials, I don't ask authors to write them "professionally". However, I also don't ask them to write step-by-step hints. The current minimum requirement for editorials is that they should be correct, so styles depend on authors.
I personally agree that having educational editorials are better. However, I'm sorry that I, as an problem author, sucks at writing such editorials. I'm too bad at explaining (or remembering) how I come up with the idea.
Anyway, thank you for the feedback, and I'll try to write better editorials for my next contest.
I’m not sure what it has to do particularly with you :P this one editorial is bad and I think there were others like that and I think that’d be better to add the intuition steps, but that’s far from the statement that you suck at writing editorial. If there’s sadly no intuition for this particular problem — well, I just don’t like this problem. I think the important feedback is that for some other problems the described solutions are „miraculous” while there is actually some clever intuition that is not shared and that people would appreciate it, so the authors should keep it in mind.
If I'm good at writing hints I can just add it myself or teach authors how to write. So that's why I feel responsible for the editorials.
I also get your point about the problem itself. I'll take it into consideration.
Sorry, I am puzzled by B — L Robust IS Editorial. The original content "If b appears before a in the sequence, appending a to (l′,b,t) yields a better state." causes curiosity--it does not work if a < t and the previous content cannot infer a >= t. Could someone solve my question?
Additionally, in this case, a could probably not to replace b, where (l', b, t) gets (l'', c, u), a < t = min(c — x — y, b — x), u <= b