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