viniciusth's blog

How to solve this problem?
By viniciusth, history, 5 years ago, In English

Given a NxN grid, you need to choose one element in each row and every element must be in a distinct column (Like placing N rooks in a NxN grid).

Print the elements you chose in each row such that they have maximum possible sum. (Any possible answer is accepted) $$$1 \leq N \leq 100$$$

$$$1 \leq A_{i,j} \leq 100$$$

Example input:

3
1 10 12
13 5 15
20 2 5

Example output: 

2 3 1

Preferably i want to solve the problem when the size of elements doesn't really matter (Say, $$$A_{i,j} \leq 10^9$$$).

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

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

You should include source for the problem. I think most people would be hesitant to reply, if you are not providing a source, unless they know you and trust you.

Errichto wrote a very detailed blog here. I think it's a very comprehensive post, about what a lot of people would prefer and what you should try to avoid.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Sure, its a reduced form of problem G that appeared on the Brazilian ICPC this last saturday. Here's the link.

    → Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Did I miss something, or is it just https://en.wikipedia.org/wiki/Hungarian_algorithm ?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Yes, i think that's it. I didn't know about the existence of this algorithm. Thanks!

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

    Wow. After seeing the algorithm, I remember I have done Optimization course in university, where we were taught the workers assignment problem.

    Looks like I don't remember anything that is taught to us. Makes you wonder, what have I done for 3 years at college?

    → Reply