Bipartite Matching | Elementary Math problem | Network Flow | Graph Theory

Key Takeaways

[Music] [Music] hello and welcome my name is William we're still talking about network flow and today's topic is one of my all-time favorite flow problems which is the elementary math problem this problem is so interesting because it's solution uses flow but it really doesn't hit you as a flow problem to begin with one of the hardest things about Network flow I believe is actually identifying that a problem is a flow problem and then setting it up as so this is why I'm spending so many videos solving some flow problems so you really start understanding how to approach them and how they are solved so let's dive into the elementary math problem this problem is actually on caddis should you want to attempt it the link is at the bottom of this slide and also in the description here's the problem statement ellen is a math teacher who is preparing and questions for her exam in each question the students have to add subtract or multiply a pair of numbers ellen has already chosen the end pairs of numbers all that remains is decide for each pair which of the following three possible operations the students should perform to avoid students getting bored Ellen wants to make sure that the end correct answers on her exam are all different for each pair of numbers a B in the same order as the input/output a line containing a valid equation each equation should consist of five parts a one of the three operators be an equal sign and the result of the expression all the N expression results must be different if there are multiple valid solutions output any of them if there are no valid answers I'll put a single line with the string impossible instead well let's have a look at an example so Ellen goes and picks four pairs of numbers say 1 in 5 3 & 3 4 & 5 and lastly -1 and -6 she wants to assign operators either plus minus or multiply to yield the unique answers on the right-hand side of the equation one assignment of operators might be the following however this assignment of operators doesn't quite work because the answers are not unique on the right-hand side here's another way of assigning operators to the pairs of numbers this assignment does work because the answers are unique on the right-hand side which is one of the requirements for the problem so we just saw that not any arbitrary assignment of operators yields a valid solution but it's also possible for no answer to exist consider the following pairs of numbers in this case there can be no solution because there are not enough unique answers that can be produced using the operators plus minus and multiply as it happens this problem presents itself as a network flow problem even though that might not be obvious at first so take a moment and attempt to set up a flow graph that can actually solve this problem it's actually a really great exercise along the way while you're doing this there are a few questions you should ask yourself or at least that I asked myself when I first did this the first is there a way that this problem can be simplified into a bipartite graph I asked myself this because I know that solving a flow problem when it's a bipartite graph can be done very efficiently and also because bipartite graphs are very easy to set up then I asked myself how am I going to detect impossible sets of pairs will my flow graph be able to handle that or do I need to do some pre or post processing to actually figure that out and lastly I'm thinking about edge cases so like how do I handle multiple repeated input pairs and how is I going to change the flow graph these are all super important questions you need to ask yourself when solving this problem this slide deck explains the first two and the third is somewhat left as an exercise I don't want to give away the full solution to this really awesome problem so thinking about how we're going to solve this problem a little more a key realization to make is that for every input pair at most three unique solutions are produced think of the input pair two and three well for that pair we can either add 2 & 3 subtract 2 & 3 or multiply 2 & 3 so there can be at most three unique results there may be less if there are collisions think of the input pair 0 0 0 plus 0 is 0 0 multiplied by 0 of 0 and 0 subtracted by 0 is also 0 so we may end up with less than three unique solutions and that's fine the great thing about this is that we can easily set up a bipartite flow graph from this because we can have input pairs on one side and solutions on the other side let's see if we can set the flow graph and solve this set of input pairs we have the pair's 1 5 3 3 minus 1 minus 6 and finally 2 2 so how we're going to set up this bipartite graph is we're going to have input nodes on the left side and answer nodes on the right side for our first input pair 1 5 if we compute 1 minus 5 1 plus 5 and 1 multiplied by 5 we get minus 4 6 & 5 which become answer nodes on the right-hand side then we want to attach an edge between that input pair and the answer do the same thing for the next input pair make it input pair node and attach edges to the answer nodes however don't create another answer node if there already exists one with the value we need in this example you'll see that 3 plus 3 equals 6 and we already have an answer node 4 6 so simply attach an edge from 3 3 to 6 do not create another answer this is to ensure that our answers remain unique and do the same thing for the other two remaining input pairs you'll notice that the last input pair only produced two outgoing edges and not three this is because there was a collision in particular two plus two equals four but also two multiplied by two equals four and this is fine just put one edge don't put two edges then like every bipartite graph you're trying to find a matching four you'll want to add the source s and the sink T and the matching is really what we're after here we want to match input pairs to answers and then we've actually solved the problem the next step after adding the source and the sink is to actually assign capacities to the edges of the flow graph let's start on the right side the capacities from the answer nodes to the sink should all have a capacity of 1 since the answers need to be unique and limiting the edge capacity to 1 ensures that capacities for the input pairs two answers should also have a capacity of 1 since only one of + - or multiply should actually be matched to an answer capacities from the source to the input pairs should reflect the frequency of the input pair in this example all frequencies are 1 but as we know that's not always the case now the flow graph is set up let's run a Mac slow algorithm on it the flow algorithm does its thing and some edges are filled with flow these are the edges that were selected to be part of the maximum flow from this we can derive what the matching was more specifically we're interested in the middle edges those are the edges which give us information about the matching every edge in the middle with one unit of flow represents a matching from an input pair a B to its answer for example the input pair 1 5 was matched to the answer node 6 because there's one unit of flow going through that edge from this we can even deduce the opera used for each matching which is actually needed for the final output this can be done by trying which of the plus/minus or multiply operator results in the found matching basically we first solve the problem by figure out which answers we get and then work backwards to figure out which operator was used and theory we could tag each middle edge with what operator was used but I didn't bother doing that it's a it's more work let's wrap up this problem the last thing we need to do is look at the matchings and figure out what operators were used the first matching is the input pair 1 5 matched to 6 so we ask ourselves which of the 3 operators plus minus or multiplier results in 1 5 equaling 6 so we try all three options and we figure out that hey 1 plus 5 is 6 so the operator is the plus then we move on to the next pair and then we do the same thing if there are multiple operators that result in the right answer pick any of them and that's basically it we can verify that all our operators yield the correct result and that all our answers are unique I didn't go into great detail on how to support multiple repeated pairs but I'll leave that as an exercise to the listener thank you so much for watching please like this video if you learn something and subscribe for more mathematics and computer science videos