ZZEZ73's blog

By ZZEZ73, history, 2 years ago, In English

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.

 
 
 
 
  • Vote: I like it
  • +11
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you provide the problem link?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes!! Could you help me figure out how to do that??

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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 a sum in 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))$$$

          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I am extremely new to c++ and my english isn't that good so could you show me an implantation in code for the algorithm you just said. I am having a hard time understanding the explanation.

            Sorry for the inconvenience

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ZZEZ73 (previous revision, new revision, compare).