Как он это «заметил»?

Question

[Homemade]

Задача
Разбор

Отсюда следует решение задачи. Для каждого числа находим позицию старшего единичного бита pi. Тогда нам необходимо посчитать количество пар чисел, для которых pi=pj. Можно заметить, что ответ равен ∑ℓkℓ⋅(kℓ−1)2, где kℓ — количество чисел, у которых pi=ℓ.

Сложность полученного решения по времени — O(n).

Как он заметил эту формулу? До слов "Можно заметить" все понятно.

Answer 1

[Wataru]

Ну, это известная формула - количество пар среди n объектов. Для самого левого подходит n-1 правых концов. Для второго - их будет n-2. Для последнего - 0. Сумма (n-1)+(n-2)+...+1+0 = (n-1)n/2. Можно через сумму арифметической прогрессии получить.

Comments

[Homemade]

Спасибо большое!

Answer 2

[Dimonchik]

вам повезло попасть на довольно известный математический баян

Answer 3

[12rbah]

Как он заметил эту формулу?

Ну на самом деле некоторые формулы можно вывести самостоятельно, если предполагаешь, что некоторые числа имеют связь.
В школе как-то подумал, что квадраты натуральных чисел связаны друг с другом, в итоге получил, такую закономерность
1 = 1
1 + 3 = 4 (2^2)
1 + 3 + 5 = 9(3^2)
1 +... 7 = 16
1 +... 7+9 = 25
1 +... 7+9+11 = 36
...
думаю дальше понятно, например через эту формулу можно проверить есть ли целочисленный квадрат у числа (хотя я бы так делать не с)

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

Comments

[Homemade]

Спасибо за полезный совет