rng_58's blog

AtCoder Grand Contest 050/051 (Good Bye rng_58 Day 1 / Day 2) Announcement
By rng_58, history, 4 years ago, In English

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!

  • Vote: I like it
  • +443
  • Vote: I do not like it

Comments Comments (84)
| Write comment?
»
4 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Will you allow one to participate (unrated/rated) on day 2 if (s)he drops below 2000 after day 1?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    I think all can participate, just like how contestants under 1200 rating can participate in AGC without getting rated.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it -6 Vote: I do not like it

          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.

          → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    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).

    → Reply
»
4 years ago, # |
  Vote: I like it +86 Vote: I do not like it

You are a really execellent problem setter!

We will miss you.

Anyway happy Christmas rng_58!

→ Reply
»
4 years ago, # |
  Vote: I like it +125 Vote: I do not like it

BlessRNG

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +30 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Problems will be published after the contest, and everyone will be able to upsolve / participate virtually.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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

    → Reply
»
4 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Why are you leaving atcoder rng_58 ??

→ Reply
»
4 years ago, # |
  Vote: I like it +677 Vote: I do not like it

Thanks for everything!

→ Reply
»
4 years ago, # |
  Vote: I like it -43 Vote: I do not like it

Why are you talking in the third person? "... these contests will be rng_58's last contests".

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -45 Vote: I do not like it

Goodbye rng_58, please do not commit suddoku

→ Reply
»
4 years ago, # |
  Vote: I like it -71 Vote: I do not like it

My rating is 1999,can I participate in it?

→ Reply
»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like 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 .

→ Reply
»
4 years ago, # |
  Vote: I like it +155 Vote: I do not like it

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?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +44 Vote: I do not like it

    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.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +43 Vote: I do not like it

    Imagine having an onsite WTF anytime soon in these WTF times.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +41 Vote: I do not like it

    Looks like turning it into an hour-long contest isn't a bad strategy ...

    → Reply
»
4 years ago, # |
  Vote: I like it +47 Vote: I do not like it

Not even read access to the problems :'(

→ Reply
»
4 years ago, # |
  Vote: I like it +32 Vote: I do not like it

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).

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    for me, problem A is the hardest problem in the first 4 problems

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      Me too!

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +33 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes,this time A took me nearly 50 minutes. Comparing to A, B C D are much easier to find the direction of thinking.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    It seems that the performance only depends on your rank, so it doesn’t matter.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +25 Vote: I do not like it

      The performance depents on your rank and the people who participate.

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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.

:(

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +33 Vote: I do not like it

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$$$).

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +15 Vote: I do not like it

    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

    → Reply
»
4 years ago, # |
  Vote: I like it +121 Vote: I do not like it

I missed 2 years ago when problem A of AGC can be solved in 5 minutes

→ Reply
»
4 years ago, # |
  Vote: I like it +74 Vote: I do not like it

Reminder: Thank you for participating in the first contest. Don't forget to participate in the second contest too! It will start soon.

→ Reply
»
4 years ago, # |
  Vote: I like it +154 Vote: I do not like it

Me solving day 2 A:

Anyway, it was a very cute problem, maybe one of the best easy problems this year.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +55 Vote: I do not like it

    Cheater, you should get banana'd permanently!

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why there can't be only one black cell on the sample of problem C.

operations
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    You cannot reverse

    ##

    ##

    ##

    can only reverse

    ###

    ###

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      oh,my bad.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      By the way,can this problem be solved if you can flip in two directions?

      → Reply
»
4 years ago, # |
  Vote: I like it +92 Vote: I do not like it

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!

→ Reply
»
4 years ago, # |
  Vote: I like it +42 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sierpinski triangle does better, $$${\left( \frac{3}{2} \right)}^6 \approx 11.4$$$ with $$$N = 3^6 = 729$$$ lol

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it -18 Vote: I do not like it

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!

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The FFT solution is actually the official one.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      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).

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 3   Vote: I like it +43 Vote: I do not like it

        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

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        $$$\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

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          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?

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yes, that's true and really nice (getting rid of one of the 2 theorems involved and getting better complexity)

            → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    I think they used to avoid tasks related to FFT.

    But this is not a case after AtCoder Library released.

    → Reply
»
4 years ago, # |
  Vote: I like it -114 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Read the editorial, then you will feel stupid.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +38 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it -35 Vote: I do not like it

          I thought "it has at least one much worse solution" was a reason to not pick a problem, not a reason to pick it.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it -23 Vote: I do not like 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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              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.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                4 years ago, # ^ |
                  Vote: I like it +2 Vote: I do not like it

                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.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                    Vote: I like it +16 Vote: I do not like it

                  B was solved by 283 people

                  See, this would be a good argument but it's a 4.5 hour contest.

                  → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +12 Vote: I do not like it

    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

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Indeed, AGC050 A must have scared lots of participants away. I personally couldn't find a solution in 1 hour

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +24 Vote: I do not like 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.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    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 :)

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +33 Vote: I do not like it
Another solution for Day2 B
→ Reply
»
4 years ago, # |
  Vote: I like it +125 Vote: I do not like it

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!

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

→ Reply