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: The node we're on currently and the 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)}{4} \cdot 100 \approx 4 \cdot 10^8$$↵
↵
Because of all the hash tables and the huger, 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).
↵
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
A simple bound of the number of states is
↵
Because of all the hash tables and the huger
↵
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).
