A fork week

AtCoder Grand Contest 039 was the highlight of the Sep 30 - Oct 6 week (problems, results, top 5 on the left, analysis). ksun48 was the fastest on five problems, but ecnerwal was also able to finish problem F in about an hour, something that other top finishers could not match. Congratulations on the win!

Problem D has gathered quite some heat (see this comment and the thread below), but I think the problem was actually very nice: you are given 3000 points on the circumference of the unit circle. What is the expected position of the center of the circle inscribed in a triangle formed by a random triple of those points?

In my previous summary, I have mentioned a Codeforces problem: consider a bipartite graph with 6 vertices in each half, and each edge existing with a certain probability (these 36 probabilities are given to you). What is the probability that this graph has a perfect matching? The probability needs to be computed modulo 10⁹+7, and the time limit is 7 seconds.

My approach is already described in this comment, but let me repeat it here since it's short anyway. Let us run the normal dfs-based algorithm for finding maximum matching, but whenever the algorithm needs to check if an edge exists, we will fork the search, one branch continuing as if it does, and one branch continuing as if it does not. Why would something like this work fast: the intuition is, since dfs stops right after finding any augmenting path, in most branches we won't care about the state of many edges, therefore the total amount of branches won't be too big.

Here is my implementation, the number of branches it considers for a 6x6 graph is 16404365 (much less than 2³⁶, as expected), practically it means getting accepted in 5.3s out of 7s time limit.

This approach is quite tricky to get right, though. Since we have to branch a recursive algorithm (dfs), we need to rewrite it to maintain the stack in arrays we control so that we can copy those. This process is quite tedious and error-prone, and it took me quite a lot of time to find a bug in that part of the code (if I remember correctly, I was missing line 113 "stack[sp - 1] = cur;").

Here's my question: is there a programming language or an approach where implementing such branching search on a recursive algorithm would be easy, and that would still fit into the 7 second time limit for 16 million branches? fork() in C/C++ comes to mind as the first choice, but I think its overhead is way too high for such number of branches to be practical.

Thanks for reading, and check back for more!