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
Last year's contest standings and problems are available at https://maps19.kattis.com.
Auto comment: topic has been updated by finnlidbetter (previous revision, new revision, compare).
The contest is just over 3 hours away! Registration is still open at https://maps20.kattis.com
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?
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.
If anyone is curious to see a solution following this methodology, I am posting mine below in a Pastebin link!
Pastebin
What is your FFT solution? We were wondering why is the TL 7 seconds..
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.
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.
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.
Will testcases be uploaded somewhere?
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.
How to solve B? I thought you should be able to factor $$$d-1$$$ and check each factor as $$$m$$$, but this gets WA.
I realized we just had to check if there exists such m, for which
but couldn't proceed
Yes, this is true. My observation was that if
then
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...
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.
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$$$.
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.
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.
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.
Can you please share your code. I don't know how to find the factors for numbers of such order.
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}}).$$$
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.
Well, of course, thanks! So it seems the fault in my logic was to say that
Though for other reasons it seems like the following conclusion does hold:
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
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?
Suppose that $$$d>2$$$. We know that the order of $$$a$$$ (the minimum $$$x$$$ such that $$$a^x\equiv 1\pmod{d}$$$) divides $$$d-1$$$. $$$m$$$ exists iff $$$x$$$ is even because then $$$a^{x/2}\equiv -1\pmod{d}$$$.
Let $$$d'$$$ be the largest odd factor of $$$d-1$$$. Then $$$x$$$ is odd (the answer is no) iff $$$a^{d'}\equiv 1\pmod{d}$$$.
Nice. Thanks!
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$$$
You probably had some mistake in the implementation. We got AC doing exactly this.
Can B be solved without a fast factoring method (eg. Pollard rho)?
How'd you make sure not to overflow?
I assume you're asking about not overflowing in the pow function, in which case you should learn about binary exponentiation modulo a number: https://cp-algorithms.com/algebra/binary-exp.html#toc-tgt-3
I'm familiar with that, I was asking because you still need to multiply 2 numbers than are potentially up to 2^63, which could overflow a long(java/kotlin). I got AC by using BigInteger (java/kotlin), but I was wondering if there was a better way around it besides just using a type that can store bigger numbers.
Another option is modpow here: https://github.com/kth-competitive-programming/kactl/blob/master/content/number-theory/ModMulLL.h
Use __int128.
For problem L, was the answer the maximum width (maximum parallelism) in a DAG.
How was it supposed to be calculated?
Apply Dilworth's theorem.
Take care to ignore nontrivial SCCs and any descendants.
Can you share your code for this problem?
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
Is there a better way to solve problem I than SCC decomposition and then use bitset in $$$O(\frac{nm}{64})$$$?
Let $$$m$$$ be no. of scc, $$$X$$$ be their sizes and $$$pref(i) = (X_1 + ... + X_i)$$$.
Answer = $$$\sum\limits_{i = 1}^mX_i\times pref(i - 1) -$$$ no. of edges $$$(u$$$->$$$v)$$$ such that $$$scc(u)\neq scc(v)$$$, where $$$scc(v)$$$ is the id of the scc that vertex $$$v$$$ belongs to.
We need to do topological sort on those components right?
Yes, you need to perform a top sort on the compressed SCC DAG.
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.
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.
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.
Kosaraju's algorithm finds SCC's in reverse topological order. No need to run an additional toposort.
I wonder what the bitset solution is?
Ulna's solution was the obvious solution that came to my mind.
What is the idea for K?
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
forj=(i+1)%n
orj=(i+2)%n
. Also, we can calculatedp[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]
anddp[k][j]
to solve.The above can be written as:
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.Auto comment: topic has been updated by finnlidbetter (previous revision, new revision, compare).