Reducing Algorithm Time Complexity of Recursive Function

Question

This is the code for function f(T,k) where

f(T,0)=∑(from i=1 to i≤len(T)) T[i], where len(T) is length of array T.
f(T,k)=∑(from i=1 to i≤len(T)) ∑(from j=i to j≤len(T)) f(T[i...j],k-1), for k>0, where len(T) is length 
of array T and T[i...j] is sub-array of T with elements form the i-th to the j-th position (T[i],T[i+1],...,T[j])

It is a recursive function and I need to reduce the complexity, but I don't know how.
Can someone help me out?

This is the problem text:
1000000007 players participate in this game and the winner is decided by random selection. To make the selection random, the company has set strict rules for selecting that player. First they number the players with identification numbers from 0 to 1000000006. Then they choose array A with N elements and the number k. They then define the winner as the player who has the identification number f (A, k) mod (100000007)

#include <iostream>
#include <vector>

using namespace std;

int N,k,a;
vector<int>A;


int fja(vector<int>A,int k){
    long long suma=0;
    if(k==0){// If k==0 calculate the first said function
        for(auto it=A.begin();it!=A.end();it++)suma=(suma+(*it))%(1000000007);//Moduo is there because suma is very big
        return suma;
    }else{//If k>0 calculate the second function 
        int duzina=A.size();//duzina is length of A (T)
        for(int i=0;i<duzina;i++){//Going through the first and second sum of second function
            for(int j=i;j<duzina;j++){
                vector<int>b(A.begin()+i,A.begin()+j+1);//Creating new vector (array) to pass it into the new function call
                suma=(suma+fja(b,k-1))%(1000000007);//Moduo is there because suma is very big
            }
        }
        return suma;
    }

}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>N>>k; //Number of elements and k
    for(int i=0;i<N;i++){
        cin>>a;
        A.push_back(a);//All the elements
    }



    cout<<fja(A,k);

}

@AlanBirtles It is too slow for large inputs of N and k. I want to reduce time complexity. — Sip_
What exactly is a large value of N and k? What runtime do you expect? What runtime are you seeing? Have you enabled compiler optimisations? — Alan Birtles
Changing fja to take a pair of iterators rather than a vector would avoid the need to take copies of the data — Alan Birtles

Arty Arty · Accepted Answer · 2020-12-20T06:16:11

I implemented non-recursive version, only loop-based, but it has O(k * n^4) so for biggest 10^5 values of N and k it will be too slow.

I provided recursive solution for reference, it can solve for N and k up to 10, my non-recursive solution can solve up to N and k of 100.

I'm sure some loops can be removed in my solution by algorithmic optimization. Still I could not figure out how to solve task for very large values of 10^5.

In current main() function N and k both are 10, for testing only, to leave only fast version you may change N and k from 10 to 100 and comment out f_ref() call. f_ref() is reference recursive function, f_fast() is my faster variant.

Try it online!

#include <cstdint>
#include <vector>
#include <iostream>

typedef uint32_t u32;
typedef int64_t i64;
typedef uint64_t u64;

enum { mod = 100000007 };

i64 f_ref(std::vector<i64> const & T, size_t begin, size_t end, size_t k) {
    i64 sum = 0;
    if (k == 0)
        for (size_t i = begin; i < end; ++i)
            sum = (sum + T[i]) % mod;
    else
        for (size_t i = begin; i < end; ++i)
            for (size_t j = i; j < end; ++j)
                sum = (sum + f_ref(T, i, j + 1, k - 1)) % mod;
    return sum;
}

i64 f_fast(std::vector<i64> const & T, size_t k) {
    size_t N = T.size();
    std::vector<std::vector<i64>> mc, mn;
    for (size_t n = 1; n <= N; ++n) {
        mc.resize(mc.size() + 1);
        for (size_t j = 0; j < n; ++j)
            mc.back().push_back(((n + (n - 2 * j)) * (j + 1) / 2) % mod);
    }
    for (size_t ik = 0; ik + 1 < k; ++ik) {
        mn.clear();
        mn.resize(N);
        for (size_t n = 1; n <= N; ++n) {
            mn[n - 1].resize(n);
            for (size_t i = 0; i < n; ++i)
                for (size_t j = i; j < n; ++j)
                    for (size_t l = 0; l <= j - i; ++l)
                        mn[n - 1][i + l] = (mn[n - 1][i + l] + mc[j - i][l]) % mod;
        }
        mc = mn;
    }
    i64 sum = 0;
    for (size_t i = 0; i < N; ++i)
        sum = (sum + mc.back()[i] * (T[i] % mod)) % mod;
    return sum;
}

int main() {
    std::vector<i64> a;
    for (size_t i = 0; i < 10; ++i)
        a.push_back(i + 1);
    size_t k = 10;
    std::cout << f_ref(a, 0, a.size(), k) << " " << f_fast(a, k) << std::endl;
    return 0;
}

Output for N = 10 and k = 10:

78689325 78689325

Output for N = 100 and k = 100:

37190121

Reducing Algorithm Time Complexity of Recursive Function

1 Answers