Where is the Ghost

Discussions Toph Problems
1

The ghost exploration team find some 1D coordinate where the cursed object is located. You will be g…

Click here to read the complete problem statement.

If you need help solving this problem, mention your approach and ask specific questions. Please avoid sharing your code and asking the Community to figure out “what’s wrong”.

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

using i64 = long long;
i64 const &N = 2520; 
i64 const &mod = 1E9 + 7;

void Solution() {
    i64 n;
    cin >> n;
    i64 _array[n];
    for (auto & x: _array) {
        cin >> x;
    }
    vector < i64 > dp(N, 0);
    dp[1] = 1;
    for (int i = 0; i < n; ++ i) {
        i64 x = _array[i];
        vector < i64 > dp_new = dp;
        for (i64 num = 1; num < N; ++ num) {
            i64 rem = (num * x) % N;
            dp_new[rem] += dp[num]; dp_new[rem] = dp_new[rem] % mod;
        }
        dp = dp_new;
    }
    cout << dp[0] << "\n";
    return ;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int T;
    T = 1;

    while (T --) {
        Solution();
    }

    return 0;
}


what is wrong here ?
4

num should start at 0, since this would mean everytime we have a new number, the existing subset that could be divisible by 2520 would double.

On top of that, dp[1] should not be initialized, since this means that there already exist a subset with remainder 1. To add, after the for loop you should add dp_new[rem] by one, to account for the subset that only contain that new number

1 Like