Я пытаюсь решить проблему, описанную в моем вопросе: алгоритм покорения
Для этого расширения известно, что на мероприятии присутствуют представители 3 сторон, и 1 сторона посещает больше участников, чем любая другая. Формальное описание проблемы можно найти ниже.
Вам дано целое число n. Существует скрытый массив A размера n, содержащий элементы, которые могут принимать 1 из 3 значений. Существует значение, пусть это будет m, которое встречается в массиве чаще, чем 2 других значения.
Допустимы запросы вида Introduction(i, j), где i≠j, и 1 ‹= i , j ‹= n, и в ответ вы получите логическое значение: вы вернете 1, если A[i] = A[j], и 0 в противном случае.
Вывод: B ⊆ [1, 2. . .. n], где A-значение каждого элемента в B равно m.
Решение грубой силы может вычислить B за O(n2), вызвав Introduction(i, j) для n(n-1) комбинаций элементов и создать 3 списка, содержащих A-индексы элементов. элементы, для которых была возвращена 1, когда для них была вызвана команда, возвращающая список наибольшего размера.
Я понимаю алгоритм голосования Бойера-Мура, но не может найти способ изменить его для этой проблемы или найти эффективный алгоритм для ее решения.
