TLE in Niceness of the Arrays (NICARRAY)

general
, , ,
1

I was solving the Niceness of the Arrays problem (NICARRAY Problem - CodeChef) and I came up with the following backtracking solution which generates all the sets of integers for the missing values. Though the code gives the correct output but it is not efficient enough hence gives TLE in the second sub-task.

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

void solve(int i, int n, int v, vector<int> solution, vector <vector<int>>& solutions, int prev)
{
    if(i == n)
    {
        if(accumulate(solution.begin(), solution.end(), 0) == v)
        {
            solutions.push_back(solution);
            return;
        }
        else
            return;
    }

    else if(accumulate(solution.begin(), solution.end(), 0) > v)
    {
        return;
    }

    else
    {
        for(int j=1; j<=(v-n+1); j++)
        {
            if(j >= prev)
            {
                solution.push_back(j);
                solve(i+1, n, v, solution, solutions, j);
                solution.pop_back();
            }
        }
    }
}

const long long MOD = 1e+9 + 7;
long long niceness(int a[], int len)
{
    long long gcd_sum = 0;
    for(int i=0; i<len-1; i++)
    {
        for(int j=i+1; j<len; j++)
        {
            gcd_sum += __gcd(a[i],a[j])%MOD;
        }
    }
    return gcd_sum%MOD;
}

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

    int t;
    cin >> t;
    while(t--)
    {
        int N, S;
        cin >> N >> S;
        int sum = 0;
        int A[N];
        vector<int> missing;
        for(int i=0; i<N; i++)
        {
            cin >> A[i];
            if(A[i] > 0)
                sum += A[i];
            else
                missing.push_back(i);
        }
        vector<int> sol;
        vector <vector<int>> sols;
        int target_val = S - sum;
        int vars = missing.size();
        solve(0, vars, target_val, sol, sols, 1);

        int total_niceness = 0;
        for(int i=0; i<sols.size(); i++)
        {
            do
            {
                for(int j=0; j<vars; j++)
                    A[missing[j]] = sols[i][j];
                total_niceness += niceness(A, N)%MOD;
            }while(next_permutation(sols[i].begin(), sols[i].end()));
        }
        cout << total_niceness%MOD << "\n";
    }

    return 0;
}

How can I improve this solution to get an AC? Please help.

2

@everule1 Please help.

3

@tmwilliamlin Please Help.

4

https://www.codechef.com/viewsolution/30693644
Finally. Dp solution. A lot of 0s in the array, so I can optimise it a lot, but it seems that’s not needed.
Took me a full hour.
Finished commenting.

1 Like
5

It took me 4 hours to come up with a solution that gives a TLE. :joy:
Thank you so much :blush:. The only problem is that I still can’t understand the approach, maybe it has something to do with my poor understanding of dynamic programming :frowning:. Can you please suggest some ways by which I can get better at dynamic programming (and recursion)? Another doubt, how does this problem have ‘easy’ as it’s tag?

6

Atcoder dp contest has a good difficulty curve.
Maybe the question is actually easy and I’m stupid :disappointed_relieved:. But honestly some questions are easy for the average person but hard for you, and some questions are hard for the average person but easy for you, so there’s no correct difficulty. The correct solution is probably a easier backtracking but I’m infinitely more comfortable with an iterative dp.

1 Like