Всем привет!
Вот и закончился Codeforces Round #261. Решая задачу 459D - Задача Пашмака и Пармиды у меня возник очень интересный баг. Делал я задачу с помошью дерева Фенвика, код — 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.
И всё же, багом назвать такое нельзя.
С первого взгляда, конечно, разница незаметна, и списать различие можно разве-что на причуды оптимизатора. Но, внезапно, вы написали Фенвика на мэпе (хотя зачем, ведь частота не превышает количества элементов в массиве?). Следственно меняется порядок добавления чисел в дерево (которое внутри map'а): от меньших к большим, или наоборот. А это уже может повлиять на внутреннюю работу структуры, например, увеличить количество вращений.
В общем, предугадать такое нельзя, но и удивляться особо не стоит =)
Я ожидал в приблизительный ответ, но 33 тест такой: n=1000000, а все а[i]=1. То есть все а[i] одинаковы.
Но вы добавляете не a[i], а s[i], то-есть накопленные частоты. А они как раз возрастают: 1 2 3 4 5 ...
Если точнее, то в мэп добавляются числа, по которым шагает Фенвик, но для них соответствующая монотонность тоже наблюдается.
Ах да, точно. Приношу извинения
ВЫНОСЛИВОСТЬ: УЛУЧШЕНО. ТЕПЕРЬ ТЫ МОЖЕШЬ БЕГАТЬ, ПЛАВАТЬ И ВРАШАТЬСЯ ДОЛЬШЕ
Раз уж подняли тему про map, хочу спросить. Если у нас есть мап <X, Y> и мы интересуемся значением мапа на объекте Х, для которого не определено значение, то для этого используется конструктор по умолчанию для Y?
Именно так.
cppreference
(the element is constructed using its default constructor)
Но я все же использую
map::count
для проверки существования ключа.Что-то подобное частенько бывает.. В задаче 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. Обвал решения на последнем тесте — жестоко...
Та да, последний тест... Но зато теперь я узнал, что есть существенная разница в порядке добавления чисел в мэп. Добавление чисел в мэп в порядке их увеличения работает на много быстрее чем по убыванию.
кстати есть такой трюк. В коде из посылки
в цикле идет по 2 обращения к мапе. Но можно обойтись и одним, ведь оператор
[]
возвращает ссылку:вот этот код тоже лучше переписать:
t[v]
вставляет в мапу элементы с нулевыми значениями. Лучше использовать итераторы:"t[v] вставляет в мапу элементы с нулевыми значениями"
В самом деле вставляет? Было бы грустно.
да, и из-за этого очень часто получаются TLE.
-- выведет 10
Иначе не получилось бы вернуть ссылку, чтобы туда можно было записать. А оператор на чтение и запись только один.
s[i]=++mp[a[i]];
тогда уж, не?Тоже хотел задать вопрос про особенность структур данных в С++.
Почему данный код валится по времени, а этот проходит все тесты? Multiset так долго работает?
Возможно потому, что count в нём работает за линию.
Сложность функции count в мультисете — логарифм от размера множества + линия от количества совпадений.
Следственно, у вас квадрат.
Замена map на unordered_map делает ОК ваше ТЛ решение.
http://codeforces.net/contest/459/submission/7494177
Асимптотика уменьшилась в log раз, ибо unordered_map амортизировано работает за О(1).
Я боюсь, unordered_map (aka хеш-таблица) не дает амортизированной оценки.
Почему же? http://www.cplusplus.com/reference/unordered_map/unordered_map/operator[]/ Average case: constant.
UPD Приношу извинения, не подумал что среднее время и амортизированное — это разные вещи.