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 problems, which is the elementary math problem. This problem is so interesting because its 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.

Elon has already chosen the N 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. Elon 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 The n expression results must be different.

If there are multiple valid solutions output any of them. If there are no valid answers, output a single line with the string impossible Instead, let's have a look at an example. So Ellen goes and pigs, four pairs of numbers, say one and five, three and three, four and five, and lastly minus one and minus six. 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 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 bicycle Part A 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 two and three, subtract two in three or multiply two in three. So there can be at most three unique results, there may be last if there are collisions, think of the input pairs 000 plus 000, multiplied by 00. And zero subtracted by zero is also zero.

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 have input pairs on one side and solutions on the other side. Let's see if we can stop the flow graph and solve the set of input pairs. We have the pairs 1533, minus one minus six and finally, two, two. 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 one five, if we compute one minus pi One plus five and one, multiply by five, we get minus four, six and five, 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 an 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 three plus three equals six and we already have an answer node for six. So simply attach an edge from three three to six do not create another answer node. 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 But also to multiply 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 for, you'll want to add the source s and the sync T. And a 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 one since the answers need to be unique and limiting the edge capacity to one ensures that capacities for the input pairs two answers should also have a capacity of one since only one of plus minus 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 one. But as we know, that's not always the case.

Now the flow graph is set up, let's run a maximal 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 so we can derive what the matching was. More specifically, we're interested in the middle edges. Those are the edges which gives 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 one five was matched to the answer node six because there's one unit of flow going through that edge. From this we can even deduce the operator used for each matching, which is actually needed for the final output. This can be 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. In theory, we could tag each middle edge with what operator was used, but I didn't bother doing that 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, one five matched to six. So we asked ourselves, which of the three operators plus minus or multiplier results in one five equaling six, so we try all three options and we figure out that hey, one plus five is six. 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.