понедельник, 10 мая 2010 г.

1002. Телефонные номера (ДП) [acm.timus.ru]

[Условие]

Основная идея:
Всю задачу можно разделить на 3 этапа:
1) Хранение данных
Каждое слово из словаря необходимо хранить как в цифровом, так и в буквенном варианте
.
Для слова “our” цифровое представление будет равно “087”. При этом необходимо иметь связь между между обоими представлениями для получения ответа. Один из вариантов хранения такого представления можно описать в виде структуры, а весь словарь в виде массива элементов таких структур:

  1. struct word
  2. {
  3.   string str;      // буквенное представление
  4.   string digits;   // цифровое представление
  5. };
  6. vector<word> dict; // словарь

По условию задачи длина каждого слова не превышает 50 символов. Тогда, вся структура word будет иметь размер в худшем случае 2*50=100 байт. Забегая вперед отметим, что по ходу решения нужно будет хранить словарь в отсортированном виде. При сортировке самая тяжеловесная операция – это обмен двух элементов местами. Поэтому есть предложение модифицировать нашу структуру для ускорения этой операции. Будем хранить в структуре не всю строчку в буквенном представлении, а только указатель на него.

  1. struct word
  2. {
  3.   string digits;
  4.   int id;
  5.   word(){}
  6.   word(string Digits, int Id)
  7.   {
  8.     digits = Digits;
  9.     id = Id;
  10.   }
  11. };
  12. vector<string> hash;
  13. vector<word> dict;

Строковое представление слова храним в массиве hash, а в качестве id(указатель на строковое представления) храним индекс в массиве hash. При таком раскладе сортировка массива dict будет проходить быстрее, но в памяти будет храниться лишние 4 * N байт, где N – количество слов в dict.

2) Динамическое программирование
Для получения ответа заведем два массива last и amount, при этом:
last[i] – это номер слова из словаря, на которое заканчивается оптимальная комбинация слов при составлении начала исходного номера, начиная от 0-ого символа и заканчивая i-ым. (по умолчанию -1)
amount[i] – это количество слов в оптимальной комбинации, заканчивающейся i-ым символом. (по умолчанию infinity)
Наша задача последовательно заполнить массивы last и amount. При этом если последний элемент массива last равен –1, то можно с уверенностью сказать, что исходный номер нельзя представить в виде комбинации слов из словаря.
Детали реализации см. исходник (функция findAnswer)

3) Получение ответа
Рассмотрим массивы last и amount для первого теста:

index  = {  0,  1,  2,  3,  4,  5,  6,  7,  8,  9}
last   = { -1, -1, -1,  3, -1,  0,  2, -1, -1,  4}
amount = {inf,inf,inf,  1,inf,  2,  1,inf,inf,  2}

Ответ формируем с конца.
3.1) Текущий индекс = 9. Последнее слово ответа имеет id = 4. Это слово “our”.
3.2) id предыдущего слова хранится левее на расстоянии длины текущего слова по индексу 6, т.е. id = 2. Это слово “reality”.
3.3) После выполнения шага 3.2) мы находимся в –1 индексе. Это сигнализирует о том, что ответ найден. Выводим его без лишних пробелов

[Исходный код]

6 комментариев:

  1. it = lower_bound(dict.begin(),dict.end(),curStr);

    Можно искать на за O(log n), а за O(1), используя алгоритм Ахо-Корасика http://e-maxx.ru/algo/aho_corasick

    ОтветитьУдалить
  2. А вообще спасибо за блог, очень интересный!

    ОтветитьУдалить
  3. Здравствуйте. А вы не могли бы снова выложить решение задачи? Ссылка с решением не работает.

    ОтветитьУдалить