rng_58's blog

By rng_58, history, 16 months 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

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    16 months 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).

  • »
    »
    16 months 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.

    • »
      »
      »
      16 months 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 ?

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

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

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

          ok , inverse + fermat's theorem .. i get it. thanks ! :)

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

          radoslav11 Why upto 2*mod building for segment tree.

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

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

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

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

              • »
                »
                »
                »
                »
                »
                »
                »
                16 months 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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  16 months 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$$$

»
16 months 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
  • »
    »
    16 months 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.

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

      How you solved.

      • »
        »
        »
        »
        16 months 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

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

    mango_lassi wow, amazing solution.

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

Does the "M" stand for "Math"?

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

How to solve C?

  • »
    »
    16 months 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?

  • »
    »
    16 months 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}$$$.

  • »
    »
    16 months 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.

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

How to solve D?

  • »
    »
    16 months 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.

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

      Thanks aarcee.

    • »
      »
      »
      16 months 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).

      • »
        »
        »
        »
        16 months 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.

»
16 months 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.

  • »
    »
    16 months 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...

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

      no issue even though similar, many dont solve this problem earlier.

»
16 months 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))?