historydev, Ну тогда это решение вполне оправдано. Но названия у него особого нет. Может быть, Хеш-таблица с кешем для итерации. В каких-то языках в стандартных библиотеках хеш-таблицы, скорее всего, прямо так и реализованы. Ибо хранить толстые объекты прямо в слабо заполненной таблице дорого. Там хранят указатели, или индексы, а сами элементы лежат где-то рядом в массиве.
Михаил, Можно что угодно разместить где угодно. Удобнее ли это будет - отдельный вопрос. И вообще, если у вас другая задачка, лучше задайте ее отдельным вопросом.
ffff567, двигаем вправо. Обрабатываем справа налево.
Смотрите код. Сдвиг происходит за счет прибавления a[current] к a[current+1] и зануления прошлой позиции. Это одновременно сдвигает элемент на место нуля вправо и объединяет пару одинаковых элементов.
Что значит, "двигать ноль"? Там же нет ничего. Но просто в этом алгоритме мы считаем, что можно значение сдвинуть, если дальше пустота (0) или такое же значение. Но для двух 0 подряд это условие выполняется. Однако двигать-то нечего, после выполнения сложения, у вас остается такой же массив в двумя нулями подряд.
Мы двигаем все числа по одному, справа-налево, пока можем. Если не можем текущее число двигать, переходим к более левому.
Ирина Грачева, Пополам делиться потому что в дп считаются оба варианта раскраски корня. Любая раскраска имеет двойника - можно все цвета инвертировать.
Но во время счета нам надо взять количество раскрасок поддерева со строго одним фиксированным цветом в корне. Например, когда мы считаем k, у нас есть k от отца. Теперь нам надо это домножить на варианты раскрасить поддерево в ребенке без изолированных вершин, но ребенок должен быть другого цвета! Поэтому берём n и делим на 2, чтобы выкинуть все варианты с совпадающим цветом.
Irina_Yurievna, Нам надо все эти диагональные пути целиком подсчитать. (кстати, не только диагональные, может быть из нижнего дерева в верхнее еще). Эти диагональные пути распадаются на 3 части: середина и 2 кусочка внутри копий дерева.
Середину мы дополнительно разбиваем на отдельные ребра и по каждому новому ребру считаем, сколько раз это ребро во всех путях встречается.
Оставшиеся концевые куски в деревьях мы в каждом дерове группируем вместе одинаковые и оказывается, что каждый кусок встречается ровно 3Y+2 раза в каждом дереве. Ну, потому что ровно столько есть вариантов выбрать второй конец пути. Вы зафиксировали кусок в дереве, выбрали любой второй конец - получили какой-то изначальный путь. От каждого этого изначального пути это кусок надо подсчитать. Дальше, эти 3Y+2 можно вынести за скобки и в каждом дереве остается сумма всех путей от угла - т.е. X.
Irina_Yurievna, X - это пути от угла дерева, а не все пути. Все пути мы считаем в answer. Но в процессе подсчета мы заметили, что куски новых путей можно сгруппировать и там вылезает как раз сумма путей из угла. Поэтому ввели X.
Irina_Yurievna, надо детали все прочитать. Y*Ai - этот множитель получается при счёте, сколько раз в ответе будут 4 ребра от новых вершин к копиям дерева. Множитель X получается при счете путей между деревьями, конкретно кусков этих путей между концом и углом дерева, в котором этот конец находится.
</>в редакторе). Иначе вопрос удалят.