I recently solved the problem Playlist on Kattis: https://open.kattis.com/problems/playlist. In brief the statement is:
Given a directed graph with $$$n \leq 100$$$ nodes and the outdegree of each node is less than 40. All the vertices are colored. Find a path of length 9 in the graph such that no pair of nodes in the path has the same color, and output this path. If there're multiple solutions, output any, output "fail" if there is no such path. The time limit is very big (12 seconds).
My solution involved meet-in-the-middle:
Split the path into a middle node and two paths of length 4 connected to this middle node.
Now we first calculate for each node all the subsets of 4 colors such that there's exist a path of these four colors going into this node and going out of this node. This can be done by a DFS with extra state. The state is of the form: (current node, subset of colours we visited until know). A state can be extended by putting the colour of the current node in the subset and going to a neighbour of a color that isn't in our subset. With hashtables I assure that no path is calculated twice (like normal DFS). We do this for the given graph, and the reverse graph. A simple bound of the number of states is $$$\binom{100}{4} \cdot 100 \approx 4 \cdot 10^8$$$, and for each state we loop through all the out edges. So the number of operations of this step is about $$$40 \cdot |\mathrm{States}|$$$.
In the combining step we loop through all candidate middle nodes. Now we have two collections of subsets (one for the ingoing paths, one for the outgoing). We want to find two sets in both collections that are disjoint. I used Inclusion-Exclusion to count for a given set in the first collection, how many sets in the second collection have at least one element in common, and with this we can detect disjoint sets. This adds $$$2^4 \cdot |\mathrm{States}|$$$ to the runtime.
Because of all the hash tables and the huge number of states, my solution ran in 11 seconds.
Here's my code: https://ideone.com/JEZoNF
Is there a simpler or faster solution? I couldn't find an editorial from the contest (Spotify Challenge 2011).
Auto comment: topic has been updated by jeroenodb (previous revision, new revision, compare).
$$${100} \choose {4}$$$ fits in space so it might be possible to use an array instead of a map. You can't have hundred such arrays but a single array should be enough when we consider one vertex as the middle one.
Although we could only consider one vertex as the middle one at once, and do a DFS for that, I don't think we can shrink the number of states of the DFS to $$$\binom{100}{4}$$$. Because the transitions need also to know which node we came from (A bit like hamiltonian path DP).
First I also stored parent pointers of the DFS for the reconstruction, but they're not needed. Therefore I don't need maps, but sets. This could be done with 100 bitsets of $$$\binom{100}{4}$$$, but it seems hard to give a unique id to each subset that can be computed quickly. Now I use bloomfilters, and with a few other optimizations it now gets accepted in 6 seconds.
When you are at any node in DFS, store up to three previous colors. Don't include the color of the final node. That's $$$100 \cdot {{100} \choose 3}$$$ states, or let's just make it $$$100^4$$$. You can compress further when considering the very last node.
You can do the whole thing with for-loops too, no DFS needed.
That's a problem of counting lexicographically smaller sorted sequences of fixed length. It's indeed non-trivial $$$O(4)$$$ with precomputed binomial coefficients and prefix sums. It's be easier and faster to precompute an array
int id[a][b][c]so you could say that hash of $$$(a, b, c, d)$$$ is $$$id[a][b][c]+d$$$. So, $$$id[a][b][c]$$$ is lexicographical id of sequence $$$(a, b, c, 0)$$$, minus $$$c$$$.Sorry for necroposting, but there's a really nice solution using a technique called color coding. Take every color (artist) and remap it to a random one in $$$[0,k)$$$ for some $$$k \geq 9$$$. Then, we can do DP over these reduced colors in O($$$2^k \cdot E$$$) instead of the normal $$$O(2^N\cdot E)$$$ DP. If we're lucky, we color the nodes just right and find the path of length 9. We will repeat this until time limit is reached. If we find a solution, we print it, otherwise we print "fail".
Now, what should $$$k$$$ be? Let $$$p(k)$$$ denote the probability that a coloring is "good", i.e., running DP on it finds a path of length 9. If there is exactly one path of length 9, $$$p(k)=\frac{k!}{(k-9)!x^9}$$$. Now, we want to minimize the expected work, $$$2^k \cdot p(k)^{-1}$$$, which can be found to be minimized at $$$k \approx 11$$$. It's only about 2x better than $$$k=9$$$, but in practice, larger $$$k$$$ seem to work better. Perhaps it's difficult to make strong test data.
You can also use color coding to solve https://open.kattis.com/problems/dragonball2. The algorithm can also be derandomized in a pretty neat way https://www.cs.tau.ac.il/~nogaa/PDFS/colpr.pdf.
If we assign a random vector of length $$$k$$$ to each color, then we can assume the path has no repeated color if the determinant formed by the $$$k$$$ vectors is a non-zero value (with high enough possibility), and we can use a $$$O(2^kkm)$$$ DP to find the sum of determinants for all paths.
Despite being very familiar with k-path problem and knowing like 6 different FPT algorithms for it, this is a new one for me and likely very first one that is both fast and easy to code!
However, I have to point out that your description is somewhat lacking. The way I understood it at the first reading is that we draw a random color for each vertex, draw random vector per each color and then we run these determinants. That is both 1) too slow (cause we need $$$e^k$$$ iterations) 2) incorrect (cause we get a lot of false negatives because path of colors abc cancels out with bac). The way I'd fix that is to forget about any colors whatsoever and just draw a random vector for each vertex and I'd reckon that'd work. Isn't that what you meant?
EDIT: Oh, I misread the original problem, it already imposes the coloring, it's not an ordinary k-path :) (introducing colors is very often done in order to solve the problem without any colors, which is why I was mistaken). In that case we dont need to iterate through $$$e^k$$$ colorings, but we still have to deal with the cancellation issue. I think multiplying each vector by a random constant (different for each vertex) should work then?
EDIT2: As mnnvmar pointed out to me, multiplying by random number per vertex is not enough — we can make a clique on 3 vertices ans everything will cancel out. But if we draw a random number for each edge and multiply each the transition through it by that number — that will be enough, because the set of edges uniquely determines the path, unlike it's set of vertices