finnlidbetter's blog

By finnlidbetter, history, 2 months 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

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

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

»
2 months 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

»
2 months 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?

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

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

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

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

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

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

»
2 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Will testcases be uploaded somewhere?

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

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

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

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

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

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

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

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

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 weeks 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 weeks 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}}).$$$

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

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

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months ago, # ^ |
                Rev. 2   Vote: I like it +11 Vote: I do not like it
                Spoiler
        • »
          »
          »
          »
          »
          2 months 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$$$

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

»
2 months ago, # |
  Vote: I like it +13 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +38 Vote: I do not like it
    Spoiler
»
2 months 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?

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

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

      Can you share your code for this problem?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it
        Spoiler
    • »
      »
      »
      6 weeks 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

»
2 months 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})$$$?

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

      We need to do topological sort on those components right?

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

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

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

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

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

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

»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

What is the idea for K?

  • »
    »
    5 weeks 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 weeks 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).