rng_58's blog

By rng_58, history, 5 years ago, In English

We will hold AtCoder Grand Contest 035. This contest counts for GP30 scores.

The point values will be announced later.

We are looking forward to your participation!

UPD: We are very sorry, due to an urgent trouble we delay the round by 30 minutes. UPD2: We fixed the trouble and the round will start from 21:30 JST. Again we are very sorry for the inconvenience.

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

| Write comment?
»
5 years ago, # |
  Vote: I like it -36 Vote: I do not like it

i am sofa.

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

    this ??

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      Why so many people do not like my comment.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        According to the (virtual) rules of codeforces you need to be at least orange to get upvotes on such a shitty comment

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          OK, i know it now.

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

            BTW do you know what does that mean, your first comment?

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it +69 Vote: I do not like it

              In China, It means the first comment of all.

              • »
                »
                »
                »
                »
                »
                »
                »
                5 years ago, # ^ |
                  Vote: I like it +29 Vote: I do not like it

                So it's like the usual Youtube comment "first"?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                    Vote: I like it +20 Vote: I do not like it

                  Yup :>

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

                  Ok, yeah, these kinds of comments always deserve downvotes.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +13 Vote: I do not like it

          Probably you need people who understand what "Sofa" means and knows you too to give you upvotes before other people follows.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    What's the meaning of 'sofa'? I can't understand

»
5 years ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

Falls on the same date as Educational Codeforces Round #68 so I can take part in both contests.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it +61 Vote: I do not like it

Does the delay have to be 30 minutes? In that case it will clash with the next Codeforces round.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    The overlap is like 5 minutes and there's usually nothing to do in the last x minutes of the contest, so it's not that bad.

»
5 years ago, # |
Rev. 2   Vote: I like it -7 Vote: I do not like it

And now I don't wanna give this contest anymore.

»
5 years ago, # |
  Vote: I like it +81 Vote: I do not like it

First and last time I will ever write this, but

Please delay Educational by 10 mins)))

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

And now it's clashing with Educational round 68 ;_;

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

It seems that I have to stay up a little late.

»
5 years ago, # |
Rev. 2   Vote: I like it -27 Vote: I do not like it

i deleted my response

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

    I believe you have plenty of time to eat during the contest.

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it -17 Vote: I do not like it

      i deleted my response

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

        Maybe you can find inspiration by going to dinner when you have difficulty in solving problem a.

»
5 years ago, # |
Rev. 3   Vote: I like it -55 Vote: I do not like it

The answer for First question for test case

4

3 3 3 3

should be NO. But my code gives answer as Yes and it is accepted. There exist no permutation of given input which will satisfy the given constraint but it is passing my solution which basically does this: Compute xor of all input and print YES if it 0 else print NO.

the test cases are certainly weak or the tester/setter code is incorrect.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -95 Vote: I do not like it

    It is also giving tle for just insert and erase in multiset. The submission which is correct gives tle and submission which is logically incorrect is accepted. This makes no sense.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +58 Vote: I do not like it

      Next time, don't discuss problems during the contest.

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it -155 Vote: I do not like it

        Next time set better quality contest and don't give chance to anyone to discuss.

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

          Next time and also this time, follow the rules.

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it -118 Vote: I do not like it

            First of all you start following the rule of uploading correct test cases, then automatically all the rules will followed.

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it +28 Vote: I do not like it

              Why should I upload test cases for a contest I'm competing in? That doesn't make any sense.

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Why is problem C named after Skolem?

»
5 years ago, # |
  Vote: I like it +39 Vote: I do not like it
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think B appears at least yearly in one contest (it's been part of the Romanian folklore for at least 12 years). In mathematics it's even better known. I find it very odd that atcoder would use such a problem. Also, B was significantly easier than C, I find it strange they had the same score

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Well, for me C was much easier than B. I haven't seen B before, it was an interesting problem for me.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B

»
5 years ago, # |
  Vote: I like it +20 Vote: I do not like it

How to solve C?

  • »
    »
    5 years ago, # ^ |
    Rev. 6   Vote: I like it 0 Vote: I do not like it

    Here's a simple way to solve the problem:

    Let's first say Vertex $$$N+i$$$ as $$$i$$$ for simplicity, and all we need to do is place 2 vertexes with value $$$i$$$ such that it forms the required tree, where the weight of each vertex is its value.

    Now, take the first case when $$$N$$$ is odd, Place $$$1$$$ as the root of the tree, and for each $$$i$$$ where $$$i$$$ is even, connect with $$$1$$$ the following $$$2$$$ branches, $$$(i+1)-i-$$$ and $$$i-(i+1)-$$$. This would complete the requirement for all $$$i$$$ and $$$i+1$$$ such that $$$i$$$ is even. Next, we are only left to satisfy $$$1$$$ which could be simply done by connecting it to the leaf of any of the branches connected to $$$1$$$.

    Next case, when $$$N$$$ is even, We can do the above process to satisfy each vertex up to value $$$N-1$$$. Now, we just need to satisfy the criterion for vertex $$$N$$$ as well. We could show that these two vertexes must not be on the same branches, otherwise we wouldn't be able to satisfy vertex $$$N$$$, let's say they are on different branches, then, 1 must lie on the path between them, So, $$$1 \oplus x = N$$$ where $$$x$$$ is the weight of other vertexes on path, so, $$$x = N+1$$$. Another observation would be the following, that $$$N$$$ must be connected to the direct children of $$$1$$$. So, All we need to do is find two vertexes $$$j$$$ and $$$k$$$ $$$(1 \lt j,k \lt N)$$$. such that $$$j \oplus k = N+1$$$.

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

    Good question. It took me probably over an hour to figure it out.

    If $$$N$$$ is a power of $$$2$$$, there's obviously no solution. Otherwise, there is a solution. For $$$N$$$ odd, it's easy, just make paths $$$(2k+1)-(2k)-1-(2k+1+N)-(2k+N)$$$ and add $$$N+1$$$ somewhere to the bottom.

    For $$$N$$$ even, we have to do something with the $$$(N, 2N)$$$ pair. For example, a path $$$(N)-(N+1-2^k)-(1)-(2^k)-(N+N)-(N+N+1-2^k)-(N+1)-(N+2^k)$$$ can do it, where the $$$k$$$-th bit in $$$N$$$ is $$$1$$$ ($$$k > 0$$$). This means we can't add all the remaining pairs $$$(2k, 2k+1)$$$ just like for $$$N$$$ odd, since we broke the pairs $$$(2^k, 2^k+1)$$$ and $$$(N-2^k, N+1-2^k)$$$. Fortunately, we can add $$$(2^k+1, N+2^k+1)$$$ from the first pair as $$$(2^k+1)-(1)-(2^k)-(N+2^k+1)$$$ and $$$(N-2^k, N+N-2^k)$$$ from the second pair as $$$(N-2^k)-(N+1-2^k)-1-(N+N-2^k)$$$, and the rest can be handled like for $$$N$$$ odd.

»
5 years ago, # |
  Vote: I like it +21 Vote: I do not like it

D: Is this solution intended to pass? Because it runs like a beast, in <= 4 ms:

Contiguous sequences of eaten cards are independent, so for each of them, let's find out all pairs of costs it can send to its (left, right).

Let's take a sequence from card $$$l$$$ to card $$$r$$$. We're assuming that cards $$$l-1$$$ and $$$r-1$$$ haven't been eaten yet and the last of the cards $$$l$$$ through $$$r$$$ that's eaten is card $$$c$$$. Let's denote the set of pairs of costs added to cards $$$l-1$$$ and $$$r-1$$$ by eating these cards by $$$P_{l, r}$$$. For each pair $$$(x, y)$$$ in $$$P_{l, c-1}$$$ and $$$(z, w)$$$ in $$$P_{c+1, r}$$$, eating card $$$c$$$ (with cost $$$A_c + y + z$$$) afterwards means that we get a pair $$$(x+A_c+y+z, w+A_c+y+z)$$$ in $$$P_{l, r}$$$. We can try all possible $$$c$$$ and compute $$$P_{l, r}$$$ for each $$$l, r$$$.

This is easy and it's slow, probably $$$O(N!)$$$. However, here comes a heuristic. Whenever there's a pair $$$(a, b)$$$ in $$$P_{l, r}$$$ such that there is a pair $$$(c, d)$$$ in $$$P_{l, r}$$$ with $$$c \le a, d \le b$$$, we can discard $$$(a, b)$$$. Discarding all such pairs is just sorting and one pass. That's it.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -38 Vote: I do not like it

    sir, can u plz explain in detail(easier version) , i'm new in cp... thanks!!

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

      It's a question for the organisers.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried B by simply iterating over the vertices and setting edge directions to make degree even but i am getting WA on some testcases. can someone please explain where this logic fails? https://atcoder.jp/contests/agc035/submissions/6375813

»
5 years ago, # |
  Vote: I like it +23 Vote: I do not like it

I think for people like me who don't use prewritten code it would be nicer if you give some substantial amount of points for $$$O(n \log n \log m)$$$ in F (calculating power of polynomial via binary exponentiation, not $$$\log$$$ and $$$\exp$$$).

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

    From the editorial, it seems to me like this wasn't intended to pass, with or without prewritten code.

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

    Wow, checked tourist's solution and it was apparently possible to squeeze NTT in.

    You probably already checked the editorial, but the intended solution is just one loop in linear time, and the NTT solution misses a key idea, so maybe the opposite should've been done and constraints raised further to disallow all kinds of NTT?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +91 Vote: I do not like it

      Wow, checked tourist's solution and it was apparently possible to squeeze NTT in.

      Sure, but it is a well known fact that when a CPU encounters tourist's code, it gets scared and runs twice as fast.

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

      OK, intended solution is cooler :)

      Funny that if I didn't think that I have any chances to get AC with $$$O(n \log n \log m)$$$, I could probably find a way to simplify the polynomial on paper.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Sorry we didn't know the existence of such solutions. Our intended solution is simple $$$O(n log n)$$$.

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

    Simple reduce to $$$O((N + M)log(N + M))$$$ by Taylor: $$$(\sum(\frac{n - i + 1}{i!}x^i)^m = (\sum(\frac{n + 1}{i!})x^i-\sum(\frac{1}{i!})x^i)^m=(n + 1 - x)^me^{mx}$$$.

    Easily to apply NTT here.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      And then we can multiply it by $$$n! e^{x}$$$, take coefficient before $$$x^{n}$$$ and get exactly the formula from editorial. Yes, I can do math too, but not when I have 18 minutes left and I'm writing FFT.

»
5 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

My approach to F, which sadly didn't work out. Make a grid $$$(N+1) \times (M+1)$$$. In each row except the first one place a red token in some cell, similarly place blue token in some cell in each column except first. Blue and red token can share a cell. This token represents the number selected in row and column, respectively.

A forbidden configuration is one that has a blue token directly below red one. In that case, we can move the tokens around to achieve a configuration without this pair, but one that generates the same grid. Now we have the following DP:

$$$DP[i][j]$$$ = number of ways of placing red and blue tokens in columns $$$(1..i)$$$, such that $$$j$$$ red tokens have been used.

The transition is $$$DP[i][j+k] = DP[i][j] * (M+1-k) * {M-j \choose k}$$$. Naively, this is $$$\mathcal O(NM^2)$$$.

This is equivalent to $$$DP[N][j] = \sum \frac{M!}{\prod_{i=1}^N x_i! \cdot (M+1-x_i)}$$$ where $$$\sum x_i \leq M$$$, from which we can compute the answer. This can be computed by NTT and binary exponentiation in $$$\mathcal O(N \log N \log M)$$$.

However, this is where I got stuck (or more precisely, the time ran out) — the input is too big to allow two logarithms, let alone the big constant of NTT, it runs for more than $$$20$$$ seconds even for $$$N=M=10^5$$$.

EDIT: I read Um_nik's comment above and agree.

»
5 years ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

.........................................

»
5 years ago, # |
  Vote: I like it +60 Vote: I do not like it

AtCoder doesn't stop to amaze with their insane quality of problems. I absolutely loved E and F seemed to be great as well, but I didn't have time for it.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +40 Vote: I do not like it

    If I had to be really picky, I would object to B and C being constructive graph problems. But you're right, I enjoyed every single one that I solved and also loved revealing the secrets of F.

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

    I can't comment on E or F and I liked C and (in principle) D, but B shouldn't have been used, since it's too standard. Also, A and maybe D allowed me to get an unfairly high place.

»
5 years ago, # |
  Vote: I like it -38 Vote: I do not like it

There's some issues with the problem A. Consider this test case:
4
1 2 5 6
The answer should be 'No'. But many solutions output 'Yes', like #6386417, while some solutions output 'No', like #6386376, and they're both AC. This round should be unrated!

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -24 Vote: I do not like it

    That's the limitation of system test format. Unless we expect such solutions in advance, we can't prepare counter-tests for them.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      In general, yeah, but in a problem where the answer is obviously No if the xor is non-zero, you can always expect a solution that outputs Yes if the xor is 0. I read the problem, immediately wrote and submitted that, thinking "well it's such a stupid simple solution that if it's wrong, you surely prepared countertests!".

      Also, it fails even on simple tests like "$$$N$$$ even, all $$$A_i$$$ identical".

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +65 Vote: I do not like it

        Frankly speaking, when testers are strong, they miss too stupid solutions.

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

          They won't miss simple stupid solutions if they try to come up with them. The issue is they usually don't try.

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

            We try hard to avoid wrong solutions, for example this time in problem D marathon specialist chokudai wrote a marathon-like solution for D and we tried hard to break it.

            Still, sometimes solutions we never imagine can appear. Here's a quiz for you. What wrong solutions passed in this problem?

            Spoiler
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it +8 Vote: I do not like it

              You can't make too many tests, because judging will be slow. The only way to fix it is multitest. If you give 10000 test cases, such wrong solutions wouldn't pass.

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

                That can be broken using "if small test then bruteforce" in solutions, but in general, yeah, +10000 small random tests are a good idea.

              • »
                »
                »
                »
                »
                »
                »
                »
                5 years ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                Something that absurd is indeed impossible to predict but then usually it's hard to create tests that will let it pass. For example, 100 1 looks like a very important test in this problem (max/edge-test). Does it work iff K > N/2? That's really hard to avoid in 10-20 tests ;p

                Btw. the point touched by Xellos that "if small then bruteforce" is very important. Having this hack shouldn't give you AC so I don't like problems with multiple test cases and condition like "the sum of N doesn't exceed 1e6".

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

                  Having this hack shouldn't give you AC so I don't like problems with multiple test cases and condition like "the sum of N doesn't exceed 1e6"

                  But you can do the same in problems with single test case.

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

                  Nah, problems with single test case don't have thousands of small random tests.

                  I'm saying the most important tests are smart big tests. The strength of tests is roughly equal to the number of types of big tests you will create.

»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

When will the testcases be uploaded?

Link

»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Secret History: The idea of problem E is from the card game, Dominion (although the setting changed so much from original). Does someone enjoy this game and notice that?

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

    I haven't played for so long... it seems like a card effect, which one?

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

      Original one is trashing a card from hand and gain (and topdeck) the cards whose costs are exactly -1 and +1 of the cost of the trashed card. In this problem it became -2 and +K.

»
5 years ago, # |
  Vote: I like it +20 Vote: I do not like it

One of the many many instances of problem B.

»
5 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Can someone explain how Tourist's solution for D works in time? To me it looks like it will do 16! operations??

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

    Let $$$f(k)$$$ be the number of recursive calls of Go when you call Go once with $$$to - from = k$$$.

    Then $$$f(k) = 1 + 2(f(1) + ... + f(k-1))$$$ and $$$f(k) = 3^{k-1}$$$.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

From the editorial, for problem A, how do you observe that quickly?

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    May be slightly easier solution. Consider two cases: (a) the sequence begins with 2 equal numbers, (b) the sequence begins with 2 different numbers. In first case the sequence will look like: "x x 0 x x 0 ..." and in the second case it looks like "a b c a b c ...". Now the only thing is to handle the "last number = first number". But instead of that, you can observe that, "if you pick two unequal numbers from the given numbers, they will always be adjacent". So pick the largest number X and the smallest number Y (if all the numbers are equal, following solution still works). Consider them as first two numbers, and try to find all the next N — 2 numbers. Now just check if the count of the numbers in this sequence matches with the input. Also check if the last two numbers yield the first number.

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

For task A, the solution given by the editorial is $$$O(n\log n)$$$. But I solved it in only $$$O(n)$$$. And I just judged whether the XOR of all numbers is ZERO. So how to prove the sufficiency?

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

    Oh, I found it was wrong. Here is a hack data:

    4
    1 1 2 2
    

    Obviously it is impossible.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    It can be solved in $$$\mathcal O(n)$$$ though. You can simply answer No once the map has $$$4$$$ elements.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please help with this solution for problem B, could someone provide some testcase when this code wont work? Here is my submission (just one wrong answer): https://atcoder.jp/contests/agc035/submissions/6383471

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

    i visited the vertices in the order of their new degrees, pls some testcase for which my algorithm fails?

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

where I can find the editorials in english for the AtCoder Grand Contest 035?

»
5 years ago, # |
  Vote: I like it +32 Vote: I do not like it

I am not able to understand dp in editorial of E for several days. Could please anyone help me?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Me neither, couldn't figure out how to do transition concerning the last dimension of the dp state in the tutorial.

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

    This is pretty tricky to get right. Think of this that way. Every cycle of desired shape has some start and end which are of the same parity. It contains all elements with the same parity that are between them and moreover some more consecutive elements of the other parity which are symmetrical with respect to the middle of the cycle. We will "detect" such cycle just after the end of the other parity part.

    We are at some position $$$p$$$. Assume that x is the number of last positions with the same parity as $$$p$$$ that were deleted. That is $$$p, p-2, p-4, \ldots, p-2x+2$$$ were deleted, but $$$p-2x$$$ wasn't. Assume that y denotes the same but for the other parity, that is $$$p-1, p-3, \ldots, p-2y+$$$1 were deleted, but $$$p-2y-1$$$ wasn't. Assume x>y. This is the moment where we want to bound number of consecutive appearances of deleted positions for the future in order to omit the forbidden cycle. If $$$y=0$$$ then we won't get here any hypothetical cycle, so we don't have to do anything. If $$$y \ge 1$$$ and $$$2x \ge k+3$$$ then we know that if we delete next $$$\frac{k - 2y + 1}{2}$$$ elements with the same parity as $$$p$$$ then we get this forbidden cycle, so we keep $$$x + \frac{k - 2y + 1}{2}$$$ as the bound on the length of current length of consecutive deleted elements with the same parity as $$$p$$$.

    One more thing to note is that this is one bound for one parity, but what about the other parity? Maybe it has some bound on its length as well, so we should keep two bounds in state? Actually it is not necessary since we can keep the bound just for the parity that currently has longer suffix of deleted elements.

    Maybe my code can help: https://atcoder.jp/contests/agc035/submissions/6384104 but I used a bit different naming there. $$$b$$$ corresponds to $$$x$$$, $$$c$$$ to $$$y$$$, $$$d$$$ to that bound, prefix $$$prv_$$$ means it is from previous state, prefix $$$n$$$ stands for $$$\texttt{new}$$$ and stands for new value of that variable. $$$\texttt{dp[i][b][c][d]}$$$ stands for the number of states so that I considered $$$i$$$ positions, $$$x=b$$$, $$$y=c$$$ and the bound on the length of longer sequence of deleted elements is $$$d$$$ (meaning that, if it reaches $$$d$$$ then the cycle is completed, so $$$dp[i][d][c][d]=0$$$). I did this dp in "forward" manner instead of more popular "backward" manner. Ignore any ifs regarding debugs because they are successfully polluting this.

    Hope I helped.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I write a brute force for D and find out that the number of distinct ways is the $$$(n-2)^{th}$$$ Catalan number, which means it can actually be solved by brute force if we can avoid redundant states. The idea is basically if you have a b c d e, you will never eat b after d because it would yield the same result as eat b before d. My code

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

    Ok, that explains why my heuristic solution is fast enough, this is the worst case for it. It deals with much fewer states, but at least it's "much fewer than Catalan numbers" instead of "much fewer than factorial".

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

    Nonisomorphic ways of doing this process indeed correspond to binary trees with n-1 leaves, so it indeed is some Catalan number. It can be seen by marking spaces between elements and when we are removing some element we are merging two consecutive spaces.

    I noted this during competition, but somehow didn't realize that this is only 35 mlns...

»
5 years ago, # |
  Vote: I like it -27 Vote: I do not like it

rng_58 Is the data of problem A weak? I found that if you just judge if the xor of all the numbers is 0,you will get AC,but the data 1 2 4 7 is No even 1^2^4^7 is 0 :).

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't understand the editorial of problem E. In the situation where we cannot add $$$a$$$ to $$$S$$$, why $$$b$$$ must be less than $$$a$$$? And why a \not= b (mod 2)?