Решал эту задачу, но ловлю ТЛЕ. Идея: применим МИТМ, подсчитаем f[cnt][i, j] - количество способов добраться до точки (i, j) используя cnt операций из левой части. Затем я перебирал правую часть и обновлял ответ. Вот мой код. Разве мое решение не должно работать за
O(2 ^ \frac{n}{2} + 2^\frac{n}{2} * \frac{n}{2})? Это же \approx 0.22 секунды, но на деле ТЛЕ при лимите 4 секунды. Я прочитал разбор, там та же идея, но немного другая реализация. Что я делаю не так?
5 лайков
unordered_map <pll, int, hsh> все портит?
Может быть коллизий много, попробуй обычный мап, или gp hash table
2 лайка
и так, и так ТЛЕ
Еще я пытался reserve-ить, но тоже ТЛЕ
2 лайка
скинь код
1 лайк
У тебя очень много обращений в unordered_map 2^\frac{n}{2} * \frac{n}{2} \approx20\cdot10^6. Это много для мапы, я переписал на вектора и два указателя и решение зашло за 900мс.
2 лайка
Можешь скинуть код? Просто не совсем понимаю как писать
подумай
1 лайк
Еще у меня есть замечание к хешу. Почему у тебя hash(x, y) = x \cdot 239 + y? Тут же будет очень много коллизий.
1 лайк
Он походу с авторского взял хэш
1 лайк
Да, я изначально использовал map <ll, pll> mem[N] и после ТЛЕ решил переписать на unordered_map и у меня не компилилось. Потом я посмотрел разбор, там использовали такой хэш и я его взял.
Я написал два указателя, но теперь у меня ВА. Я создал vector <pair <pii, int> > fir, sec и перебирал координаты, а если они равны, я обновлял ответ. Можете подсказать что у меня не так?
1 лайк
Пусть у тебя в первом массиве :
{{1, 1}, 2} и {{1, 1}, 3}
и во втором массиве :
{{1, 1}, 2} и {{1, 1}, 3}
Тогда твой ответ будет неправильным.
1 лайк
Теперь когда я нахожу одинаковые координаты, я записываю все левые cnt в v1, а все правые в v2, а затем обновляю ответ. Теперь у меня ТЛЕ на 5 и 16 тестах. Прикольно, что именно эти тесты у меня проходили с unordered_map) Как обновлять ответ быстрее?
2 лайка
Ну подумай о том как работать с этим эффективней?
Если у тебя все элементы равные будут то у тебя это будет работать за O(2^n), попробуй подумать как исправить ситуацию
Сдал. Спасибо.
1 лайк
Понимаешь почему это решение зашло?
Скажи асимптотику
Да, потому что когда я кладу в мапу, в m1 и m2 будет не более 20 значений
O(2 ^ \frac{n}{2} * \frac{n}{2} + 2^\frac{n}{2} * \frac{n}{2}) чтобы посчитать в начале и O(2 * 2^\frac{n}{2} + (\frac{n}{2})^2) чтобы пройтись двумя указателями. Правильно?
1 лайк
А сколько действий в итоге будет примерно в проге?
Если n = 40, то 4 * 10^7 примерно
1 лайк
Почему + (n/2)^2
Потому что мы примерно столько раз в сумме перебираем все элементы в m1 и m2, нет? В начале я написал * (\frac{n}{2}) ^ 2, но мы же не перебираем \frac{n}{2} элементов каждый сдвиг в двух указателях
1 лайк