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

Автор 1dayac, 12 лет назад, По-русски

Привет! Около полугода назад я начал заниматься олимпиадным программированием серьезно, перейдя из математики, в этом сезоне уже начали бороться за победу в ДФО, но суть не об этом. Что на полуфинале, что на отборе Всесиба не смогли решить задачи на строки, которые немалая часть команд решает без проблем (задача H на полуфинале и задача A на отборе Всесиба). Придумать самостоятельно решение задач лучше чем за квадрат я не смог, но из разборов понял что используются для решения мапы или хэшмапы. Хочется попросить немного подробнее объяснить подобные задачи, если можно дать ссылку на теорию или главу книги где бы это обсуждалось, ну и ссылки на задачи кодфорсес на похожие темы. Заранее спасибо

  • Проголосовать: нравится
  • +19
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Трудно понять что вы имеете в виду (самая типовая задача очевидно найти дублирующие строки за примерно O(N)). Однако я вижу что на популярном сайте даже целый раздельчик есть:

http://e-maxx.ru/algo/string_hashes

»
12 лет назад, # |
Rev. 6   Проголосовать: нравится +3 Проголосовать: не нравится

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

В А отбора всесиба был такой смысл хешей — проще посчитать хеш от строки и пихнуть его в меп, чтобы потом при сравнении они сравнивались за О(1), а не как строки за О(длина строки), + занимали меньше места. Т.е. смотря на текущую (под)строку посчитаем ее хеш, если нашли его в мепе, значит строка как бы уже встречалась. Но может и не эта строка, а строка с таким же хешем, но другая — этот случай называется коллизией.

В H в мепе хранилась маска четности для букв из префикса (от 0..52), что влезает в long long (там 64 бита). К строковым хешам это явление не относится, но хешмеп для более оптимального хранения тут пригодится.

Помимо обычного мепа (например std::map и прочих основанных на сбалансированных бинарных деревьях) существует хеш-меп (или хеш-таблица). Делается так — берем массив hashtable какого-то размера P и считаем хеш сначала как угодно, а потом берем результат по модулю P и пихаем или сам элемент, или его хеш в hashtable[hash(str) % P]. Теперь, на запрос "есть ли строка в массиве" мы можем сказать, что ее точно нет, если hashtable[hash(str) % P].size() == 0. Иначе, нам надо проверить, именно наша ли строка там есть — проходом или бинпоиском, если поддерживать его отсортированным. Понятно, что тут возможно куча эвристик и шаманств типа дополнительных хешей и т.д. Например, в отборовсесибской А я пропихнул решение с двумя разными хешами ) один был для хеш-таблицы, поменьше, а другой, большой, для хранения в хештаблице. Хешмап круто использовать, когда у вставляемых в мап элементов коллизии довольно редкие.

Надеюсь, понятно объяснил ) + автор комментария выше кинул правильную ссылку на емакс, а его заминусовали О_о

Можешь вот эту задачу пропихнуть хеш-таблицей, точно разберешься)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Кажется, я начинаю кое-что понимать, спасибо большое:) Сегодня сяду разбираться, наверное, что-то да получится, по крайнем мере про задачу со Всесиба кажется уже все понял

  • »
    »
    12 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Стал перерешивать задачу A с отбора Всесиба, получил TL14 с таким кодом: ~~~~~

    //map<long long, vector<pair<int,int>>> mymap;
    vector<vector<pair<long long,pair<int,int>>>> hashtable(30000);
    const long long Prime = 29633;
    int main()
    {   
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
        string st = "";
        cin>>st;
        int numberof1 = 0;
           int numberof2 = 0;
           for(int i = 0; i<st.length(); i++)
           {
             if(st[i]=='0')
              numberof2++;
             else
              numberof1++;
           }
    
           int lala = min(numberof1,numberof2);
                //Считали строку и определили максимально возможный в теории ответ
        int answer = 0;
        const int p = 29;
        vector<long long> p_pow (10000);
        p_pow[0] = 1;
        for (size_t i=1; i<p_pow.size(); ++i)
           p_pow[i] = p_pow[i-1] * p;
                //Как на сайте e-maxx посчитали степени для хэша
        int n = st.length();
        for(int i = 0; i<n; i++)
        {
    
           long long hash1 = 0;
           for(int j = i; j<min(n,i+lala); j++)
           { 
           hash1 += (st[j] - '0' + 1) * p_pow[j-i];
           int u = abs((int)(hash1%Prime));
           hashtable[u].push_back(make_pair(hash1, make_pair(j-i, i)));
                       //Все запихнули в хэш-таблицу (хэш, длина подстроки, индекс первого элемента)
           } 
        }
    
        for(int i = n-1; i>=0; i--)
        {
    
           long long hash2 = 0;
           for(int j = i; j>=max(0, i-lala); j--)
           { 
             int p = 0;
              if(st[j]=='0')
              {
                  p='1';
              }
              else
                  p='0';
    
           hash2 += (p - '0' + 1) * p_pow[i-j];
        int y = abs((int)(hash2%Prime));
           if(!hashtable[y].empty())
           {
    
             for(int z = 0 ; z<hashtable[y].size(); z++)
             {
               //Если хэш совпадает, подстроки не пересекаются, то пересчитываем ответ.
    
             if(hash2==hashtable[y][z].first&&hashtable[y][z].second.second+hashtable[y][z].second.first<j&&i-j==hashtable[y][z].second.first)
             {
              answer=max(answer, hashtable[y][z].second.first+1);
              break;
             }
             }
           }
    
           } 
        }
        cout<<answer;
        return 0;
    }
    

    ~~~~~

    http://pastebin.com/nCYDRv60 — код на pastebin Какие тут явные ошибки, какие недочеты можно исправить? Спасибо.

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
       for(int i = 0; i<n; i++)
          {
      
             long long hash1 = 0;
             for(int j = i; j<min(n,i+lala); j++)
             { 
             hash1 += (st[j] - '0' + 1) * p_pow[j-i];
             int u = abs((int)(hash1%Prime));
             hashtable[u].push_back(make_pair(hash1, make_pair(j-i, i)));
                         //Все запихнули в хэш-таблицу (хэш, длина подстроки, индекс первого элемента)
             } 
          }
      

      явный квадрат. во втором цикле вообще куб, поделённый на твой простой модуль

      а конструктивной критики нет — сам писать пока не пытался

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      выкинь на pastebin, не понятно ничо в форматировании

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

      edit: или не понял что ты делаешь...

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Да, получается в начале я считаю хэши за квадрат. Потом считаю хэши для обратных строк, если нахожу пару одинаковых хэшей строк с непересекающимися индексами — обновляю ответ. Неужели можно считать хэши все подстрок быстрее чем за квадрат или же можно не считать многие из них?

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          В этой задаче ограничения на длину строк до 105, пихать квадрат — не лучшая идея.

          Действительно, можно не считать многие из хешей. Как описано на емаксе, если посчитать хеши на всех префиксах строки, то после этого можно за O(1) получить хеш любой подстроки. Правда там не совсем очевидно описан один очень полезный трюк — если мы хотим сравнивать на равенство много подстрок фиксированной длины len, то есть смысл домножить хеш каждой подстроки [i..j] на pmaxn - i, чтобы равные подстроки имели равные хеши.

          Конкретно в этой задаче помогает наблюдение, что если есть ответ длины len, то будет и ответ длины len - 1, т.е. можно сделать бинпоиск по ответу. Единственное что осталось — научиться проверять, существует ли ответ длины len. Ну а для этого можно просто выписать все подстроки такой длины, отсортировать их хеши и аккуратно проверить, есть ли совпадающие. O(nlog2n) хорошо укладывается в ограничения.

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Ух ты, спасибо, от того, что недостаточно опыта не видел бинарный поиск в упор, даже когда мне внизу на него указали, думаю теперь-то я сдам задачу:)

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Как уже сказали, тут плохая ассимптотика, уж я то знаю, в дорешке сдал за +75. Ну и на самом контесте пробовал не один раз. Мысль с хеш таблицей абсолютно верная, а вот остальное хромает. Попробуй как-нибудь (спойлер)