There are a variety of ways to try to resolve boundary conditions; it's a problem you need to deal with whether you are doing direct convolution or FFT-based convolution. Unfortunately, it's not clear exactly what your difficulty is (your graphs don't have enough context for me to tell where they come from or what they mean); in the following, I will have to guess.
The thing you need to need to remember about FFT-based convolution is that it treats its input as a periodic loop. Your question mentions a problem that "does not arise if we directly integrate to find convolution"; that difference is probably due to this property.
You claim that "the zero padding is responsible for the undesired boundary effects". However, in order for FFT convolution to match the results of direct convolution, you must ensure that there is sufficient zero padding added to the original data to keep the periodic nature of the FFT from interfering with the convolution. For this purpose, I believe that "sufficient zero padding" should be length of the filter you are convolving with. Try splitting the zero padding for your fftconvolve() evenly between the beginning and end of your data run.
If you are unsatisfied with the boundary effects of your direct convolution, I'm not sure what to tell you, since I don't know what your application is. I will advise that the result of your convolution will be as long as the original data plus the length of the filter, so you will need to provide for that.
This question is basically two-fold:
- How do you solve the actual problem? and
- How do you generally read in graph data?
The first question is a bit narrow, and it sounds like the second one is of more interest to you in the long run. So, let me just point you to flow algorithms. It's a step up from Dijkstra in terms of implementation complexity, but as you already realized, there is just so much you can do with a single path. Network flows are a whole different thing.
As for reading your input, it dramatically depends on the kind of graph library you want to use. A few years ago, when I was active in these competitions, we weren't allowed to use 3rd-party libraries, so had to roll our own implementations.
In that case, you have to think ahead if you want to read in a complete matrix, or if you want to keep the graph as an adjacency list. These are the two most important data structures to know for graph algorithms. (more precisely, often you don't need to think ahead, because the problem input specification directs you to one or the other)
Reading input for an adjacency matrix is as straightforward as two nested for-loops. In the body of the inner loop, you simply read one value and assign it to one matrix cell. Done.
For adjacency lists you need to prepare the list of neighbors of a node for each of the nodes, i.e. for n
nodes you prepare a list of size n
that contains an empty list for each entry. Then you again have two nested for-loops: the outer loop goes over the nodes, the inner loop reads the neighbors of that node and adds them to the corresponding inner list. Voila - an adjacency list representation of the graph.
Important addition for programming challenges/competitions: Make sure that you know in your dreams how to write both variants before you even think about competing. There are limitless sample questions and practice sites out there. Search around for problems with graph input, then write and rewrite the input code again and again. It should almost always be nearly the same code, and once you've grown accustomed to it, reading in input like the one you gave above takes you 5 minutes at most. If you want to compete with the really strong players in that field, you should be able to code the input reading for this within about 1 minute or less.
Best Answer
Mock your inputs. Say "Assume that this array consists of integers or floats or whatever". You can also annotate things with comments.
I'd write this in Python like so:
I'm prone to writing Python functionally so I'd instantiate a list of tables then call a function that checked each table to see if had enough seats or not. I'd probably use a filter to that. Could also do a list comprehension. The latter is more "Pythonic".