maroonrk's blog

AtCoder Grand Contest 065 Announcement
By maroonrk, history, 11 months ago, In English

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

The point values will be 500-700-900-900-1500-1600.

We are looking forward to your participation!

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

»
11 months ago, # |
  Vote: I like it +16 Vote: I do not like it

A with 500 points? Seems a tough round.

→ Reply
»
11 months ago, # |
  Vote: I like it +76 Vote: I do not like it

Thanks for the contest! ABCE are amazing, but D is just this link, which is super frustrating...

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

    Ohh damn, that explains why 2-3 very not really high rated folks solved D.

    → Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +52 Vote: I do not like it

    I'm sorry, I completely overlooked this one. Actually, the intended solution does not involve this interpretation and I thought it wasn't known. I'll try to be more careful when setting a problem like this.

    Anyway, thanks for participating in the contest and I'm glad you liked other problems.

    → Reply
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +50 Vote: I do not like it

      Thanks for yet another great round!

      Assuming the intended solution in the one from the editorial, why is this problem only worth 900 points? It would seem closer in difficulty to E and F than to C with that solution :)

      → Reply
      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +28 Vote: I do not like it

        Actually, the latter half of the intended solution (after the "it can be rephrased as follows:" line in the editorial) is a famous problem. For example, I can remember the same technique was used in the problem A in the Stage 7 of the UCUP this season. Therefore I thought it would not be as hard as E and F.

        In addition, testers solved the problem without great difficulty. They said it wouldn't be hard for those who are familiar with formal power series, and C and D were of a similar difficulty. This is how we chose the score of 900.

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

        I'd also say it's not very hard for people familiar with formal power series, though I used a completely different approach from the editorial. Describing the answer using coefficients of closed form is straightforward with only difficulty coming from algebraic mistakes, expanding that into series is a bit trickier since you can choose to expand in an ugly way, but you can try multiple things there.

        Basically if the OGF of choosing $$$m$$$ segments inside a slice containing $$$n$$$ unused points (the segment that would cut off this slice can't be chosen) is $$$f(x,y) [x^m y^n]$$$, then the answer is $$$f^2(x,y) [x^{N-2} y^{M-1}] \frac{N}{2M}$$$. A bit of combinatorics gives

        $$$f = 1 + y(1+x) f + xy(1+x) f^2$$$
        $$$f = \frac{(1-y-xy) - \sqrt{(1-y-xy)^2 - 4xy(1+x)}}{2xy(1+x)}$$$
        $$$f^2 = \frac{(1-y-xy)^2 - 2xy(1+x) - (1-y-xy)\sqrt{(1-y-xy)^2 - 4xy(1+x)}}{2x^2y^2(1+x)^2}$$$

        and the square root can be expanded using Taylor series for square root. This is where things can get ugly, but it gets much nicer if we take $z = y(1+x)$ and bring $$$1-z$$$ outside the square root before expanding $$$\sqrt{1-4xz/(1-z)^2}$$$:

        $$$f^2 = \sum_{k \ge 1} \frac{(2k-1)!!}{2^k (k+1)!} 2^{2k} (xz)^{k-1} (1-z)^{-2k} = \sum_{k \ge 1} \frac{(2k)!}{k!(k+1)!} (xz)^{k-1} \sum_{j \ge 0} {2k-1+j \choose j} z^j$$$

        Then we take just the terms containing $z^{N-2}$, expand $$$(1+x)^{N-2}$$$ in them to pick the right coefficients for $$$x^{M-1}$$$ in total and we're done. It's work but doesn't require a stroke of genius, I think I could've switched solving C for D and gotten around the same result.

        → Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Did anyone manage to solve D in-contest without referring to external resources? If so, did you do it in a simpler way than the editorial?

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

      I didn't attend the contest. However, if we write down the generating function $$$F(x,y)=\sum\limits_{n,m}f(n,m)x^ny^m$$$ we can get that $$$F$$$ is the root of some quadratic polynomial. By solving this directly and expanding the square root with another power series we may get the same sum of binomial coefficients as in the tutorial.

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

        Would you mind sharing a full derivation? I got

        $$$F^2 * b + (a + ab - 1) * F + (a + ab) = 0,$$$

        where the answer is

        $$$[a^{N-1}b^M]F=[a^{N-1}b^M]\frac{1 - a - ab - \sqrt{1 + a (b + 1) (a(b + 1) - 4b - 2)}}{2b}.$$$

        But when I tried expanding the square root I ended up with a quadratic rather than a linear number of terms. I'm getting the correct answers for small $N$ and $$$M$$$ so it must be equivalent to the editorial somehow ...

        UPDATE: It works out if you rewrite the square root as

        $$$(1-c)\sqrt{1-\frac{4bc}{(1-c)^2}}$$$

        where $$$c=a(1+b)$$$, as Xellos did above.

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

      I'm not sure if it's easier, but I decided this way at the contest: Let's consider the points in the order 1,2,..., n. At each moment of time (let's say the $$$i$$$-th) we will have a set of "available" points, i.e. those that have a number less than $$$i$$$, and we can draw an edge from $$$i$$$ into them. Then adding a point first deactivates some points, and then it becomes active itself. Let's draw a closing bracket for deactivation, and an opening bracket for activation.

      Let's say that when adding a point, we drew an edge into the $$$j$$$-th ($$$j<i$$$), and $$$j$$$ is the minimal such number. Then all points between i and j will be deactivated regardless of the edges between them. That is, in terms of the generating function, the closing bracket multiplies by $$$(1+x)$$$, and sometimes we also need to multiply by $$$x$$$ if we deactivate at least 1 vertex, in the opposite case by $$$(1+x)$$$. If you calculate everything carefully, you get a sum of type $$$C_px^a(1+x)^b$$$, where $$$C_p$$$ is the number of parenthesis sequences with $$$p$$$ pairs of adjacent opening brackets, which can be calculated explicitely, and $$$a,b$$$ depends on $$$p$$$. So $$$m$$$-th coefficient is just the sum of linear size.

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

        To calculate $$$C_p$$$, do you need to use the same method as the editorial uses to compute $$$G_k$$$?

        → Reply
»
11 months ago, # |
  Vote: I like it +36 Vote: I do not like it

Problem D

→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +57 Vote: I do not like it

    I'm sorry again. Of course I checked OEIS before setting the problem, but this sequence didn't show up when I made a search.

    The trick is that the OEIS table only contains values for $$$M \leq N$$$ and that deceived me. I need to study how to use OEIS...

    → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone solved A differently than editorial?

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain problem A's construction for c = c' — 1 please? I couldn't understand the editorial for this case's construction!

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

    The thing is we will first look at the set of elements which have max. frequency , if there is only one element which has max. frequency then it can be placed at both ends acheiving c * k as the answer. if there are more than one such elements( we will represent them by v) then say x is minimum of them and y is max. then using c , the max. possible is x — y + c * k . However we may achieve a better answer by trying to adjust first and last elements but by making c' = c — 1. At c' we can make leftmost element as v[i] and rightmost as v[i+1] achieving answer as v[i+1] — v[i] + k * c'.

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

      For the array A = (8,5,2,2,4,4), c = 4.

      Now for c'= 3, isn't this the best construction? (5,4,2,4,2,8). This is not among the v[i+1]-v[i] cases you mentioned at the last right?

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

        you can do more better for c' = 3 , (4, 2 , 5 , 4, 2 , 8). But the thing is in this case c = 4 is the best we can , in the cases where c = max. is not the best it can be shown v[i+1]-v[i] thing yields the best answer.

        → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain their solution for A? I find the editorial a bit hard to understand.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

There seems to be a clerical error in E's editorial.

In the case of x<z<y, maybe the last formula should be reverse(y+1,n,1,3,1,2).

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

    And in F's Editorial, the subscript of second formula of [2] should be k.

    → Reply