Code : Sending a Sequence Over the Network

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"

bool solve(vector<int> &a) {
    int n = a.size();

    vector<bool> dp(n);
    // dp[i] is true if a[0...i] can be sent over a network.

    for (int i = 0; i < n; i++) {
        // The last segment is [j, i] (inclusive of length).
        for (int j = i - 1; j >= 0; j--) {
            int len = i - j;
            if ((a[i] == len) || (a[j] == len)) {
                dp[i] = dp[i] || (j ? dp[j - 1] : true);
            }
        }
    }

    return dp[n - 1];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        if (solve(a)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"

bool solve(vector<int> &a) {
    int n = a.size();

    vector<bool> dp(n);
    // dp[i] is true if a[0...i] can be sent over a network.
    // Instead of taking contribution, distribute it.

    for (int i = 0; i < n; i++) {
        // Suppose last segment is [j,i].
        // Then, i - j = a[i] ==> j = i - a[i]
        // Therefore, we need to pull contribution from j - 1.
        int j = i - a[i];
        if (j == 0) {
            dp[i] = true;
        } else if (j > 0) {
            dp[i] = dp[i] || dp[j - 1];
        }

        // Push the contribution forward.
        // Suppose last segment is [i,j].
        // Then, j - i = a[i] ==> j = i + a[i].
        // Therefore, we need to push contribution to j.
        j = i + a[i];
        if (j < n) {
            if (i == 0) {
                dp[j] = true;
            } else if (i > 0) {
                dp[j] = dp[j] || dp[i - 1];
            }
        }
    }

    return dp[n - 1];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        if (solve(a)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}