Loopin's blog

By Loopin, history, 7 years ago, In English

You have nXn matrix filled with numbers,you have to pick n numbers from it such that their sum is maximal and no 2 are in same column or row. My guesses after 20 mins: I tried greedy algorithm,sorting each row and memorizing column of each number in new sorted matrix and now I would take largest in each row and if 2 are in same column I would pick larger and move pointer for row of lower one to next largest number,but no can do,found counterexample,we can pick lower one if number behind greater number is much larger then number behind lower number...

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it