Неоднозначность в проблеме CodeForces - использование HashSet против LinkedHashSet

Question

Вчера я решал задачу Codeforces. URL-адрес проблемы: this

Я просто коротко объясню вопрос ниже.

Учитывая двоичную строку, разделите ее на минимальное количество подпоследовательностей в таким образом, что каждый символ строки принадлежит ровно одной подпоследовательности, и каждая подпоследовательность выглядит как «010101 ...» или «101010 ...» (т.е. подпоследовательность не должна содержать двух соседних нулей или единиц).

Итак, по этой проблеме я вчера представил решение во время конкурса. Это решение . Он был временно принят, и в финальных тестовых примерах был получен статус Превышен лимит времени .

Итак, сегодня я снова представил другое решение , и оно прошло все случаи *. 1019 *

В первом решении я использовал HashSet, а во втором - LinkedHashSet. Я хочу знать, почему HashSet не очистил все случаи? Означает ли это, что я должен использовать LinkedHashSet всякий раз, когда мне нужна реализация Set? Я видел эту статью и обнаружил, что HashSet работает лучше, чем LinkedHashSet. Но почему мой код здесь не работает?

Answer 1

Этот вопрос, вероятно, получит больше ответов на Codeforces, но я все равно отвечу на него здесь.

После окончания конкурса Codeforces позволяет другим пользователям «взламывать» решения, создавая собственные входные данные для запуска на других пользовательские программы. Если программа защищающегося пользователя медленно работает с пользовательским вводом, статус отправки кода изменится с «Принято» на «Превышен лимит времени».

Причина, по которой ваш код, в частности, изменился с «Принято» на «Превышен лимит времени» означает, что кто-то создал «тест anti-ha sh» (тест, при котором ваша функция ha sh приводит к множеству коллизий), на котором ваша программа работает медленнее, чем обычно. Если вам интересно, как генерируются такие тесты, вы можете найти несколько сообщений на Codeforces, например: https://codeforces.com/blog/entry/60442.

По ссылке @Photon, есть сообщение на Codeforces объясняет, почему вам следует избегать использования Java .HashSet и Java .HashMap: https://codeforces.com/blog/entry/4876, что в основном связано с тестами anti-ha sh. В некоторых случаях добавление дополнительного коэффициента log(n) из сбалансированного BST может быть не так уж и плохо (с использованием TreeSet или TreeMap). Во многих случаях дополнительный коэффициент log(n) не приведет к тайм-ауту вашего кода и даст вам защиту от тестов anti-ha sh.

Как вы определяете, достаточно ли быстр ваш алгоритм, чтобы добавить коэффициент log(n)? Я предполагаю, что это приходит с некоторым опытом, но большинство людей предлагают провести какой-то расчет. Большинство онлайн-судей (включая Codeforces) показывают время, в течение которого вашей программе разрешено запускаться для решения конкретной проблемы (обычно от одной до четырех секунд), и вы можете использовать 10^9 операций с постоянным временем в секунду в качестве практического правила, когда выполнение расчетов.