finnlidbetter's blog

MAPS 2019
By finnlidbetter, history, 6 years ago, In English

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.

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

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

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.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone want to share how to solve B and K?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it +2 Vote: I do not like it

      Oh god... I got the wrong formula... Thanks!

      Sounds like the formula should be $$$F_k(n) = (5n + 1) (nk-k+7)$$$?

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

        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.

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

      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 ?

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

        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.

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

        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.

        → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

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

      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.

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

        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.

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

          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 1
          Further hint 2
          Solution idea
          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it +11 Vote: I do not like it

              If you're still interested in a proof, the idea is more or less the following:

              Proof outline

              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.

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

    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.net/blog/entry/58048?#comment-417398

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

WA Code for G

My Ideas

Consider 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?

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

    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?

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

      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.

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

        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 case
        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

        → Reply
»
6 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).

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it

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<bits/stdc++.h>
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<b100, long long> gt;
	b100 p1(1),p2(0),p3(1),p4(0),mask;
	for(int i=0;i<m;i++) mask.set(i);
	for(long long i=0;i<(1<<19);i++){
		if(!gt.count( (p1<<m) | p2 )) gt[(p1<<m) | p2]=i;
		p2^=modm(p1<<1,mask,m);
		swap(p1,p2);
	}
	long long ans=1LL<<50;
	long long k=(1<<19)%m; 
	for(long long i=0;i<(1<<19);i++){
		if(gt.count( (p4<<m) | p3 )) ans=min(ans,gt[(p4<<m) | p3]+(i<<19));
		p3^=modm(p1<<k,mask,m);
		p4^=modm(p2<<k,mask,m);
		swap(p1,p3);
		swap(p2,p4);
	}
	printf("%lld\n",ans+1);
	return 0;
}
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve D, M?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    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 Code

    M: 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 k<j$$$ we must have $$$r_k>0.$$$

    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<i\le num,$$$ but we can do these separately.

    Code

    → Reply