rng_58's blog

By rng_58, history, 5 years ago, In English

We will hold M-SOLUTIONS Programming Contest.

The point values will be announced later.

We are looking forward to your participation!

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

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

    I used this formula answ = x * d^(n — 1) * f( d / x , n — 1 ), where f(x,y) = fact(x + y) / fact(x — 1).

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

    First handle the $$$D=0$$$ corner case. Now we know that if $$$N \geq mod$$$, answer is $$$0$$$.

    Let's look at $$$x * (x + d) * (x + 2d) * ... * (x + (n - 1) * d)$$$. We will get $$$d$$$ out of every bracket and get $$$d^n * \frac{x}{d} * (\frac{x}{d} + 1) * (\frac{x}{d} + 2) * ... * (\frac{x}{d} + n - 1)$$$. This is basically a product of consecutive numbers when having them moded.

    To find this product fast, we can build a segment tree for products on {1, 2, 3, 4, ..., 2 * mod}. Another way is to do suffix and prefix products.

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

      ok ! but what about x/d , it can be in fraction. what u did for it ?

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

        $$$\frac{x}{d}=x * d^{-1} = x * d ^ {mod - 2}$$$

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

          radoslav11 Why upto 2*mod building for segment tree.

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

            x/d + n — 1 can be more than mod.

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

              Answer is zero when $$$ \dfrac{x}{d} + n - 1 \geq MOD $$$.

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

                Why . Does it because there will be a number which will be a multiple of mod? How

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

                  Let $$$k = \dfrac{x}{d} \pmod{MOD}$$$. Note that $$$k \lt MOD$$$. The answer reduces to
                  $$$d^n \cdot \left( k \cdot (k + 1) \cdots (k + n - 1) \right) \pmod{MOD}$$$.

                  Now if $$$k + n - 1 \ge MOD$$$, it is clear that one product term is equal to $$$MOD$$$

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

What's with the difficulty distribution? A,B,D are trivial, F was pretty hard, and C,E are impossible :/

I liked F a lot though. My solution is $$$O(n^{3} / 64)$$$ with bitsets:

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

    I think pC is a common problem in probability textbooks, so it may be easy for some people.

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

      How you solved.

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

        consider the case when $$$c = 0$$$

        then you can calculate the expectation of A wins the game in i steps for $$$i$$$ = $$$n$$$ to $$$2*n - 1$$$

        $$$E(i) = i * C(2*n-1,i) * p_a^n * p_b^i$$$

        and do the same thing with B

        Finally consider the C value by multiply $$$\frac{100}{100-c}$$$ to the expectation

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

    mango_lassi wow, amazing solution.

    mango lassi solution
»
5 years ago, # |
  Vote: I like it +42 Vote: I do not like it

Does the "M" stand for "Math"?

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

How to solve C?

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

    And, what is "the expected number of games". Number of games with a possibilitie of min 0.5 of reaching n? And, how can "the expected number of games" be a fraction?

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

    We can reduce the problem to one with $$$C = 0$$$. Just normalize $$$A$$$ and $$$B$$$, so that $$$A + B = 1$$$, and multiply the answer by $$$\frac{1}{1 - C}$$$.

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

    I will denote by $$$a$$$, $$$b$$$ and $$$c$$$ the probabilities and not the percentages.

    First find the expected number of turns to have a non-draw outcome. It is equal to $$$\frac{1}{1-c}$$$ and I will denote it as $$$d$$$.

    Now let's fix the number of wins of the first player, assuming the second will win. Let this number be $$$x$$$. Then we choose which of the games will be wins for the first player. This means we will have to add to the answer: $$$d * (n + x) * \binom{n + x - 1}{x} * (\frac{a}{a + b})^x * (\frac{b}{a + b})^n$$$.

    We do the same if the first player wins.

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

How to solve D?

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

    Consider a straight tree like 1-2-3-4-5. We can notice that we have to assign ci values in increasing/decreasing order to attain the maximum value. The same thing applies to any tree. Considering 1 as the root and every path from 1 to a leaf node should be in decreasing order to attain the maximum value where our maximum value is the sum of all c[i]'s except the largest value. This is equivalent to every node in subtree should be less than or equal to the root node of the subtree. Sort all the subtrees by their sizes and assign them the values in increasing order of c[i]'s.

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

      Thanks aarcee.

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

      I used dfs starting from the index having maximum size of subtree. And kept assigning them c[i]'s in decreasing order. i.e. the root gets a higher value of c[i] than any of its children. But I got WA. This is my submission . What is the problem with my code(logic).

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

        You are sorting by the degree of each vertex instead of sorting it by the size of subtree.

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

F was very similar to the D1 1000 from the last TopCoder round.

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

    Yes, it's very similar. I haven't checked this TC task, sorry...

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

Am I correct that in C's editorial 1 is added as because Y(m) = c*(1 + Y(m)) + (1-c)*(1 + Y(m-1))?