search

ivanseed / google-foobar-help

Guidance on how to tackle some of the foobar challenges.
174 stars 47 forks source link

Distract the Trainers - Maximum Matching #24

Open MartinJaskulla opened 2 years ago

MartinJaskulla commented 2 years ago

My solution attempt consists of two steps:

  1. Creating a graph of the infinite games
  2. Finding the maximum matching

For the second step I am using the blossom algorithm by Jack Edmonds. However the test cases 3,4,5 seem to time out.

My questions:

  1. Has anyone submitted a solution using the blossom algorithm, which passes all test cases (meaning only my implementation of the blossom algorithm is too slow or is the time complexity of O(V^2 E) too slow in general)?
  2. Is the blossom algorithm needed at all?

For example you can pass all 5 test cases by recursively matching the node with the minimum edges with its neighbour with the minimum edges. However there are potential graphs for which this algorithms would fail:

#    *3              *10
#  /   \           /   \
# *2    *4 - *8 - *9    *11
# |     |         |     |
# *1    *5        *15   *12
# | \ / |         | \  /
# *0 *7-*6        *14-*13

# An adjacency list of the graph above. Numbers represent the indexes of the other nodes e.g. the first node [1] points to the second node [0,2,7] and the second node points back to the first node as well as the nodes at indexes 2 and 7
graph = [[1], [0, 2, 7], [1,3], [2,4], [3,8,5], [4,6,7], [5,7], [1,5,6], [4,9], [8,10,15], [9,11], [10,12], [11,13], [15,12,14], [15,13], [9,14,13]]
  1. Is it impossible for the input (banana_list) to create a graph with blossoms such as above or do Google's test cases just not cover such a case?