PROBLEM LINK:Setter Misha Chornyi DIFFICULTY:CHALLENGE PREREQUISITES:General Programming. Knowledge of Probability and Expectations PROBLEM:Given a $N*M$ matrix, divide it into $K$ connected components such that $MaxMin$ is minimized, where $Max$ is the maximum valued component and $Min$ is minimum valued component. QUICKEXPLANATION:Key to AC Notice that numbers are uniformly, randomly generated. Trying out various orderings and simulations was expected to give good score. Note that the values are uniformly, randomly generated. Hence, if we divide the array into $\frac{N*M}{K}$ partitions, then it;d be a good start. Lets see what more we can do. Assign labels to array elements such that elements of same labels are in same connected component. Now, try to convert it into a $1D$ array and see if we can do manipulations (eg push another element into minimum district subarray). Trying out multiple such labellings/orderings/patterns and operating ideally on them was expected to give a good score. EXPLANATION:I will be sharing the expected solution of setter in the editorial. As usual, the editorial of challenge problem is never complete without contribution from community. So if you have any approach which is not yet covered, feel free to share it! :) Setter's solution is quite simple and relies on the fact that numbers are randomly generated, so its very unlikely that theres a huge concentration of high or low values accumulated around a small area. I tried to visualise the process in pic below, before beginning to explain it. The first step in the above algorithm would be, to try any random order. One property which must hold in that order is that, elements which are adjacent in the equivalent $1D$ array must also be adjacent in the initial $2D$ array as well. You can try multiple such orders, for example, in the picture above I followed the order/pattern of going from left to right, then 1 step down, then right to left ... and so on. Now, for every order you try, assign the matrix elements "labels" or indices where they'd appear in $1D$ array. Once done, convert the $2D$ array into $1D$ array. Now our problem reduces to "Partition a $1D$ array into atmost $K$ partitions such that difference between highest and lowest valued partition is minimum.". Note that, following just $1$ or $2$ patterns may not give optimal answer, we simulate the process for multiple patterns/orderings. (Meaning, steps till now are simulated for multiple patterns). One way of initially partitioning the array could be, find the array sum and partition whenever the size of partition is $\approx N*M/K$, other would be to partition when the partition sum is close to $\sum A_{ij}/K$. Another very good improvement is, once we get an initial partition, try "popping an element out of maximum partition" and/or "pushing an element into minimum partition" (since we made sure that elements adjacent in $1D$ array are adjacent in $2D$ matrix as well, its well possible). Do this as long as it helps. However, note that our algorithm has an expensive step, determine and assign partition. That step takes $O(N*M)$ time, while manipulating the already partitioned array (pushing/popping as discussed before) takes significantly less time. So, its worthwhile to pay some extra attention in trying to improve manipulation techniques rather than blindly using thousands of orderings/patterns. Thats it from setter's side XD. I tried to decode participants solutions but most of the top solutions are complex :( . I'd hence like to invite everybody to share their approach and how it ended up for them. Hope you guys enjoyed the problem. SOLUTIONTester Editorialist $Time$ $Complexity=O(N*M)$ CHEF VIJJU'S CORNER :D1. Setter's Notes 2. Hall of fame for noteworthy Solutions
3. A note on when questions have this random generation 4. Related Problems
This question is marked "community wiki".
asked 23 Sep '18, 18:14

Here is a visual comparison of the hall of fame authors on a random case $(n=536, m=958, k=879)$. The colors in the images are districts and the difference between the largest cluster and smallest cluster is in the title. The grayscale image gives a sense of the order in which order districts are placed (black to white corresponds to earliest to last). Click images to see them in full resolution. mcfx1: max  min = 1No obvious pattern for the top part, the bottom part has alternating seams. The packing is done topdown, so I presume the transition at the bottom is to abort the previous packing cleanly. other than that I have no idea what happens here, especially on the top, but evidently it works really well. whzzt: max  min = 1Starts off with a clockwise spiral and transitions into slicing the interior when it's small enough. Nice choice of pattern to maximize the circumference which directly translates to a good chance for optimization. The interior is also easy to handle, it corresponds to something like phase 2 that I describe in my solution. gorre_morre: max  min = 12Divide into bands of as equal sum as possible, then split the bands into correct sized districts. Seems similar to my approach but much more aggressive in it's choice of bands (wide) and in the optimization of districts. This seems to help a lot, in contrast to my solution. The choice of seams seems (no pun intended) to be a lot less strict, which makes the districts look quite fuzzy. algmyr: max  min = 911I'll elaborate a bit more on this one, for obvious reasons. I didn't quite reach the scores of the top 3, but I wasn't too far off considering a naive solution typically has differences of order between $10^8$ and $10^9$. I do two phases, creating seams to separate bands of equal(ish) size and then dividing the bands into districts. The reason for this structure is to simplify code and guarantee connectivity. Essentially the same code can be used for both phases. Phase 1  BandsSay we want to create $b$ bands and that the total sum is $S$. My goal is to create one band, so the goal sums are $\frac{(b1)S}{b}$ and $\frac{S}{b}$. Start naively picking elements from left and right and add them to a left and right partition and try to maintain the correct ratio. Proceed until we have a 1 wide seam to go:
Now, the elements in this seam can belong to either partition, and we have a goal sum for both partitions. This is an instance of a partition problem! Sadly this problem is NPhard, but fortunately it's easy to approximate (this has been called the easiest NPhard problem for a reason). I use the KarmakarKarp differencing method (see the wiki page linked). One band is now done, proceed to split the larger part into $b1$ equal(ish) bands. Phase 2  DistrictsI pick bands so that they are at least narrow enough for districts cover around 3 rows, which means I can safely do the same kind of seam process to produce correct sized districts. Note on image creationThe color images were generated based off my validation+scoring script I used during the competition. In short: find all clusters and note which clusters are neighbors. Go through all clusters and assign to it the mex of all its neighbors. This is then translated using a color table. Typically this only takes 45 colors (in general any board will require at most 4 colors, and this method typically comes pretty close). For this kind of image related stuff I can recommend NetPBM as a format. For the graymaps, the output data by itself is only a header
away from being a valid graymap! answered 25 Sep '18, 07:05

I quite liked the problem, even if I didn't get as good a score as the others. mcfx1 and whzzt in particular achieve perfect or near perfect scores, which is just amazing. They typically get
maxmin = 1
which is optimal unless the sum of all elements is divisible byk
).