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

Забавный баг по задаче D (Round #261)
Автор PashaChemerys, 10 лет назад, По-русски

Всем привет!

Вот и закончился Codeforces Round #261. Решая задачу 459D - Pashmak and Parmida's problem у меня возник очень интересный баг. Делал я задачу с помошью дерева Фенвика, код — 7476143. У меня был тайм лимит на 33 тесте. Долго просидев за кодом и сравнением его с чужими решениями, я так и не понял в чем проблема. Прошу обратить внимание на вот эти две строчки в моем коде: 

for (i=2;i<=n;i++)
        add(s[i],1);

Процедура add прибавляет единицу с позиции s[i]. Случайным образом мне пришла мысль написать вот так:

for (i=n;i>1;i--)
        add(s[i],1);

Разницы казалось бы не какой, но с этой "оптимизацией" у меня — Полное решение. Причем разница в некоторых тестах одна секунда! Почему так произошло?

Вот кода для сравнения(певый — ТЛ, второй — ОК): 7476143 и 7476106.

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

»
10 лет назад, # |
← Rev. 4   Проголосовать: нравится +22 Проголосовать: не нравится

И всё же, багом назвать такое нельзя.

С первого взгляда, конечно, разница незаметна, и списать различие можно разве-что на причуды оптимизатора. Но, внезапно, вы написали Фенвика на мэпе (хотя зачем, ведь частота не превышает количества элементов в массиве?). Следственно меняется порядок добавления чисел в дерево (которое внутри map'а): от меньших к большим, или наоборот. А это уже может повлиять на внутреннюю работу структуры, например, увеличить количество вращений.

В общем, предугадать такое нельзя, но и удивляться особо не стоит =)

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

    Я ожидал в приблизительный ответ, но 33 тест такой: n=1000000, а все а[i]=1. То есть все а[i] одинаковы.

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
      ← Rev. 4   Проголосовать: нравится +7 Проголосовать: не нравится

      Но вы добавляете не a[i], а s[i], то-есть накопленные частоты. А они как раз возрастают: 1 2 3 4 5 ...

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

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

    увеличить количество вращений.

    ВЫНОСЛИВОСТЬ: УЛУЧШЕНО. ТЕПЕРЬ ТЫ МОЖЕШЬ БЕГАТЬ, ПЛАВАТЬ И ВРАШАТЬСЯ ДОЛЬШЕ

    → Ответить
»
10 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Раз уж подняли тему про map, хочу спросить. Если у нас есть мап <X, Y> и мы интересуемся значением мапа на объекте Х, для которого не определено значение, то для этого используется конструктор по умолчанию для Y?

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

    Именно так.

    cppreference (the element is constructed using its default constructor)

    Но я все же использую map::count для проверки существования ключа.

    → Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

Что-то подобное частенько бывает.. В задаче Div1 A на поиск точек прямоугольного треугольника по длине катетов (у которого все стороны не параллельны осям X и Y) мне помогло пройти упавшее решение изменение в коде — из for(int x = -1; x >= -1000; x--) в (int x = 1; x <= 1000; x++), так как возможно два ответа когда известны две точки треугольника, хотя потом я понял, что это не баг, а просто не попался тест, ответом на который будет что-то вроде

0 0 -12 -16 -12 9

Т.е. как в первом решении Х)

P.S. Обвал решения на последнем тесте — жестоко...

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

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

    → Ответить
»
10 лет назад, # |
← Rev. 4   Проголосовать: нравится +8 Проголосовать: не нравится

кстати есть такой трюк. В коде из посылки

for (i=n;i>0;i--)
{
    mp[a[i]]++;
    s[i]=mp[a[i]];
}

в цикле идет по 2 обращения к мапе. Но можно обойтись и одним, ведь оператор [] возвращает ссылку:

for (i=n;i>0;i--)
{
    int& it = mp[a[i]];
    s[i]= ++it;
}

вот этот код тоже лучше переписать:

while (v>0)
{
    s+=t[v];
    v=(v & (v+1))-1;
}

t[v] вставляет в мапу элементы с нулевыми значениями. Лучше использовать итераторы:

while (v>0)
{
    map<int, int>::iterator it = t.find(v);
    if (it != t.end()) s+=it->second;
    v=(v & (v+1))-1;
}
→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    "t[v] вставляет в мапу элементы с нулевыми значениями"

    В самом деле вставляет? Было бы грустно.

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

      да, и из-за этого очень часто получаются TLE.

      map<int, int> mp;
for (int i = 0; i < 10; ++i) mp[i];
cout << mp.size() << '\n';

      -- выведет 10

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

      Иначе не получилось бы вернуть ссылку, чтобы туда можно было записать. А оператор на чтение и запись только один.

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

    s[i]=++mp[a[i]]; тогда уж, не?

    → Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Тоже хотел задать вопрос про особенность структур данных в С++.

Почему данный код валится по времени, а этот проходит все тесты? Multiset так долго работает?

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

    Возможно потому, что count в нём работает за линию.

    → Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

    Сложность функции count в мультисете — логарифм от размера множества + линия от количества совпадений.

    Следственно, у вас квадрат.

    → Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Замена map на unordered_map делает ОК ваше ТЛ решение.

http://mirror.codeforces.com/contest/459/submission/7494177

Асимптотика уменьшилась в log раз, ибо unordered_map амортизировано работает за О(1).

→ Ответить