@Homemade

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

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

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

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

Как он заметил эту формулу? До слов "Можно заметить" все понятно.
  • Вопрос задан
  • 199 просмотров
Решения вопроса 3
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
Ну, это известная формула - количество пар среди n объектов. Для самого левого подходит n-1 правых концов. Для второго - их будет n-2. Для последнего - 0. Сумма (n-1)+(n-2)+...+1+0 = (n-1)n/2. Можно через сумму арифметической прогрессии получить.
Ответ написан
dimonchik2013
@dimonchik2013
совет, который уже дан - ничего не стоит
вам повезло попасть на довольно известный математический баян
Ответ написан
@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
...
думаю дальше понятно, например через эту формулу можно проверить есть ли целочисленный квадрат у числа (хотя я бы так делать не с)

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

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

Войти через центр авторизации
Похожие вопросы