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

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

We will hold AtCoder Regular Contest 106.

We are looking forward to your participation!

  • Проголосовать: нравится
  • +168
  • Проголосовать: не нравится

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

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.

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

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?

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

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

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

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

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

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

      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?

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

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

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

        \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

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

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

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

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

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

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

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

    Can you please share your approach for C

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

      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

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

      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.

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

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

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

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

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

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

The curse of the testcase (1,0).

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

How to solve B?

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

    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.

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

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

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

    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.

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

      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.

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

        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.

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

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится
Unofficial editorial for F (messy; is there a more elegant solution?)
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +37 Проголосовать: не нравится

    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.

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

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

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

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

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

how to solve c

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

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

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

Will an editorial be uploaded anytime soon?

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

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