### finnlidbetter's blog

By finnlidbetter, history, 7 months ago, ,

You are invited to participate in MAPS 2019 (Mount Allison Programming Showdown) on Saturday, March 16, 16:00-21: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:

http://maps.rocks

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://maps19.kattis.com/.

UPDATE: The problems are now available on open kattis here if you wish to work on and submit the problems out of contest.

• +39

 » 7 months ago, # |   0 If anyone is hoping for a contest to participate in today, MAPS 2019 starts in one hour and registration is still open. Feel free to discuss problems here once the contest is over.
 » 7 months ago, # |   0 Does anyone want to share how to solve B and K?
•  » » 7 months ago, # ^ | ← Rev. 3 →   0 For B, the recurrence relation has closed form $F_k(n) = (5n + 6)(kn + 7)$so you can just precompute primes up to 10^8 + 7 and then check for each n if both 5n + 6 and kn + 7 are primes.
•  » » » 7 months ago, # ^ | ← Rev. 3 →   +2 Oh god... I got the wrong formula... Thanks!Sounds like the formula should be $F_k(n) = (5n + 1) (nk-k+7)$?
•  » » » » 7 months ago, # ^ |   +8 emanuelefwm assumes the sequence is 0-indexed, while you assume it is 1-indexed as the problem statement describes, but they are essentially the same thing.
•  » » » 7 months ago, # ^ |   +3 how do you approach these kinds of problems like if we can guess that F is quadratic in n then we can solve for co-efficients and get F ,what's the intuition that F is quadratic in first place ?
•  » » » » 7 months ago, # ^ |   0 Well, there are general methods to solve such recurrences so that you don't have to do any guessing (for instance the one described here).In this case since the problem is directly asking you to find when the number can be written as the product of two primes, and since the numbers get so large (10^15) that factorizing each of them is not feasible, we can guess that there is a closed form consisting of a product of two terms.
•  » » » » 7 months ago, # ^ |   +6 If $(F(n)-F(n-1))-(F(n-1)-F(n-2))$ is of degree $0,$ then $F(n)-F(n-1)$ is of degree one and $F(n)$ is of degree two.
 » 7 months ago, # |   0 Did anyone else have issues with TLE on J? I was using Dinic's and had a hard time squeezing it into an AC.I would also be interested to see thoughts on I and M...
•  » » 7 months ago, # ^ |   +11 I is half-plane intersection. You binary search on the distance, and for a given distance d, you move each of the line segments forming your polygon in by d, and check if there still exists a convex polygon.
•  » » » 7 months ago, # ^ |   +5 Another solution to I that is perhaps easier to implement is to do nested ternary searches. Ternary search on the x coordinate and ternary search on the y coordinate for a fixed x coordinate.
•  » » » » 7 months ago, # ^ |   0 Could you explain the solution to K? I guessed that "visiting the same city again is never optimal", but I couldn't prove it (and thus, didn't implement) during the contest.
•  » » » » » 7 months ago, # ^ |   +5 You are correct that you should never visit the same planet twice. Try thinking about what the solution would look like in terms of the edges that are traversed by regular travel rather than by portals. Further hint 1The edges traversed by regular travel in an optimal solution form a set of pairwise and self vertex-disjoint walks. (Can you prove this?) Further hint 2How long can the longest of these walks, in terms of the number of edges, be in an optimal solution? 1 edge? 2 edges? 3 edges? More? Solution ideaUse dynamic programming to find the lowest cost set of vertex-disjoint walks, each with at most 2 edges, covering all vertices.
•  » » » » » » 7 months ago, # ^ |   +8 I think the main thing I had trouble proving was "hint 1". I couldn't prove that it was true that an optimal solution never went back to a non-source node twice.Also, are there solutions that are going to be posted? I'd also like to see the solution for E. Benq said that he just precalculated with brute force, so I was wondering if that was the intended solution.Also, since I haven't mentioned this, pretty nice contest. Lots of easy problems (a good thing for the target audience) and also some pretty cool problems.
•  » » » » » » » 7 months ago, # ^ |   +11 If you're still interested in a proof, the idea is more or less the following: Proof outline Every feasible solution is a set of non-trivial walks that cover all vertices and don't share any endpoints. (Endpoints represent using portals). In an optimal solution, no walk visits the same vertex twice. (If it does, you can find a no worse solution by skipping the already visited vertex). In an optimal solution, no pair of walks share a non-endpoint vertex. (If they do you can find a no worse solution by skipping the already visited vertex in one of the walks). In an optimal solution, no walk has more than 2 edges. (If there is such a walk, you can find a better solution by splitting the walk). I don't think the solutions are going to be posted, but I'd be happy to point you in the right direction if you're stuck on any of the remaining problems. Regarding problem E, Benq and everyone else that solved it did as the author intended: a brute-force pre-computation. I would be very interested if anyone has a non-brute-force approach.And thank you for your kind comment on the problemset. We were glad that all problems got solved, that no-one solved all the problems, and that it was accessible to newcomers to competitive programming with more than half of all teams that solved at least 1 problem, also solved at least 3 problems.
•  » » 7 months ago, # ^ |   0 Not sure if this is surprising or not, but I had no issues with the standard DFS-based matching, which I think is $O(V E^2)$ in worst case, but difficult to come up with test cases for. Some discussion here: https://codeforces.com/blog/entry/58048?#comment-417398
 » 7 months ago, # |   0 WA Code for GMy IdeasConsider a directed graph of all the enclosure types. If all nodes are isolated, the answer is simply "FALSE ALARM". Otherwise, we check if all non-isolated nodes form a weakly connected component. We then check if all nodes have indegree equal to outdegree, or that exactly one pair exists such that indegree = outdegree-1 and outdegree = indegree-1. If both of these conditions are fulfilled, the answer is "POSSIBLE", and if not, "IMPOSSIBLE".Can someone provide a countertest to this logic, or find a flaw in my implementation?
•  » » 7 months ago, # ^ |   0 You have the right idea, but I think you aren't implementing the check for "all non-isolated nodes are in a single component" correctly. You start the search from node 0, but what if 0 is itself isolated and not part of the component?
•  » » » 7 months ago, # ^ |   0 finnlidbetter notice that the variable "st" in my code is set to a nonzero value if an edge is found leading from "st" to another node. I added "assert(adjacency[st].size() > 0);" just to make sure I was not starting the BFS/DFS from an isolated node, and I still get WA instead of the RTE that a failed assert would produce.
•  » » » » 7 months ago, # ^ |   0 Ok well that would have to be fixed as well, because that could be part of a test case. Try debugging your solution on this test case: Wrong answer test case5 8 monkey 2 penguin elephant elephant 3 lion lion elephant jaguar 1 monkey lion 2 monkey elephant penguin 0 
•  » » » » 7 months ago, # ^ |   +3 Your issue is that your isGood counter is not counting what you think it's counting. It's not counting the nodes that are completely disconnected from everything else, it's counting the nodes that have 0 edges to other nodes. Thus, when you do (numSeen != N — numGood), it's possible that numSeen is > N-numGood and for you to have a possible solution.
 » 7 months ago, # |   0 Auto comment: topic has been updated by finnlidbetter (previous revision, new revision, compare).
 » 7 months ago, # | ← Rev. 3 →   +11 It's sad to see that the intended solution for E is really brute-force precomputation, I probably shouldn't spend that much time thinking about this problem. Here's a baby-step-giant-step solution which can pass without precomputation, but I actually don't know how to prove an upperbound for the answer so I chose $2^{19}$ based on "precomputation". The observation is, from the recursive formula $a_{i+1}=a_{i}M \oplus a_{i-1}$ we can derive that $a_{i+2^k}=a_iM^{2^{k-1}}\oplus a_{i-2^k}$. Therefore a power of 2 giant step can be done efficiently. This code barely got AC but it is not optimized at all. #include using namespace std; typedef bitset<100> b100; inline b100 modm(b100 x, b100 mask, int m){ return ((x>>m)^x)&mask; } int main(){ int m; scanf("%d",&m); unordered_map gt; b100 p1(1),p2(0),p3(1),p4(0),mask; for(int i=0;i
•  » » 7 months ago, # ^ |   0 You actually don't 'technically' need to precompute: If you modify your code to step your shift up from 1 while you've found no solutions it passes in 0.57s. I also have no idea how to prove an upper bound; I expect that most solves didn't prove one but instead relied on a guess and check to solve.
 » 7 months ago, # |   +8 How to solve D, M?
•  » » 7 months ago, # ^ |   +20 D: For all $n>25$ we can find a solution with $k\le 3.$ Suppose that we fix the number of bits in each of the $k$ numbers $a_1,\ldots,a_k$, we can do dynamic programming where the states are determined by $idx:$ the current bit of $N$ (iterate from $60$ down to $0$) $carry:$ the carry from the previous bit of $N$ $b_1, \ldots, b_k:$ the number of bits which each of the $k$ numbers needs (in order to make each one equinumerous) You can do transitions based on whether $a_1,\ldots,a_k$ have $1$ or $0$ in the $idx-1$'th bit.Jason Yuen's CodeM: Let $num$ be the final number of piles, and let $sum$ be the total number of crates. For all possible values of $num$ you can calculate the needed number of moves in linear time. Let $v_i$ be the number of crates in the $i$-th pile initially. In total, we must do $ans=\sum_{i=1}^{num}\left |b_i-sum/num\right |$ pickups and dropoffs in total. Now we need to deal with the moves in between stacks. Let $l_i$, $r_i$ be the # of moves from stack $i+1$ to $i$ and stack $i$ to $i+1,$ respectively. We can get a lower bound on $l_i$ or $r_i$ based on how many crates we need to move between $i$ and $i+1.$ After doing this, we should increment each $l_i$ or $r_i$ until $0\le r_i-l_i\le 1$ and $r_i-l_i\ge r_{i+1}-l_{i+1}$ for all $i.$ Also, if $r_j>0,$ then for all $0\le k0.$ After calculating all the $l_i,r_i,$ we can add them to $ans$ to get the result. If $sum$ is large we might not have enough time to calculate these values when \$N