ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1590. Шифр Бэкона

Can we use hashes?
Послано Khamitbekov Madi 6 апр 2011 22:59
Can we solve this problems with hashes?
It takes TLE #3 with hash table...
Who solved with hashes, comment please =)
Re: Can we use hashes?
Послано George_Aloyan[PTSObninsk] 21 окт 2011 15:21
I tried, but i didn't use tables. Just calculated the number of different hashes. But I have WA3. And it seems quite interesting to me.
Re: Can we use hashes?
Послано vlyubin 9 фев 2012 07:10
George_Aloyan[PTSObninsk] писал(a) 21 октября 2011 15:21
I tried, but i didn't use tables. Just calculated the number of different hashes. But I have WA3. And it seems quite interesting to me.

Why do you think that you could avoid hash collisions?
There could be 5000*5000/2 different substrings and if your hash size (modulo you are using) is less than that, some two will DEFINITELY be in the same section and they could be unequal. Even if your number is greater, you still can get WA because of a collision ...