Column sums

Hello world

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.

How would you solve this task?

I'm not asking for your code but your ideas.

Thanks in advance
Last edited on
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...
Last edited on
Your solution was the first that sprung to my mind and yes - it's not correct. But thank you for your comment.
Last edited on
Topic archived. No new replies allowed.