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

Автор hmehta, история, 5 лет назад, По-английски

Hey All!

Topcoder SRM 772 is scheduled to start at 07:00 UTC -5, Dec 11, 2019. Registration is now open in the Web Arena or Applet and will close 5 minutes before the match begins.

Thanks to abdullahkool768 and vivek1998299 for writing the problems for the round. Also thanks to misof and adamant for coordinating and testing the round.

This is the fifth SRM of Stage 1 of TCO20 Algorithm Tournament.

Stage 1 TCO20 Points Leaderboard | Topcoder Java Applet | Next SRM 773 — Dec 21, 12:00 UTC-5

Some Important Links

Match Results (To access match results, rating changes, challenges, failure test cases)
Problem Archive (Top access previous problems with their categories and success rates)
Problem Writing (To access everything related to problem writing at Topcoder)
Algorithm Rankings (To access Algorithm Rankings)
Editorials (To access recent Editorials)

Good luck to everyone!

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

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

Either the time-and-date link is wrong, or it doesn't start in 4 hours ^^

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

hmehta was the time changed? I am pretty sure It was 21:30PM IST for me when I saw it earlier.

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

500 is a really nice problem!

I expect somebody to say "Oh, it was in Polish subregional in Chrząszczyżewoszyce in 2012, it's such a standard trick". For me, it was fresh.

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

Great, can't even solve 250... The combinatorial formula seems obvious, but how to compute it fast since M is non-prime??

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

    you can simplify it to get answer as a product of contiguous integers which can be computed using segment tree or any data structure.

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

    The answer is $$$\left[X \cdot (X-1) \cdot \dots \cdot (X-K+1)\right] \cdot (N-K)!$$$. You can compute the first term using Fenwick tree with multiplication modulo $$$M$$$.

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

      How can we use Fenwick tree to calculate the first term? Won't we need to calculate multiplicative inverse in that case?

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

        Observe how you calculate such a product with a segment tree. In each node, you either

        • return the value stored in the node if its interval is subset of the query,
        • return zero element if its interval is disjoint with query, or
        • recurse into both children and combine the result

        You can do the same with bitwise magic in a Fenwick tree.

        I don't have that in my codebook, so I simply used a (slightly slower) segment tree with multiplication over a finite field:

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

      Even a slightly easier option is to use sqrt-decomposition. You need to add 4 lines of code to the loop computing the result.

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

Really nice round! For Div1 all three were nice problems, especially for Div1 500 — it was so moving when I have come up with the solution. Definitely one of the best problems of this year!

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

    thank you a lot!! When I thought of this problem, the first solution which came to my mind was using max flow, then when I observed the flow carefully I realized that it could be done using greedy strategy.

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

1000:

The terms you need to sum have the form $$$\frac{N!}{R! (N-R)!} \cdot \frac{1}{R + Q} \cdot P(R)$$$, summed from R = 0 to N.

The $$$R+Q$$$ term is annoying, but if we absorb it into the $$$R!$$$ term, we can rewrite this as $$$\frac{N! (R+1)\dots(R+Q-1)}{(R+Q)!(N-R)!} P(R)$$$, which can be seen as $$$\binom{N+Q}{R+Q}$$$ times some new polynomial in R, $$$P_2$$$. Polynomial $$$P_2$$$ has small degree as K and Q are small.

Now this can be computed by the binomial theorem: $$$\sum_{i=0}^{A} \binom{A}{i} (i)(i-1)\dots(i-k+1) = A(A-1)\dots(A-k+1)\sum_{i=0}^{A-k} \binom{A-k}{i} = A(A-1)\dots(A-k+1)2^{A-k}$$$. It's left to represent $$$P_2$$$ as a sum of polynomials of the form $$$x(x-1)\dots(x-k)$$$, where k ranges between [Q-1, Q+K-1].

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

    We can also kinda get rid of the annoying $$$R+Q$$$ by getting rid of everything else instead. Just write $$$R = (R+Q)-Q$$$, $$$R+P = (R+Q)+(P-Q)$$$ and expand using the binomial theorem, which leaves us with $$$\sum_{-1 \le k \le K} \sum_R {N \choose R} (R+Q)^k A_k$$$. The terms with non-negative $$$k$$$ can again be expanded and $$$S_{N, k} = \sum_R {N\choose R} R^k$$$ can be rewritten as e.g. matrix exponentiation.

    Then we need to compute $$$\sum_R {N\choose R} \frac{1}{R+Q}$$$, which seems to have a reasonably nice closed form (says WolframAlpha for small $$$Q$$$).

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

      What's the closed form? (To me, computing this sum is the hard part of the problem.)

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

        The answer to that can be obtained by integrating x^(Q-1)*(1+x)^N under limits 0 to 1 which can be done using dp in O(Q) time. :)

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

        for Q=4, the denominator is clear and the numerator is 2^n * poly(n) + constant...

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

          Sure, but what's the polynomial, if you say there's a closed form? Even if you have an expression for the polynomial, it has degree Q, and doesn't necessarily follow that you can easily evaluate in O(Q) time instead of O(Q^2).

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

            I said seems to have, it looks nice enough that it could have one. Maybe it doesn't.

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

            Actually when $$$Q$$$ is fixed it is P-recursive of order $$$2$$$ and degree $$$1$$$, so the values for $$$N = 0, ..., Q$$$ can be computed in time $$$O(Q)$$$.

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

        My thoughts without Wolfram Alpha: consider the polynomial f(x)=sum(c(n,r)*x^(r+q)/(r+q)). We need to find f(1). f'(x)=sum(c(n,r)*x^(r+q-1))=x^(q-1)*(1+x)^n. Now we need to find the integral of that, which we can do by integrating by parts q-1 times. The formula will thus have q terms with some powers of two and partial factorials.

        Didn't manage to code this in time, though :)

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

          Good idea. It's indefinite $$$\int (x+c)^a (x+d)^b = \sum_{k=0}^b \frac{(-1)^k (x+c)^{a+1+k} (x+d)^{b-k} a! b!}{(a+1+k)!(b-k)!}$$$, so

          $$$\sum_r {N \choose r} \frac{1}{r+Q} = \sum_{k=0}^{Q-1} \frac{(-1)^k 2^{N+1+k} N! (Q-1)!}{(N+1+k)!(Q-1-k)!} + \frac{(-1)^Q N! (Q-1)!}{(N+Q)!}$$$

          and then, $$$\sum_r {N \choose r} r^a$$$ can be computed as $$$\sum_r {N \choose r} r^a e^{rx}$$$ at $$$x=0$$$, which is the $$$a$$$-th derivative of $$$\sum_r {N \choose r} e^{rx} = (1 + e^x)^N = (1 + \sum_{k \ge 0} \frac{x^k}{k!})^N$$$, which is $$$a!$$$ times the coefficient at $$$x^a$$$ of this sum. Since $$$a$$$ is $$$O(K)$$$ here, this can be found easily with fast exponentiation.

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

            Can you explain how do you calculate $$$a$$$ th derivative of $$$(1+e^x)^N$$$ .

            I couldn't understand this part: "which is $$$a!$$$ times the coefficient at $$$x^a$$$ of this sum. Since $$$a$$$ is $$$O(K)$$$ here, this can be found easily with fast exponentiation.".

            Edit: Got it. Nice approach :)

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

        Here goes my ugly solution (which I completed in during the challenge phase :(

        $$$\sum_{r=0}^N \binom{N}{r} r^k = 2^N f_k(N)$$$ where $$$f_k$$$ is a polynomial of degree around $$$k$$$.

        $$$\sum_{r=0}^N \binom{N}{r} \frac{1}{r+Q} = \frac{(Q-1)!}{(N+1)\cdots(N+Q)} (2^N g_Q(N) + (-1)^Q)$$$ where $$$g_Q$$$ is a polynomial of degree around $$$Q$$$. I found this by looking at the sequence, making them integers, and using OEIS...

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

    You need to compute sums of the form

    $$$\sum_{i=0}^{N+Q}\binom{N+Q}{i}(i-1)(i-2)\ldots (i-k)$$$

    for $$$Q-1\le k\le Q-1+K,$$$ but it isn't immediately obvious how your explanation above addresses this. It took me a while to realize that this sum can be easily computed given

    $$$\sum_{i=0}^{N+Q}\binom{N+Q}{i}i(i-1)(i-2)\ldots (i-k)$$$

    and

    $$$\sum_{i=0}^{N+Q}\binom{N+Q}{i}(i-1)(i-2)\ldots (i-k+1)$$$

    ...

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

How to solve div1 — 500 ?

I can only solve the specific case which all the points are arranged in a line. It can be solved with a greedy algorithm, taking the points one by one from the two sides of the line to the "outside set".

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

    When you move a point from outside to inside, the variable "inside" increases by the sum of its distances to all inside points and the variable "outside" decreases by the sum of its distances to all outside points. That means inside-outside increases by the sum of its distances to all points. We need to find these sums, sort them and add the points in that order.

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

Maybe this is a very bad question, but how can I view the contest problems? The UI seems confusing to me.

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

I liked the problems in Div 2 very much (especially 500 was very cool). Looking forward for the editorial!

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

ETA of problems in practice room?

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

Is this SRM unrated? It disappeared from Contest Arena

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

    They added this SRM at wrong place in practice.
    Practice Room -> Tournament -> SRM 772 instead of usual Practice Room -> SRM -> SRM 772.

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

When editorials will be released?