imagine you are given a matrix of positive integer numbers (maximum 25*15, value of number does not exceed 3000000). When you do column sums and pick the smallest and the largest one, the difference between them must be the smallest possible.
You can swap numbers in every row (permute rows), not in column, how many times you want.
Sort every row from smallest to biggest number.
Then shift every entry by the number of the row.
Could it really be this easy?
Can't really prove it but this seems plausible.
Sorted rows:
[1,2,3,4,5]
[1,2,3,4,5]
[1,2,3,4,5]
[1,2,3,4,5]
[1,2,3,4,5]
After shifting:
[1,2,3,4,5] shift 0 times left
[2,3,4,5,1] shift 1 times left
[3,4,5,1,2] shift 2 times left
[4,5,1,2,1] shift 3 times left
[5,1,2,2,4] shift 4 times left
Sum:
[15,15,15,15,15]
Edit: Yep too simple, just tried it and seems to only work with this example :)
Another idea that I had was to reverse every odd row or something...
Or mixture between reversing and shifting...
Edit2: Ok I give up, I can't figure it out. Even though it seems so simple... I have a brute force method though ;) Shift the numbers around randomly 1 million times (or how many times you want) and save the matrix if its difference is smaller than before :) Who needs math? Haha...