Блог

Мне дана таблица команд 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!) временной сложности?

Есть способ сделать это с полиномиальной сложностью.

Чтобы показать вам, почему ваше решение не работает, давайте рассмотрим другую, более простую проблему. Допустим, каждая команда выбирает только 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.