rng_58's blog

AtCoder Regular Contest 106 Announcement
By rng_58, history, 4 years ago, In English

We will hold AtCoder Regular Contest 106.

We are looking forward to your participation!

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

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

Bump. ARC soon, fellow S.T.A.L.K.E.R. (Oh really, when? Now.)

Come play if you're a pleb like me and it's still rated for you.

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

I wish the word positive was in bold in problem A :)

How do you solve D? Is there some nice result that comes straight from binomial expansion, or do I have to do some fancy math?

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

    https://atcoder.jp/contests/arc106/submissions/17633994

    Depends on your definition of fancy, but I think both are needed.

    Solution: Swapping the order of summation, we first rewrite the sum as

    $$$ \sum\limits_{i=0}^x \binom{x}{i} \sum\limits_{1\le L<R\le N} A_L^i A_R^{X-i}$$$

    Now observe $$$\binom{x}{i}=\binom{x}{x-i}$$$ and

    $$$\sum\limits_{1\le L<R\le N} A_L^i A_R^{X-i} + \sum\limits_{1\le R<L\le N} A_L^i A_R^{X-i}$$$
    $$$=\sum\limits_{1\le L,R\le N, L\ne R} A_L^i A_R^{X-i} = (\sum\limits_{L=0}^{N-1} A_L^i)(\sum\limits_{R=0}^{N-1} A_R^{X-i})-\sum\limits_{i=0}^{N-1} A_i^X$$$

    For each

    $$$1\le i\le K,$$$

    we precompute

    $$$\sum\limits_{L=0}^{N-1} A_L^i $$$

    in $O(NK)$ and do the final computation in $$$O(K^2)$$$.

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

      Consider using $$$\sum\limits_{i=1}^{k} something$$$ notation.

      \sum\limits_{i=1}^{k} something

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

      sorry for silly question but i didn't understand the optimization can you please elaborate more or provide particular resource to learn this types of mathematics?

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

        Here the topic is not related but you will have some idea on how to reduce this type of things.

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

        \begin{equation} \sum^N_{i=1}\sum^N_{j=i+1} (A_i+A_j)^X \end{equation} \begin{equation} =\frac{1}{2}\left(\sum^N_{i=1}\sum^N_{j=1} (A_i+A_j)^X — \sum_{i=1}^N(2A_i)^X\right) \end{equation} \begin{equation} =\frac{1}{2}\left(\sum^N_{i=1}\sum^N_{j=1} \sum^X_{p=0}\binom{X}{p}A_i^{X-p}A_j^p — \sum_{i=1}^N(2A_i)^X\right) \end{equation} \begin{equation} =\frac{1}{2}\left(\sum^X_{p=0}\binom{X}{p}\sum^N_{i=1}A_i^{X-p}\sum^N_{j=1} A_j^p — \sum_{i=1}^N(2A_i)^X\right) \end{equation} If you pre-compute $$$\sum^N_{i=1} A_i^p$$$ and $$$\sum_{i=1}^N(2A_i)^X$$$ you can answer for each X in O(K). So the overall complexity of the final computation is O($$$K^2$$$).

        Submission

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

          thanks one last question we can separate the order of summation if i and j are both independent of each other?

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

            $$$\sum_{i=1}^N\sum_{j=1}^NA_iB_j=\left(A_1+A_2+....A_N\right)\left(B_1+B_2+....B_N\right)=\sum_{i=1}^NA_i\sum_{j=1}^NB_j$$$

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

    Check this out https://www.geeksforgeeks.org/sum-of-absolute-difference-of-all-pairs-raised-to-power-k/ . Although its not exactly the same question, but by tweaking according to the constraints , you would get it .And yes, Binomial expansion :)

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

    Can you please share your approach for C

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

      The only difference between the two approaches would happen is when one interval completely overlaps the other, as in $$$L_1,L_2,R_2,R_1$$$. If we have one "big interval" which contains $$$x$$$ "small intervals", we can create a difference of $$$x-1$$$ (draw and check, it'll be obvious). We can only create a positive difference, and at most a difference of $$$n-2$$$. Keep in mind the test case 1 0

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

      Note $$$0\le M\le N-2$$$ are achievable:

      Consider the construction $$$(1,2(M+2)),(2i,2i+1)_{i=1}^{M+1}$$$, $$$(2i-1,2i)_{i=M+3}^N$$$

      Now I claim $$$M\ge N-1$$$ isn't. This would mean T can get $$$N$$$ intervals but A can only get 1. This is impossible since this would imply all intervals are disjoint.

      I also claim $$$M\ge 0$$$. Assume the selection of T and A differs at some point. Then T has to be better because in the interval T and A choose to be different, the interval A chooses must contain the interval T chooses, so T's strategy is strictly better than A's.

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

    only C(n,r)=C(n,n-r)is used

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

What is wrong in my code for problem A..?

https://atcoder.jp/contests/arc106/submissions/17622365

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

The curse of the testcase (1,0).

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

How to solve B?

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

    We break the graph into components. If in a connected component the sum of $$$a_i$$$s is the sum of $$$b_i$$$s, I can win by making $$$a_i=b_i$$$ one by one.

    If the sum of $$$a_i$$$ s is not the sum of $$$b_i$$$ s, the answer is negative because the sum is an invariant.

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

I think this is the first time I used Hall's theorem to successfully solve a problem.

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

    Yeah you use it to solve E, where you consider $$$f(i)=$$$ number of days worker $$$i$$$ can work, and for any subset $$$T$$$ of $$$[n]$$$, the number of days for which at least one worker in $$$T$$$ works is $$$ \ge k|T|$$$.

    So we can binary search and find the answer. Unfortunately, I thought of this for E but ran out of time.

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

      The important thing is that the answer is at most $$$2KN+\mathrm{max}(A_i)$$$, which also follows from the theorem. This means we can bruteforce the exact set of workers on each day and checking the condition for binsearch becomes just doing subset sums on that.

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

        2KN actually. After any time period T, every person will have worked at the very least T/2 time. You take all the times that at least a person in S has worked, which is at least T/2 and needs to be (according to hall) at least NK. I agree that one was the main observation, took me quite some time to get there.

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

          Very insignificant optimization, but $$$2KN-1$$$ works by the same argument.

          → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it
Unofficial editorial for F (messy; is there a more elegant solution?)
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    Here's a combinatorial solution which only uses the fact that trees can be represented as Prufer sequences where degree of a node is equal to number of occurrences plus one:

    For a given tree, consider choosing holes for each edge one by one in arbitrary order. Each time we add an edge to a node $$$i$$$ we must multiply the answer by $$$d_i - s_i$$$ where $$$s_i$$$ is the number of edges previously added to that node. All nodes have degree at least one so take $$$\prod(d_i)$$$ of the initial values first and then decrement all $$$d_i$$$ by one. This way we can simplify the problem to say that the final $$$s_i$$$ is equal to the number of occurrences of $$$i$$$ in the Prufer sequence exactly, and then multiply the original product of $$$d_i$$$ into the answer,

    Now, we claim that the sum of this value across all Prufer sequences is equal to the number of permutations of $$$(\sum(d_i))$$$ of length $$$(N-2)$$$ (remember these $$$d_i$$$ values are the decremented ones). It turns out that there's a nice bijection which shows that fact: imagine that we have balls of $$$N$$$ colors where there are $$$d_i$$$ balls of the $$$i$$$-th color. Then the Prufer sequence count is equivalent to repeatedly choosing a color, then choosing one of the balls of that color, and then removing it ($$$N-2$$$ times total). But the step of choosing a color is irrelevant, so we can just phrase it as choosing $$$N-2$$$ arbitrary balls in order from a set of $$$\sum(d_i)$$$ balls total as desired.

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

    Here is my submission using Prufer code. What I had done is:

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

    Hi... I have heard of the prufer sequences for the first time .. And it seems gr8 , Do you have any other related questions using these type of techniques ? I want to learn them this time . Thanks..

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

how to solve c

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

is there any editorial(official/unofficial) available for the contest?

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

Will an editorial be uploaded anytime soon?

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

    switch to Japanese version of atcoder and use google translator( until the official one comes out on english version.)

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

Can anyone help me with the problem B, I am getting WA in some cases.

This is my Code in Python https://atcoder.jp/contests/arc106/submissions/17717380

→ Reply