### viniciustht's blog

By viniciustht, history, 3 months ago, ,

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$).

• +7

 » 3 months ago, # |   +8 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.
•  » » 3 months ago, # ^ |   +4 Sure, its a reduced form of problem G that appeared on the Brazilian ICPC this last saturday. Here's the link.
 » 3 months ago, # |   +6 Did I miss something, or is it just https://en.wikipedia.org/wiki/Hungarian_algorithm ?
•  » » 3 months ago, # ^ |   +4 Yes, i think that's it. I didn't know about the existence of this algorithm. Thanks!
•  » » 3 months ago, # ^ |   0 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?