Блог пользователя HolkinPV

Codeforces Beta Round #33. Разбор B
Автор HolkinPV, 14 лет назад, По-русски
Решение предполагалось следующее: во первых, если длины строк не совпадали, то ответ очевидно -1. В противном случае для каждой позиции переберём букву, которую будем на нее ставить. Чтобы быстро узнать, в какую стоимость эта операция нам обойдется предподсчитаем матрицу размера Z[26][26], где в клетке (i, j) будет записана минимальная цена перехода из i-ой буквы алфавита в j-ую. Для этого воспользуемся, например, алгоритмом Флойда. Если по причине отсутствия переходов в какой то позиции в строке мы не найдем хотя бы одной подходящей буквы, то выводим -1. Иначе суммируем ответ, и выводим получившуюся строку. 
  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I created a 2d Graph and did a simple Floyed to relax all the edges as explained .. then looped on the Strings and every time I found two characters don't match I try to find Min(graph[a][k]+graph[b][k]), where 0<=k<=25 ,and 'a' ,'b' is the character in the first ,second String respectively. 

However I'm getting a TLE on case 26 :/ .. 

any clue ? .. 

here's my code : 
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Use StringBuilder to construct the final result. Usage of += with the String is a slow operation.
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    My friends had TL on case 26 but because of the different string error.
    He used C-style strings char* and in the loop he wrote strlen(s).
    Don't do this because this operation costs O(length of the string).
    C++-style strings are more convenient for this case and s.size() is OK.
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Or just store the strlen(s) in a variable.
      Char array is faster than the C++ string, so I suggest you to use it when you can.
      → Ответить
14 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Валится на 10 тесте, если забивать в матрицу Z 10^9...
Если 10^7, то все проходит...
Может кто-нибудь объяснить в чем трабл? Вроде за пределы инта не выходит...
http://pastebin.com/690Re1Rf
Подскажите почему при INF == 10^9 вылетает 10 тест)
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Не заметил как исправил флойда >_<
стыдно(
вопрос снят, учусь писать флойда)
→ Ответить