Как оптимизировать код с++ с рекурсией в времени?

Question

[Maksym122]

Текст задачи на картинке, непонятные слова можете перевести
Вот мой код:

#include <iostream>

using namespace std;

int F(int n) {
    if (n % 10 > 0) {
        return n % 10;
    } else if (n == 0) {
        return 0;
    } else {
        return F(n / 10);
    }
}

int S(int p, int q) {
    if (p == q) {
        return F(p);
    } else {
        return F(p) + S(p + 1, q);
    }
}

int main() {
    int p, q;
    cin >> p >> q;
    cout << S(p, q) << endl;
    return 0;
}

Он проходит только 50% тестирования, в остальных не хватает времени.

Comments

[Adamos]

Второй функции необязательно быть рекурсивной по условию задачи.

[Василий Банников]

Можно пойти таким путём, что F - это функция, которая возвращает последнюю цифру числа, которая не является нулём, либо ноль, если число =0.

[res2001]

Используйте std::div для вычисления остатка и частного одновременно.

Answer 1

[Wataru]

Можно попробовать сделать микрооптимизации: функция F реализуется одним циклом (делите, пока делится на 10, потом берите последнюю цифру). S тоже можно считать циклом, а не рекурсией.

Но скорее всего, этого не хватит. Это решение за O(q*log(q)). Ограничения на числа в условии не видно, но если там что-то порядка 2000000000, то ваша программа будет считать несколько секунд.

Надо хорошенько подумать и применить математическую хитрость. Надо как-то считать числа в интервале p...q пачками, а не каждое отдельно.

Что такое функция F? Это последняя ненулевая цифра в числе. Давайте вместо суммы значений F счиатать, сколько чисел из интервала дадут вот такое вот значение? Ну просто по последней цифре сложно сказать, сколько там чисел, а вот если еще зафиксировать количество пропущенных в конце нулей, то уже становится понятно, как подсчитать это. Вот допустим, вы считаете последнюю цифру d и там должно быть 3 нуля. Тогда вы ищети числа вида "xxxd000". Или их можно представить в виде d*1000+x*10000 для произвольного неотрицательного x. И вот вам надо подсчитать сколько таких чисел в интервале [p,q]. Ну решите 2 уравнения: d*1000+x*10000 >= p и d*1000+x*10000 <= q

Таким образом вы за несколько арифметических действий и одну проверку можете подсчитать, сколько чисел вида "xxxd000" будут в интервале. Осталось циклом перебрать d от 1 до 9 и количество нулей от 0 до длины q. И вот у вас решение за O(log(q)).

Edit:
Вот код быстрого решения:

int S(int p, int q) {
  int sum = 0;
  for (int d = 1; d < 10; ++d) {
    for (int tens = 1; tens <= q; tens *= 10) {
      int left = p - d*tens;
      if (left < 0) left = 0;
      else left = (left + 10*tens-1)/(10*tens);
      int right = q - d*tens;
      if (right < 0) right = -1;
      else right /= 10*tens;
      sum += d*(right - left + 1);      
     }
  }
  return sum;
}

Comments

[Maksym122]

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

[Adamos]

Функция F рекурсивна по условиям задачи. Оптимизировать можно только S.

[Wataru]

Adamos, Она вам задана рекурсивно. Если там не написано, что надо ее именно так написать в коде, то - нет.

Если в задаче, например, сказано, что F(x) = sum i=1..x i, то функция заданна циклом. Но ее можно реализовать как x(x+1)/2.

Если вам надо обязательно иметь в коде рекурсивную F, то никак особо вы код не с оптимизируете. S разверните в цикл - и все. Но этого, скорее всего, не хватит.

[Alexandroppolus]

Это решение за O(q*log(q))

вроде за O(q).
в среднем F будет отрабатывать за ~1.1 итераций на последовательных числах

[Wataru]

Alexandroppolus, да, ваша оценка более точна.

[Алексей 〒.]

Wataru,

Если вам надо обязательно иметь в коде рекурсивную F, то никак особо вы код не с оптимизируете.

Кэширование, но да оно в данной функции роли почти не сыграет.

[Wataru]

Алексей 〒., да, в этой задаче это особо не поможет.

[Василий Банников]

Adamos, то что она задана рекурсивно - не значит, что нельзя сделать другую функцию, которая считает то же самое.

[Maksym122]

Wataru, а может быть такое что все оптимизировано нормально но не хватает глубины рекурсии или типа данных для чисел? Или в каких ещё случаях может программа продолжать работать но как бы зависать, в 50% тестов пишет что время вышло

[Wataru]

Maksym122, нет.

[Wataru]

Maksym122, Если не хватает стека, программа упадет с runtime error.
Переполнению тут особо негде и случатся, а если оно и есть, то ну получите вы отрицательные числа вместо правильных.

[Maksym122]

Василий Банников, #include
#include

using namespace std;

int S(int p, int q) {
int sum = 0;
for (int i = p; i <= q; ++i) {
int current = i;
while (current % 10 == 0 && current != 0) {
current /= 10;
}
sum += current % 10;
}
return sum;
}

int main() {
int p, q;
cin >> p >> q;
cout << S(p, q) << endl;
return 0;
}
Вот я все сделал в цикле, время сократилось но все равно 50%, остальные пишет время запуска вышло

[Василий Банников]

Maksym122, поправь форматирование, а то у тебя инклюды пропали.

[Василий Банников]

Maksym122, значит можно сделать следующий шаг - посмотреть на свойства суммы)

[Wataru]

Maksym122, Ну значит, надо как я говорил, применять математику:

int S(int p, int q) {
  int sum = 0;
  for (int d = 1; d < 10; ++d) {
    for (int tens = 1; tens <= q; tens *= 10) {
      int left = p - d*tens;
      if (left < 0) left = 0;
      else left = (left + 10*tens-1)/(10*tens);
      int right = q - d*tens;
      if (right < 0) right = -1;
      else right /= 10*tens;
      sum += d*(right - left + 1);      
     }
  }
  return sum;
}

[Maksym122]

Wataru, теперь на 70%)))
В одном тесте теперь неправильные данные, а в других двух ограничение памяти превысило

[Wataru]

Maksym122,

> В одном тесте теперь неправильные данные, а в других двух ограничение памяти превысило

Поменяйте переменные на int64_t. Особенно tens, left, right. Наверно, там переполнение. В задаче ограничения на q не приведены, но если там действительно 2000000000, то могут быть проблемы.

[Maksym122]

Wataru, СПАСИБО))) ПРОШЛО!!!
Если есть скинь адрес usdt bep20 кину пару баксов в благодарность

[Wataru]

Maksym122, не стоит

Answer 2

[mayton2019]

Здесь медленным является скорее всего вычисление функции S.

int S(int p, int q) {
    if (p == q) {
        return F(p);
    } else {
        return F(p) + S(p + 1, q);
    }
}

Вот для входных параметров p = 0 и q = 0xFFFF_FFFF например нам придется
вращать пустой цикл 4 миллиарда раз (или 4 млр раз проваливаться в рекурсию)
и все просто для того чтобы посчитать сумму

F(p) + F(q)

Можно убрать эти холостые вычисления и таким образом ускорить прохождение тестов.

Comments

[Wataru]

Вы что-то напутали. S рекурсивно вычисляет сумму всех F() от p до q. Там же на каждом рекурсивном вызове прибавляется самое левое слагаемое.

[mayton2019]

Хм... да пожалуй так..

Тогда подходить к вычислению S, F как к численному методу. Понять чем вызовы между ними
отличаются и на этом соптимизировать.