We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Sherlock's Array Merging Algorithm
  5. Discussions

Sherlock's Array Merging Algorithm

  • dehaka
     + 0 comments

    O(n^3), im very surprised this passed, at each iteration O(n^2) operations are needed and i tried to improve this algo to only use O(n) operations at each iteration, so total time would be O(n^2), but couldn't. submitted this and was shocked to see it pass

    there's probably a O(n^2) algo if u fiddle with the permutation terms

    void combinatorial(vector<vector<long>>& P) {
    for (int n = 1; n < P.size(); n++) {
        P[n][0] = 1;
        for (int k = 1; k <= n; k++) P[n][k] = (P[n][k - 1] * (n - k + 1)) % mod;
    }
}

long arrayMerging(int n, const vector<int>& M, const vector<vector<long>>& P) {
    vector<vector<long>> cache(n + 1, vector<long>(n + 1));
    int newInterval = 1;
    for (int I = 1; I <= n; I++) {
        if (M[I] < M[I-1]) newInterval = I;
        if (newInterval == 1) cache[I][I] = 1;
        for (int K = 1; K <= I/2 and I-K >= newInterval-1; K++) {
            for (int l=K; l <= I-K; l++) cache[I][K] = (cache[I][K] + cache[I-K][l] * P[l][K]) % mod;
        }
    }
    return accumulate(cache[n].begin(), cache[n].end(), 0LL) % mod;
}

int main()
{
    int n, t;
    vector<int> M = {-666};
    cin >> n;
    vector<vector<long>> P(n + 1, vector<long>(n + 1));
    combinatorial(P);
    for (int i = 1; i <= n; i++) {
        cin >> t;
        M.push_back(t);
    }
    cout << arrayMerging(n, M, P);
}