I start with a matrix, lets say 4x4. So I want the N top scores, with the sum of one element of each row. For example:

M[4][4] = { (13, 8, 5, 3), (11, 9, 7, 4), ( 8, 6, 2, 1), ( 6, 5, 4, 1) }

So the top 6 scores of that matrix will be:

top_scores = { (13, 11, 8, 6), // 38 (13, 11, 8, 5), // 37 (13, 11, 6, 6), // 36 (13, 11, 8, 4), // 36 (13, 9, 8, 6), // 36 (13, 11, 6, 5), // 35 }

What I want is to get the best scores directly, not calculating all the possible combinations and picking the top ones, because the matrix can be much bigger. I've tried to solve it with different approaches, but I failed in all of them.

  • $\begingroup$ Welcome to Computer Science! Could you please add a URL or reference to the original problem in the question? "I failed in all of them". How? Too slow to pass the time limit? $\endgroup$ – Apass.Jack Dec 3 '18 at 23:05

What you want to do is view your problem as a problem on a directed layered graph. This will allow you to solve the problem using algorithms for the $k$-th shortest paths problem.

In your example you would construct this graph: DAG

The arcs with no label have weight zero.

Finding the $k$-th shortest paths from $s$ to $t$ will find the $k$ top scores according to your definition. There are many efficient algorithms for obtaining the $k$-th shortest paths, including a variation on Dijkstra's algorithm which is probably the easiest to implement.

PS. Some of these algorithms require that the weights of the arcs be non-negative. That can be easily achieved in your case, by adding a large enough constant to every weight, e.g., shifting every weight by +13 in your example. The result is equivalent, since all the paths from $s$ to $t$ contain the same number of arcs.

  • $\begingroup$ The height of the graph could be reduced in half, but then it wouldn't be such a satisfying picture. $\endgroup$ – Albert Hendriks Jan 3 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.