#python #algorithm #optimization #data-structures
Вопрос:
Мне дана таблица команд A и B, где для каждой пары из 2 игроков есть номер. Строки представляют игроков игроков команды A, а столбцы-игроков команды B. Если число положительное, это означает, что игрок A лучше, чем игрок из команды B, и наоборот, если отрицательное.
Например:
-710 415 527 -641 175 48 -447 -799 253 626 304 895 509 -523 -758 -678 -689 92 24 -318 -61 -9 174 255 487 408 696 861 -394 -67
Обе команды знают эту таблицу. Теперь, что сделано, так это то, что команда A сообщает о 5 игроках, команда B может посмотреть на них и выбрать для них 5 лучших игроков. Если мы хотим объединить команды, мы суммируем числа на заданных позициях из таблицы, зная, что у каждой команды есть капитан, которого считают дважды (как если бы в команде было 6 игроков, и капитан был там дважды), если сумма положительна, команда А лучше.
Входными данными являются числа a
(количество строк/игроков A) и b
(столбцы/игроки B), а также таблица, подобная этой:
6 6 -54 -927 428 -510 911 93 -710 415 527 -641 175 48 -447 -799 253 626 304 895 509 -523 -758 -678 -689 92 24 -318 -61 -9 174 255 487 408 696 861 -394 -67
На выходе должно быть 1282.
Итак, то, что я сделал, заключалось в том, что я поместил числа в матрицу, подобную этой:
a, b = int(input()), int(input()) matrix = [list(map(int,input().split())) for _ in range(a)]
Для этого я использовал мини-и макс. Я помещаю строки в максимальное количество, потому что команда хочет самую большую, затем я получаю от нее 5 лучших игроков А следующим образом:
for player, values in enumerate(matrix): maxheap.enqueue(sum(values), player) playersA = [] overallA = 0 for i in range(5): ov, pl = maxheap.remove_max() if i == 0: # it is a captain playersA.append(pl) overallA = ov playersA.append(pl) overallA = ov
Команда Б, знающая игроков А, использует Минную кучу, чтобы найти своих лучших 5 игроков:
for i in range(b): player = [] ov = 0 for j in range(a): #take out a column of a matrix player.append(matrix[j][i]) for rival in playersA: #counting only players already chosen by A ov = player[rival] minheap.enqueue(ov,i) playersB = [] overallB = 0 for i in range(5): ov, pl = minheap.remove_min() if i == 0: playersB.append(pl) overallB = ov playersB.append(pl) overallB = ov
Имея игроков, я затем подсчитываю сумму из матрицы:
out = 0 for a in playersA: for b in playersB: out = matrix[a][b] print(out)
Однако это решение не всегда дает правильные решения. Например, это делается для ввода:
10 10 -802 -781 826 997 -403 243 -533 -694 195 182 103 182 -14 130 953 -900 43 334 -724 716 -350 506 184 691 -785 742 -303 -682 186 -520 25 -815 475 -407 -78 509 -512 714 898 243 758 -743 -504 -160 855 -792 -177 747 188 -190 333 -439 529 795 -500 112 625 -2 -994 282 824 498 -899 158 453 644 117 598 432 310 -799 594 933 -15 47 -687 68 480 -933 -631 741 400 979 -52 -78 -744 -573 -170 882 -610 -376 -928 -324 658 -538 811 -724 848 344 -308
Но это не для
11 11 279 475 -894 -641 -716 687 253 -451 580 -727 -509 880 -778 -867 -527 816 -458 -136 -517 217 58 740 360 -841 492 -3 940 754 -584 715 -389 438 -887 -739 664 972 838 -974 -802 799 258 628 3 815 952 -404 -273 -323 -948 674 687 233 62 -339 352 285 -535 -812 -452 -335 -452 -799 -902 691 195 -837 -78 56 459 -178 631 -348 481 608 -131 -575 732 -212 -826 -547 440 -399 -994 486 -382 -509 483 -786 -94 -983 785 -8 445 -462 -138 804 749 890 -890 -184 872 -341 776 447 -573 405 462 -76 -69 906 -617 704 292 287 464 -711 354 428 444 -42 45
Итак, вопрос в следующем: можно ли это сделать так или есть другой быстрый алгоритм ( O(n ** 2 ) / O(n ** 3) и т. Д.), Или я просто дал попробовать все возможные комбинации, используя грубую силу в O(n!) временной сложности?
Комментарии:
1. всегда ли каждая команда выбирает ровно 4 игрока 1 капитана, или это зависит от общего количества игроков в каждой команде?
2. Может ли любой игрок быть назначен капитаном?
3. @AnneAunyme да, они всегда выбирают 5 игроков — 4 1.
4. @itprorh66 да, может.
5. Вы поняли, почему ваш алгоритм не дал оптимального результата, или вы хотели бы получить объяснение этому?
Ответ №1:
Есть способ сделать это с полиномиальной сложностью.
Чтобы показать вам, почему ваше решение не работает, давайте рассмотрим другую, более простую проблему. Допустим, каждая команда выбирает только 2 игроков, а капитана нет.
Давайте также возьмем простую матрицу оценок:
1 1 1 2 1
1 1 1 1 1
0 3 0 2 0
0 0 0 0 4
0 0 0 0 4
Здесь вы можете видеть, что у команды А нет шансов на победу (так как отрицательных чисел нет), но все равно они будут стараться изо всех сил. Кого они должны выбрать?
Используя ваш алгоритм, команда А должна выбрать своих лучших игроков, и их рейтинг будет:
pa0 lt; pa1 = pa2
Если они выберут pa3 и pa4, у которых у обоих 4 балла (что плохо, но не так плохо, как у pa0 6 баллов), команда B выиграет на 8 (они выберут pb4 и другого игрока, который не имеет значения).
С другой стороны, если команда A выбрала pa0 и pa1 (которые хуже, чем pa3 и pa4 по вашему показателю), лучшая команда B может выиграть на 5 (если они выберут pb3 и любого другого игрока).
В принципе, ваше приближение не учитывает, что команда B может выбрать только двух игроков и, следовательно, не может воспользоваться слабостью pa0 pa1, в то время как она может легко использовать слабость pa3 pa4.
Лучшим решением для команды А было бы оценить результат каждого игрока только с учетом их 2 худших результатов (или 5, если необходимо выбрать 5 игроков): это сделало бы рейтинг как таковой:
pa2 lt; pa3 = pa4 lt; pa0
Тем не менее, это было бы приближением: некоторые комбинации, такие как pa2 pa3, на самом деле не так плохи, как кажутся, поскольку, опять же, слабые места достаточно распространены, чтобы команда B не могла использовать их все (хотя для этого самого примера приближение дает лучший результат).
Что нам действительно нужно выбрать, так это не двух лучших игроков, а лучшую комбинацию из двух игроков, и, к сожалению, я не знаю другого способа, кроме как попробовать все комбинации $s!/(k!(s-k)!)$ из k игроков среди s (размер команды). Это не так уж и плохо, хотя, как для K=2, что только $Х*(Х-1)/2$ и для K=5, что $Х*(Х-1)(х-2)(х-3)*(х-4)/5!$, что еще полиномиальной сложности несмотря на то, что в О(С^5). Добавление капитана в микс только умножает количество комбинаций на k. Это также требует изменений в том, как рассчитать счет, но вы должны быть в состоянии это найти.
Теперь, когда команда А выбрала своих игроков, команде В будет легко выбрать своих. Это намного проще, так как здесь каждый игрок может быть выбран индивидуально.
пример того, как этот последний алгоритм должен работать с матрицей оценок, приведенной в начале.
у команды A есть 10 возможных комбинаций: pa0 pa1, pa0 pa2, pa0 pa3, pa0 pa4, pa1 pa2, pa1 pa3, pa1 pa4, pa2 pa3, pa2 pa4, pa3 pa4. Их соответствующие баллы равны: 5, 8, 7, 7, 7, 6, 6, 7, 7, 8.
Лучшая комбинация-pa0 pa1, так что это то, что они посылают команде B.
Команда B подсчитывает счет каждого своего игрока против pa0 pa1: pb0:2, pb1:2, pb2:2, pb3:3, pb4:2. pb3 является лучшим, все остальные равны, поэтому команда B отправляет pb3 pb4 (например), и «ответ» равен 5.
Комментарии:
1. Итак, должен ли я делать это, только пробуя комбинации? Потому что последние 2 входа заняли более 10 секунд и не превысили лимит времени на тестере.
2. Вы должны попробовать все комбинации для команды А, а не общее количество комбинаций игроков в каждой команде. Как сложность O(s^5), она не будет хорошо масштабироваться, но если вы хотите быть значительно быстрее, вам придется смириться с тем, что иногда ваша программа не обеспечивает оптимального решения.
3. Итак, для каждой комбинации и капитана я использовал приоритетную очередь, чтобы выбрать 5 лучших из команды B, и это сработало 🙂 большое спасибо!