finnlidbetter's blog

By finnlidbetter, history, 2 months ago, ,

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

 » 2 months ago, # |   +13 Last year's contest standings and problems are available at https://maps19.kattis.com.
 » 2 months ago, # |   0 Auto comment: topic has been updated by finnlidbetter (previous revision, new revision, compare).
 » 2 months ago, # |   0 The contest is just over 3 hours away! Registration is still open at https://maps20.kattis.com
 » 2 months ago, # |   +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?
•  » » 2 months ago, # ^ |   +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.
•  » » » 2 months ago, # ^ |   0 If anyone is curious to see a solution following this methodology, I am posting mine below in a Pastebin link!
•  » » 2 months ago, # ^ |   0 What is your FFT solution? We were wondering why is the TL 7 seconds..
•  » » » 2 months ago, # ^ |   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.
•  » » » 2 months ago, # ^ | ← 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.
•  » » 2 months ago, # ^ | ← 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.02731Rezwan.Arefin01's suggestion is essentially one of them.
 » 2 months ago, # |   +13 Will testcases be uploaded somewhere?
•  » » 2 months ago, # ^ |   0 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, # |   +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.
•  » » 2 months ago, # ^ | ← 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
•  » » » 2 months ago, # ^ |   +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...
•  » » » » 2 months ago, # ^ |   -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.
•  » » » » » 2 months ago, # ^ |   +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$.
•  » » » » » » 2 months ago, # ^ | ← 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.
•  » » » » » » » 2 months ago, # ^ |   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.
•  » » » » » » » » 2 months ago, # ^ | ← 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 :PEDIT: found the bug, it was in my modular multiplication implementation, can confirm that the solution works.
•  » » » » » » » » » 6 weeks ago, # ^ |   0 Can you please share your code. I don't know how to find the factors for numbers of such order.
•  » » » » » » » » » 6 weeks ago, # ^ |   0 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, # ^ |   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.
•  » » » » » » » 2 months ago, # ^ |   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?
•  » » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   +11 SpoilerSuppose 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}$.
•  » » » » » » » » » 2 months ago, # ^ |   0 Nice. Thanks!
•  » » » » » 2 months ago, # ^ | ← 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$
•  » » 2 months ago, # ^ |   +13 You probably had some mistake in the implementation. We got AC doing exactly this.
 » 2 months ago, # |   +13 Can B be solved without a fast factoring method (eg. Pollard rho)?
•  » » 2 months ago, # ^ |   +38 Spoilerint main() { setIO(); ll b, d; cin >> b >> d; MOD = d; if (b%d == 0) { ps("no"); exit(0); } if (d == 2) { ps("yes"); exit(0); } ll order = d-1; while (order%2 == 0 && pow(mi(b),order/2) == 1) order /= 2; if (order%2 == 0) ps("yes"); else ps("no"); } 
•  » » » 2 months ago, # ^ |   0 How'd you make sure not to overflow?
•  » » » » 2 months ago, # ^ |   0 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
•  » » » » » 2 months ago, # ^ |   0 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.
•  » » » » » » 2 months ago, # ^ |   +3 Another option is modpow here: https://github.com/kth-competitive-programming/kactl/blob/master/content/number-theory/ModMulLL.h
•  » » » » 2 months ago, # ^ |   +8 Use __int128.
 » 2 months ago, # |   +5 For problem L, was the answer the maximum width (maximum parallelism) in a DAG.How was it supposed to be calculated?
 » 2 months ago, # | ← Rev. 3 →   0 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 →   +42 SpoilerLet $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.
•  » » » 2 months ago, # ^ |   0 We need to do topological sort on those components right?
•  » » » » 2 months ago, # ^ |   0 Yes, you need to perform a top sort on the compressed SCC DAG.
•  » » » » » 2 months ago, # ^ |   +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.
•  » » » » » » 2 months ago, # ^ |   +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.
•  » » » » » » 2 months ago, # ^ | ← 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.
•  » » » » » 2 months ago, # ^ |   0 Kosaraju's algorithm finds SCC's in reverse topological order. No need to run an additional toposort.
•  » » 2 months ago, # ^ |   +3 I wonder what the bitset solution is?Ulna's solution was the obvious solution that came to my mind.
 » 6 weeks ago, # |   +8 What is the idea for K?
•  » » 5 weeks ago, # ^ | ← 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#include using namespace std; typedef long long ll; typedef long double ld; typedef pair pi; typedef pair pl; typedef vector vi; typedef vector vl; typedef vector vpi; typedef vector vpl; #define F0R(i,n) for (int i = 0; i < n; i++) #define FOR(i,a,b) for (int i = a; i <= b; i++) #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--) #define FORd(i,a,b) for (int i = (b); i >= (a); i--) #define trav(a, x) for (auto& a : x) #define f first #define s second #define mp make_pair #define pb push_back #define lb lower_bound #define ub upper_bound const int MAX_N = 100011; const int MX = 1<<20; const ll INF = (1LL<<50) + 123; const ll MOD = 1000000007; // 998244353 const ld PI = 4*atan((ld)1); #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() template bool ckmin(T& a, const T& b) { return a > b ? a=b, 1 : 0; } template bool ckmax(T& a, const T& b) { return b > a ? a=b, 1 : 0; } int n; template int sgn(T x) { return (x > 0) - (x < 0); } template struct Point { typedef Point P; T x, y; explicit Point(T x=0, T y=0) : x(x), y(y) {} bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); } bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); } P operator+(P p) const { return P(x+p.x, y+p.y); } P operator-(P p) const { return P(x-p.x, y-p.y); } P operator*(T d) const { return P(x*d, y*d); } P operator/(T d) const { return P(x/d, y/d); } T dot(P p) const { return x*p.x + y*p.y; } T cross(P p) const { return x*p.y - y*p.x; } T cross(P a, P b) const { return (a-*this).cross(b-*this); } T dist2() const { return x*x + y*y; } double dist() const { return sqrt((double)dist2()); } // angle to x-axis in interval [-pi, pi] ld angle() const { return atan2l(y, x); } P unit() const { return *this/dist(); } // makes dist()=1 P perp() const { return P(-y, x); } // rotates +90 degrees P normal() const { return perp().unit(); } // returns point rotated 'a' radians ccw around the origin P rotate(double a) const { return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); } friend ostream& operator<<(ostream& os, P p) { return os << "(" << p.x << "," << p.y << ")"; } }; template bool onSegment(P s, P e, P p) { return p.cross(s, e) == 0 && (s - p).dot(e - p) <= 0; } template vector

segInter(P a, P b, P c, P d) { auto oa = c.cross(d, a), ob = c.cross(d, b), oc = a.cross(b, c), od = a.cross(b, d); // Checks if intersection is single non-endpoint point. if (sgn(oa) * sgn(ob) < 0 && sgn(oc) * sgn(od) < 0) return {(a * ob - b * oa) / (ob - oa)}; set

s; if (onSegment(c, d, a)) s.insert(a); if (onSegment(c, d, b)) s.insert(b); if (onSegment(a, b, c)) s.insert(c); if (onSegment(a, b, d)) s.insert(d); return {all(s)}; } int prv(int i) { return (i+n-1)%n; } int nxt(int i, int k) { return (i+k)%n; } bool angleInBetween(ld angle1, ld angle2, ld angle3) { // check if angle3 is in between, angles are in between -pi and pi if (angle2 < angle1) angle2 += 2*PI; if (angle3 < angle1) angle3 += 2*PI; return (angle3 > angle1 && angle3 < angle2); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; Point p[n]; F0R(i, n) cin >> p[i].x >> p[i].y; ll dp[n][n]; // the answer for the segment [i...j], circular and clockwise F0R(i, n) F0R(j, n) dp[i][j] = INF; F0R(i, n) dp[i][nxt(i,1)] = dp[i][nxt(i,2)] = 0; // if its 2,3 adjacent points, dp is 0 int adj[n][n]; // if there exists a line segment between i and j that doesn't intersect F0R(i, n) F0R(j, n) { if (i == j) adj[i][i] = 0; else if (i == prv(j) || j == prv(i)) adj[i][j] = 1; else { Point v1(p[prv(i)]-p[i]), v2(p[nxt(i,1)]-p[i]), v3(p[j]-p[i]); ld a1 = v1.angle(), a2 = v2.angle(), a3 = v3.angle(); bool ok = angleInBetween(a1, a2, a3); F0R(k, n) { if (k == i || k == prv(i) || k == j || k == prv(j)) continue; if (!ok || sz(segInter(p[i], p[j], p[k], p[nxt(k,1)]))) { ok = false; break; } } adj[i][j] = ok; } } FOR(len, 3, n-1) { F0R(i, n) { int j = nxt(i, len); if (!adj[i][j]) continue; for (int k = nxt(i, 1); k != j; k = nxt(k, 1)) { if (!adj[i][k] || !adj[j][k]) continue; Point a = p[k]-p[i], b = p[k]-p[j]; ll dist1 = (k == nxt(i,1)) ? 0 : 1LL*a.dist2(); ll dist2 = (k == prv(j)) ? 0 : 1LL*b.dist2(); ckmin(dp[i][j], dp[i][k] + dp[k][j] + dist1 + dist2); } // cout << i << " " << j << " " << dp[i][j] << endl; } } ll ans = dp[0][n-1]; if (ans != INF) cout << ans << endl; else cout << "impossible" << endl; return 0; } 

 » 5 weeks ago, # |   0 Auto comment: topic has been updated by finnlidbetter (previous revision, new revision, compare).