i am having a hard time making a code that find the the minimum sum of a matrix. But the catch is that you can only choose one from each row. example input would be :
3
1 8 5
9 2 5
10 7 6
and the output being:
9 10 12.
explanation would be that INT N is given and it makes a matrix of N*N and you must make a program that find the lowest sum of elements of a row. 9=1+2+6 10=1+2+7 12=1+5+6 I tried to brute force it by finding the sum of all the sums but that turned out to be a huge bust. Could any of you help me find a way to find this code because I am stumped.
Can you provide the problem link?
I would love to provide a problem link but it's in a pdf in a different language. sorry I would love to improve the way I formated the question but for some reason I can't start at a new line
You wrote
find the minimum sum. That would just be the sum of the minimum in every row. Do you want to want $$$N$$$ lowest sums as your sample output suggests?Yes!! Could you help me figure out how to do that??
First sort all rows. Keep a min-heap which will have all your current candidates for next minimum sum.
In the beginning, the only candidate for next minimum is the
sum with minimum of all rows. Add this candidate in the heap. Whenever adding asumin heap, also store the information, of which elements in each row it is a sum of (You will need this information later).At each step, extract the current minimum from the heap. Let's say this minimum sum is made of elements from each row with indexes $$$C_1 C_2...C_N$$$, then we can get next N candidates by increasing index of each row at one time like $$$(C_1 + 1)C_2...C_N$$$, $$$C_1 (C_2 + 1)...C_N$$$, $$$C_1 C_2...(C_N + 1)$$$. Add all these $$$N$$$ elements in heap if they are not already added.
You will need to the above step $$$N$$$ times, and in each step you can add atmax $$$N$$$ elements in heap. So time complexity will be $$$O(N * N * log(N))$$$