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

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

You are invited to participate in MAPS 2020 (Mount Allison Programming Showdown 2020) on Saturday March 28th 16:00 UTC. MAPS is an open, online, ICPC-style programming competition hosted on Kattis. The following site contains all of the relevant information about the contest: https://mapscontest.com/.

It is a 5 hour competition with 11-12 problems. The MAPS problem set has been put together so that it will (hopefully) both challenge reasonably strong teams and be accessible to newer competitors. The difficulty range of the problem set is expected to be similar to that of the North American Qualifier, if you are familiar with that contest. We hope that you will participate! Registration is available at https://maps20.kattis.com/.

EDIT: Feel free to discuss the problems here after the contest is over!

UPDATE: The problems are now available here on open Kattis https://open.kattis.com/problem-sources/Mount%20Allison%20Programming%20Showdown%20%28MAPS%202020%29

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

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

Last year's contest standings and problems are available at https://maps19.kattis.com.

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

Auto comment: topic has been updated by finnlidbetter (previous revision, new revision, compare).

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

The contest is just over 3 hours away! Registration is still open at https://maps20.kattis.com

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

For C I did some BFS when the max bit was small and FFT + binary search when the max bit was large ... Is there a better way?

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

    Create a graph of $$$m$$$ nodes: Add edge $$$X \to X+1 \mod m$$$ with cost $$$1$$$ and $$$X \to 2X \mod m$$$ with cost $$$0$$$. Then the smallest number of $$$1$$$ in any multiple of $$$m$$$ is the shortest path from node $$$1$$$ to node $$$0$$$ in the graph. To construct the smallest multiple with that many 1s, you'll need to BFS again on the shortest path's DAG generated by previous BFS.

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

      If anyone is curious to see a solution following this methodology, I am posting mine below in a Pastebin link!

      Pastebin

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

    What is your FFT solution? We were wondering why is the TL 7 seconds..

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

      The 7 seconds wasn't necessarily to allow any particularly slow running solution and in hindsight, perhaps the time limit should have been tighter to possibly prevent, or at least further discourage, Benq's approach. On Kattis time limits are calculated using a multiplier on the slowest running AC submission provided in the problem package. Perhaps this multiplier was too high and I should have paid more attention to this.

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

      Given two sets $$$A,B$$$ of remainders modulo $$$m$$$ you can compute $$$[a+b|a\in A,b\in B]$$$ with FFT. If you know the optimal number of bits, you can binary search to find the smallest $$$k$$$ such that the answer is less than $$$2^k$$$. This gives you one bit of the answer, now repeat.

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

    Yes, that was an unexpected solution. Here's a paper with several algorithms for solving this problem: https://arxiv.org/abs/2002.02731

    Rezwan.Arefin01's suggestion is essentially one of them.

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

Will testcases be uploaded somewhere?

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

How to solve B? I thought you should be able to factor $$$d-1$$$ and check each factor as $$$m$$$, but this gets WA.

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

    I realized we just had to check if there exists such m, for which

    $$$b^m mod (d) = d-1$$$

    but couldn't proceed

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

      Yes, this is true. My observation was that if

      $$$b^m \equiv d-1 \equiv -1 \pmod d$$$

      then

      $$$b^{2m} \equiv 1 \pmod d.$$$

      Since $d$ is prime, we know by Fermat's Little Theorem that $$$a^d \equiv a \pmod d$$$ for arbitrary integer $$$a$$$, and further if $$$a$$$ and $$$d$$$ are coprime that $$$a^{d-1} \equiv 1 \pmod d$$$. So if an $$$m$$$ which satisfies the divisibility hack exists, then $$$2m$$$ should be a factor of $$$d-1$$$, and by extension $$$m$$$ should be a factor of $$$d-1$$$. Maybe there's a hole in my logic...

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

        The problem is that your argument works in one direction, but not the other. Since $$$d-1$$$ is not the only solution to $$$x^2 \equiv 1 \pmod d$$$, you can't assume that a solution to the second equation is a solution to the first.

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

          I don’t quite follow. My argument is not that any factor of $$$d-1$$$ will do, but that if a solution exists, then it will be a factor of $$$d-1$$$.

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

            A small counter example is $$$d=5$$$, $$$b \equiv 4 \equiv -1 \pmod d$$$ and $$$m=3$$$. Then $$$(-1)^3 \equiv -1 \pmod d$$$ and $$$(-1)^6 \equiv 1 \pmod d$$$ but $$$3$$$ nor $$$2 \cdot 3$$$ does not divide 4.

            The conclusion that both $$$p-1$$$ and $$$2m$$$ are divisible by the order of $$$b$$$ modulo $$$p$$$ (minimal $$$e \geq 1$$$ such that $$$b^e \equiv 1 \pmod d$$$) is true though.

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

              Well, $$$m = 1$$$ works here, which is a divisor of $$$4$$$. So maybe: if there are some solutions, there is a solution with $$$m \mid d-1$$$. Can you prove or disprove this? We got AC with this though.

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

                Hmm.. regardless of the theory, it has become clear that I have a bug in my code considering that you got AC :P

                EDIT: found the bug, it was in my modular multiplication implementation, can confirm that the solution works.

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

              Oh well. If $$$m$$$ satisfies, so does $$$d - 1 - m$$$. So, if there are some solutions, one of them has $$$2m \leq d - 1$$$. So, taking the divisors of $$$d - 1$$$ is enough.
              Simply speaking: because of taking square root of both sides, we can possibly get two roots, each of which will lead to a solution if exists.

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

              Well, of course, thanks! So it seems the fault in my logic was to say that

              $$$a^{d-1} \equiv 1 \pmod d \text{ and } a^{2m} \equiv 1 \pmod d \Rightarrow 2m \mid d-1.$$$

              Though for other reasons it seems like the following conclusion does hold:

              $$$\text{if a solution exists, then one of the factors of } d-1 \text{ is a solution.}$$$

              Looking at the code Benq posted in another comment seems to support this, and in fact if I'm not mistaken supports the even stronger conclusion that if a solution exists then a solution of the form

              $$$\frac{d-1}{2^i}$$$

              for some i>0 exists, though I haven't studied modular arithmetic before and will need to continue thinking for a bit about why this should be true... is it obvious?

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

          Probably something like if $$$k$$$ is the smallest number such that $$$a^k \equiv 1 \pmod d$$$, then $$$k$$$ divides $$$d - 1$$$ but there might exist some $$$x = a \cdot k$$$, that does not divide $$$d-1$$$

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

    You probably had some mistake in the implementation. We got AC doing exactly this.

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

Can B be solved without a fast factoring method (eg. Pollard rho)?

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

For problem L, was the answer the maximum width (maximum parallelism) in a DAG.

How was it supposed to be calculated?

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

    Apply Dilworth's theorem.

    Take care to ignore nontrivial SCCs and any descendants.

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

      Can you share your code for this problem?

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

      By nontrivial SCCs you mean the ones which have more than 1 element right? I tried it but I don't know I keep getting wrong answer: code

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

Is there a better way to solve problem I than SCC decomposition and then use bitset in $$$O(\frac{nm}{64})$$$?

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

      We need to do topological sort on those components right?

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

        Yes, you need to perform a top sort on the compressed SCC DAG.

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

          I think we don't have to perform the topological sort. Since the meaning of the summation is actually counting no. of unordered pairs $$$(u, v)$$$ such that $$$scc(u)\neq scc(v)$$$, so the node order is irrelevant. We want to add edges between those pairs but we don't have to know its direction, so topological sort is not necessary.

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

            That's absolutely correct, my mistake. I still think that it's easier to think about in terms of the topological sort when developing the solution, however.

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

            Is it true, then, that the answer is the same regardless of whether or not we leave the edges on the graph as we add them?

            EDIT: I think this is equivalent to asking if it's true that if we add an edge (u,v) between all components u, v s.t. scc(u) != scc(v), can we direct the edges so that no cycles are formed? And, if I'm not mistaken, the answer is yes: just direct them in order of low to high DFS finish time.

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

          Kosaraju's algorithm finds SCC's in reverse topological order. No need to run an additional toposort.

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

    I wonder what the bitset solution is?

    Ulna's solution was the obvious solution that came to my mind.

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

What is the idea for K?

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

    Let dp[i][j] be the answer for the possibly circular subsection [i, ..., j], where the line segment (i,j) has already existed/been created.

    Then, dp[i][j] = 0 for j=(i+1)%n or j=(i+2)%n. Also, we can calculate dp[i][j] in general by considering all possible points in the subsection [i+1, ...., j-1] and taking the minimum possible answer if we decided to use this triangle (i, k, j) in our final construction. Then, that leaves two subproblems, dp[i][k] and dp[k][j] to solve.

    The above can be written as:

    dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]+dist(i,k)+dist(k,j)),
    

    where dist(a, b) is 0 if the line segment (a,b) is a side of the polygon, infinity if (a, b) a strut that intersects the polygon, and normal squared distance otherwise.

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

Auto comment: topic has been updated by finnlidbetter (previous revision, new revision, compare).