Hi everyone, as mentioned in the title I have been recently trying to solve ADAGROW on SPOJ, but my best attempt was to model the solution as Min Cost Max Flow problem, with a graph made of roughly $$$10^6$$$ edges — $$$O(N^2)$$$.
The total flow that can be sent is only $$$K \le 20$$$, but my solution was still far from fitting into the TL. I realized that some of edges could be skipped and that if the input was random skipping those edges would've made the network small enough to pass — this way, I managed to AC the problem.
The worst case of my solution still has $$$~N^2/4$$$ edges, so I was wondering if anyone had tips on how else to model it so that the number of edges is always something reasonable.
Thanks!
So you make a graph with the nodes being the crops, and edges between $$$i < j$$$, with the cost set to $$$|a_i-a_j|$$$. As you noticed, this graph contains $$$O(N^2)$$$ edges. You can use divide and conquer on the array to reduce the size of the graph to $$$O(N \log(N))$$$ nodes and edges.
Recursively build the graph for the left and right half of the array. Then we only need to connect vertices $$$i$$$ in the left half to $$$j$$$ in the right half with the correct costs. We can split the absolute value in two cases, where $$$a_i \geq a_j$$$ and $$$a_i < a_j$$$.
For this we make extra paths with fake vertices in the "middle" of the two halves of the array of length n. One path has directed edges up and one has directed edges down, with infinite capacity and zero cost. The vertices in the paths correspond to the sorted array of a. Now we connect all $$$a_i$$$ in the left half to the correct fake vertex of each path, with cost $$$-a_i$$$ and cost $$$a_i$$$ respectively. All $$$a_j$$$ in the right half receive an edge from some vertex of both paths, with cost $$$a_j$$$ and $$$-a_j$$$. This construction turns out to make all costs between $$$a_i$$$ and $$$a_j$$$ pairs exactly $$$|a_i-a_j|$$$.
Edit: This doesn't encourage that all crops are used, so I think if you add a large negative number to all the outgoing edges out of each of the crops, the mincost flow of size k, will use the maximum number of edges (which we need if we want the k paths together to cover all the crops). Also I forgot to specify that of course we need to connect all the crops to the source and sink.
That approach is super cool, thank you so much :)
Yes, I was doing as you said to make sure all edges were being used, but thanks for making sure I got it right.
Also, you explained it super well :)