Блог пользователя rng_58

Автор rng_58, история, 3 года назад, По-английски

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
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится -6 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится -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?

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +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.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится -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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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).

»
3 года назад, # |
  Проголосовать: нравится +86 Проголосовать: не нравится

You are a really execellent problem setter!

We will miss you.

Anyway happy Christmas rng_58!

»
3 года назад, # |
  Проголосовать: нравится +125 Проголосовать: не нравится

BlessRNG

»
3 года назад, # |
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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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

»
3 года назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

Why are you leaving atcoder rng_58 ??

»
3 года назад, # |
  Проголосовать: нравится +677 Проголосовать: не нравится

Thanks for everything!

»
3 года назад, # |
  Проголосовать: нравится -43 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится -45 Проголосовать: не нравится

Goodbye rng_58, please do not commit suddoku

»
3 года назад, # |
  Проголосовать: нравится -71 Проголосовать: не нравится

My rating is 1999,can I participate in it?

»
3 года назад, # |
  Проголосовать: нравится +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 .

»
3 года назад, # |
  Проголосовать: нравится +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?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +43 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +41 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +47 Проголосовать: не нравится

Not even read access to the problems :'(

»
3 года назад, # |
  Проголосовать: нравится +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).

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +32 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +15 Проголосовать: не нравится

      Me too!

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +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.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +33 Проголосовать: не нравится

      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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

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

»
3 года назад, # |
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.

:(

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 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.

»
3 года назад, # |
  Проголосовать: нравится +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$$$).

  • »
    »
    3 года назад, # ^ |
    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

»
3 года назад, # |
  Проголосовать: нравится +121 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +74 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +154 Проголосовать: не нравится

Me solving day 2 A:

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

operations
»
3 года назад, # |
  Проголосовать: нравится +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!

»
3 года назад, # |
  Проголосовать: нравится +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.

»
3 года назад, # |
  Проголосовать: нравится +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.

»
3 года назад, # |
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!

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      The FFT solution is actually the official one.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +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).

      • »
        »
        »
        »
        3 года назад, # ^ |
        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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 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

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится +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?

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится -20 Проголосовать: не нравится

    I think they used to avoid tasks related to FFT.

    But this is not a case after AtCoder Library released.

»
3 года назад, # |
  Проголосовать: нравится -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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    Read the editorial, then you will feel stupid.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 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.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +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.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится -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.

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится -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

            • »
              »
              »
              »
              »
              »
              »
              3 года назад, # ^ |
                Проголосовать: нравится +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.

              • »
                »
                »
                »
                »
                »
                »
                »
                3 года назад, # ^ |
                  Проголосовать: нравится +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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 года назад, # ^ |
                    Проголосовать: нравится +16 Проголосовать: не нравится

                  B was solved by 283 people

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

  • »
    »
    3 года назад, # ^ |
    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

»
3 года назад, # |
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.

  • »
    »
    3 года назад, # ^ |
    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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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.

»
3 года назад, # |
  Проголосовать: нравится +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.

»
3 года назад, # |
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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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 :)

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +33 Проголосовать: не нравится
Another solution for Day2 B
»
3 года назад, # |
  Проголосовать: нравится +125 Проголосовать: не нравится

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!

»
3 года назад, # |
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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 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.

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится