Задать вопрос
@Irina_Yurievna
тестировщик с 3 летним опаттом

Почему 8 в формуле hackerrank city?

HackerRank-city is an acyclic connected graph (or tree). Its not an ordinary place, the construction of the whole tree takes place in N steps. The process is described below: • It initially has 1 node. • At each step, you must create 3 duplicates of the current tree, and create 2 new nodes to connect all 4 copies in the following H shape:

At each ith step, the tree becomes 4 times bigger plus 2 new nodes, as well as 5 new edges connecting everything together. The length of the new edges being added at step & is denoted by input A, Calculate the sum of distances between each pair of nodes; as these answers may run large, print your answer modulo 1000000007. Input Format The first line contains an integer, N (the number of steps). The second line contains N space-separated integers describing A, A1,…, AN-2, AN-1.

Sample Input 0

1 1

Sample Output 0

29

Sample Input 1

2 2 1

Sample Output 1

2641

Из едиториала решение
https://www.hackerrank.com/challenges/hr-city/editorial
Почему в формуле 12Х+8?
Как обьсянить ту формулу
застряла - помогите пожалуйста

ПС -каритнки не вставляются
  • Вопрос задан
  • 152 просмотра
Подписаться 1 Простой 2 комментария
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Это формула просто уже причесана и разложенна на множители. Это 12Y+8 (не X, кстати) идет в слагаемом (12Y+8)*(X+Y*Ai)

8 там - это 4*2. 4 дерева и 2 новые вершины. Подробнее ниже.

Как подсчитать все расстояния? Давайте отдельно посмотрим на те, которые внутри копии из 4 деревьев. Это даст нам слагаемое 4*Answer. Теперь подсчитаем те, которые идут между двумя разными деревьями. Их можно рзабить на 2 части - куски среди 5 новых ребер длины Ai и куски внутри деревьев. Вот эти куски внутри деревьев они все будут из угла, которым дерево крепится к остальным. Поэтому нам надо считать вот эту вот сумму расстояний от угла дерева (X).

Новые ребра посчитаем отдельно. В скольки путях каждое ребро будет присутствовать? Это надо перемножить количество вершин с одного конца ребра на количество вершин с другого конца. Ведь из каждой из первых есть путь во вторые, проходящий через данное ребро. Для 4-ех новых ребер размеры кусков будут Y и 3Y+2. Вот мы получили 4*Y*(3Y+2)*Ai. Вот тут если 4 внести внутрь мы получим вот это самое 12Y+8 из вопроса. Для одного ребра размеры будут 2Y+1 и 2Y+1. Вот мы получили слагаемое (2Y+1)^2*Ai.

Дальше надо посчитать, сколько раз каждый кусок в дереве из угла пойдет в ответ из путей между деревьями. Опять же, ровно столько раз, сколько вершин можно взять в качестве другого конца. Таких веришин 3*Y+2 - в любом из трех остальных деревьях или 2 новые вершины. Но эти куски в каждом из 4 деревьев, поэтому надо домножить на 4. Это дает нам слагаемое 4*X*(3Y+2). Тут тоже вылезает 12Y+8.

Вот и получается формула там.
Чтобы пересчитать Y, понятно что надо умножить на 4 и прибавить 2. 4 дерева 2 новые вершины.

Вот с X по сложнее. Во-первых. там могут быть пути внутри одного дерева. Получаем слагаемое X. Во-вторых, надо посчитать, сколько раз каждое из новых ребер войдет в ответ. Ребро у дерева с углом с одной стороны имеет ровно одну вершину конец - угол. С другой может быть в любом дереве или в одной из 2 новых вершин. Поэтому получаем слагаемое (3Y+2)*Ai Ребро между новыми вершинами с одной стороны может кончатся в любом из 2 деревьев или в новой вершине. Получаем (2Y+1)*Ai. Оставшиеся 3 ребра ведут только в одно дерево и дают 3*Y*Ai.

Куски путей внутри других деревьев однозначно описываются одной вершиной концом и дают как раз все возможные пути из корня, т.е. получаем еще 3X.

Куски путей внутри корневого дерева - это всегда диаметр дерева Z который идет рвоно столько раз, сколько там других вершин в дереве (3Y+2). Получаем Z*(3Y+2).

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

Войдите, чтобы написать ответ

Похожие вопросы