USACO 2020 US Open Contest, Gold Problem 3. Exercise

So, my solution to this problem only passed the first test case. I’m pretty sure that there is some sort of logic error in my code, but I can’t figure out what it is. I tried to replicate the dp table by hand and I also tried to see if there were any missing holes in my logic. I was hoping that you guys could give me a few hints on any issues with my solution.

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

const int mxn=1e4+1;
int n,mod,ans,dp[mxn];
vector<int> primes;

bool isprime(int x){
    for(int i=2;i<x;i++)
        if(x%i==0) 
            return false;
    return true;
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    /* freopen("exercise.in", "r", stdin); */
    /* freopen("exercise.out", "w", stdout); */
    cin >> n >> mod;
    for(int i=1;i<=n;i++)
        if(isprime(i))
            primes.push_back(i);
    dp[0]=1;
    for(int x=0;x<(int)primes.size();x++){
        for(int i=1;i<=n;i++){
            if(i>=primes[x])
                (dp[i]+=(dp[i-primes[x]]*primes[x]))%=mod; 
/* since the sum of the permutation depends on how many permutations
there are without the prime, I multiplied the prime to the dp without that prime. 
The solution takes care of the cases with multiple primes factors because of how the 
dp table is set up*/ 
        }
    }
    cout << dp[n];
}

I take it you haven’t looked at the solution yet?
I don’t know if you’d be willing to do this, but try some small test cases and compare your DP table against the solution code’s, if that would help.

lol I’m having the same problem with the previous problem
you have a couple options

  1. try making some testcases by hand and seeing what your code says matches what you got by hand
  2. stress test
  3. download the testcases
1 Like