finnlidbetter's blog

By finnlidbetter, history, 5 years ago, In English

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

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

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

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

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

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

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

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

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

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?

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

    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.

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

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

      Pastebin

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

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

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

      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.

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

      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.

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

    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.

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

Will testcases be uploaded somewhere?

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

    The problems should hopefully be available to solve on open.kattis.com within the next day or two hopefully. Although the test data won't be public.

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

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

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

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

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

    but couldn't proceed

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

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

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

        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.

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

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

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

            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.

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

              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.

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

                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.

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

                  Can you please share your code. I don't know how to find the factors for numbers of such order.

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

                  My code is just a slight modification of the Pollard's rho implementation in KACTL, which allows one to get the prime factors of a number in $$$O(n^{\frac{1}{4}}).$$$

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

              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.

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

              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?

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

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

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

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

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

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

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

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

How was it supposed to be calculated?

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

    Apply Dilworth's theorem.

    Take care to ignore nontrivial SCCs and any descendants.

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

      Can you share your code for this problem?

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

      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

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

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

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +42 Vote: I do not like it
    Spoiler
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      We need to do topological sort on those components right?

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

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

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

          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.

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

            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.

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

            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.

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

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

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

    I wonder what the bitset solution is?

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

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

What is the idea for K?

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

    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
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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