Найти пропущенную перестановку

Question

Эта проблема была предложена Google на недавнем раунде коджем, и он до сих пор не дает покоя, как мне не удалось ее решить. пожалуйста, покажи мне, как это можно сделать:

Иди, иди, Power Arrangers! Все любят эту команду из пяти супергероев старшеклассники, которые носят буквы A, B, C, D и E. Когда они стоять бок о бок, чтобы противостоять злым монстрам, они устраивают свою команду в одном из 120 возможных различных ордеров слева направо, давая им различные разные тактические суперспособности. Они еще популярнее чем черепашки-ниндзя!

Некоторые критики шоу утверждают, что команда имеет только свое расположение трюк, чтобы владельцы шоу могли продать 120 отдельных наборов из 5 фигурки действий, каждая из которых представляет команду в разных порядок слева направо, приклеенный к основанию, так что набор не может быть переставить. Как заядлый фанат Power Arrangers, вы собрали 119 эти наборы, но вы не помните, какой набор вам не хватает. Ваш 119 комплектов выстроены горизонтально вдоль полки, так что есть всего 119 × 5 = 595 фигур в порядке слева направо. Ты сделаешь не помню, как устроены наборы, но вы знаете, что перестановка множеств выбирается равномерно случайным образом из всех возможные перестановки и независимо для каждого случая.

Вы не хотите тратить время на выяснение, какой набор вы отсутствует, поэтому вы планируете смотреть на буквы не более F цифр на полка. Например, вы можете посмотреть на письмо на восьмая цифра слева, которая будет третьей цифрой из слева во втором сете слева. Глядя на фигуру, вы получить только письмо от этой фигуры; буквы трудно увидеть, и разные члены команды выглядят очень похоже в противном случае!

После проверки не более F цифр, вы должны выяснить, какая из наборы отсутствуют, так что вы можете завершить свою коллекцию и быть готовым к противостоять любой возможной злой угрозе!

Вход и выход

Это интерактивная проблема. Вы должны убедиться, что вы прочитали информация в разделе «Интерактивные проблемы» нашего FAQ.

Первоначально ваша программа должна читать одну строку, содержащую два целые числа T, количество тестов и F, количество цифр, которые вы разрешено проверять в каждом тестовом случае. Затем вам нужно обработать T-тест случаи.

В каждом тестовом примере отсутствующий набор цифр выбирается равномерно случайным образом из всех возможных наборов, и порядок оставшихся наборов также выбирается случайным образом из всех возможных заказов. каждый выбор сделан независимо от всех других вариантов и ваших данных.

В каждом тестовом случае ваша программа будет обрабатывать до F + 1 обменов с нашим судьей. Вы можете сделать до F обменов следующей формы:

• Ваша программа выводит одну строку, содержащую одно целое число от 1 до 595 включительно, указывающее, какая цифра (слева направо вдоль полки) вы хотите посмотреть. В качестве еще одного примера, 589 будет представляют четвертую фигуру слева во втором наборе из правый.
• Судья отвечает одной строкой, содержащей одну заглавную букву A, B, C, D или E, обозначающую букву на этом рисунке. если ты отправил недействительные данные (например, номер вне диапазона или неверно сформированная строка), вместо этого судья ответит одной строкой, содержащей заглавная буква N.

Затем, после того, как вы сделали столько F обменов, сколько вы хотите, вы должны сделать еще один обмен следующей формы:

• Ваша программа выводит одну строку, содержащую одну строку из пяти заглавных букв: перестановка, соответствующая отсутствующему набору (например, CADBE).
• Судья отвечает одной строкой, содержащей одну заглавную букву: Y, если ваш ответ был правильным, и N, если он не был (или вы при условии неправильной линии). Если вы получаете Y, вы должны начать следующий тестовый пример, или прекратите отправку ввода, если больше нет тестовых случаев.

После того, как судья отправит N в ваш входной поток (из-за неверные данные или неправильный ответ), он не будет отправлять другие выход. Если ваша программа продолжает ждать судью после Получив N, ваша программа истечет время ожидания, что приведет к ограничению времени Превышена ошибка. Обратите внимание, что вы несете ответственность за программа завершается вовремя, чтобы получить неправильный ответ вместо Ошибка превышения лимита времени. Как обычно, если предел памяти превышен, или ваша программа получит ошибку во время выполнения, вы получите соответствующий суждение. Ограничения

1 ≤ T ≤ 50. Ограничение по времени: 40 секунд на тестовый набор. Ограничение памяти: 1 ГБ. Отсутствующий набор и порядок остальных наборов выбираются равномерно и независимо наугад. Тестовый набор 1 (Видимый)

F = 475. Тестовый набор 2 (скрытый)

F = 150.

Answer 1

Вы можете попробовать что-то вроде этого:

• использовать ваши первые 119 запросов для запроса первого элемента каждого "блока", то есть 0-го, 5-го, 10-го и т. Д. Элемента
• посчитайте, как часто вы находите каждую букву и где;должно быть 24 перестановки для каждой начальной буквы, но для одной только 23
• продолжите с этими 23 перестановками и запросите вторую букву этих блоков, например, если начальные позиции этих были 15, 40, 60, ..., запросите 16-ю, 41-ю, 61-ю, ... букву
• еще раз, посчитайте, как часто вы находите каждую вторую букву;должно быть 6 для каждого, но для одной буквы есть только 5
• , продолжайте с этими 5 и запрашивайте третью букву из них;для одной из них будет только одна перестановка вместо двух
• , теперь вы знаете первые три буквы отсутствующей перестановки;сделайте последний запрос для четвертой (или пятой) буквы этой единственной перестановки с теми же первыми тремя цифрами из последнего шага, и вы сможете вывести последние две цифры недостающей перестановки

Таким образомвам понадобится 119 + 23 + 5 + 1 = 148 запросов, чтобы найти отсутствующую перестановку.

Пример реализации в Python:

import itertools, random, collections
permutations = list(itertools.permutations("ABCDE"))
random.shuffle(permutations)
permutations.pop()
flat_permutations = [c for p in permutations for c in p]

queries = 0
candidates = [i * 5 for i in range(119)]
missing = ""
for i in [0, 1, 2, 4]:
    where = collections.defaultdict(list)
    for t in candidates:
        queries += 1
        c = flat_permutations[t + i]
        where[c].append(t)
    c, candidates = min(where.items(), key=lambda item: len(item[1]))
    missing += c

# we queried for the 5th and used it as 4th in 'missing'
missing += next(c for c in "ABCDE" if c not in missing)

print("queries", queries)
print("missing", missing)
print("correct?", tuple(missing) not in permutations)

Это всегда найтиотсутствует перестановка, но она также будет всегда ¹⁾ принимать 148 запросов.

Если F меньше, вы можете просто запросить случайные позиции, а затем использовать вероятность, чтобы угадатьперестановка, которая меньше всего соответствует этим предположениям.

---

¹⁾ Технически, вы могли бы найти его с меньшим количеством запросов, например, если вам очень повезло и после 100запросов у вас уже есть 4 буквы с 24 позициями в каждом, вам не нужно делать последние 19 запросов, но это будет чистой удачей, и шансы на это довольно малы.