Блог пользователя viniciusth

Автор viniciusth, история, 5 лет назад, По-английски

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
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 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?