Why is my solution timing out? (USACO 2020 Gold Open P3 Exercise)

Debugging Help
#1

I checked my code and it should have the exact same run time as the official solution: my code iterates i through [0, q=primes.size()], x through [0, N], and j through [1, log(x)]. The official code iterates i through [0, primes.size()], j through [0, N], and pp through log(j) iterations.

This means the two programs should have the exact same runtime, but mine is timing out for some reason.

My code:

#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
#include <string>
#include <cstdio>
#include <cstring>
#include <algorithm>  
#include <math.h>
#include <numeric>
using namespace std;
using ll=long long;


int N, q=0, sieve[10001];
ll M, f[10001][1230];
vector<int> p={0};

void sieveMethod(){
  for (int i=2; i<=N; i++) sieve[i]=0;
  for (int x=2; x<=N; x++){
    if (sieve[x]==0){
      for (int j=2*x; j<=N; j+=x) sieve[j]=x;
      q++;
    }
  }
  for (int i=2; i<=N; i++){
    if (sieve[i]==0) p.push_back(i);
  }
}

int main() {
  ifstream cin("exercise.in");
  cin>>N>>M;
  sieveMethod();
  for (int i=0; i<=q; i++) f[0][i]=1;
  for (int i=0; i<=N; i++) f[i][0]=1;
  for (int i=1; i<=q; i++){
    for (int x=1; x<=N; x++){
      f[x][i]=f[x][i-1];
      int m=(int)(log(x)/log(p[i]));
      for (int j=1; j<=m; j++){
        int pj=(int)(pow(p[i], j));
        ll add=((ll)(pj)*f[x-pj][i-1])%M;
        f[x][i]=(f[x][i]+add)%M;
      }
    }
  }
  ofstream fout("exercise.out");
  fout<<f[N][q];
}
#2

It’s probably something related to m. When I replaced your third for loop with a while loop like this:

#include <iostream>
#include <fstream>
#include <string>
#include <cstdio>
#include <cstring>
#include <algorithm>  
#include <math.h>
#include <numeric>
#include <vector>
using namespace std;
using ll=long long;


int N, q=0, sieve[10001];
ll M, f[10001][1230];
vector<int> p={0};

void sieveMethod(){
  for (int i=2; i<=N; i++) sieve[i]=0;
  for (int x=2; x<=N; x++){
    if (sieve[x]==0){
      for (int j=2*x; j<=N; j+=x) sieve[j]=x;
      q++;
    }
  }
  for (int i=2; i<=N; i++){
    if (sieve[i]==0) p.push_back(i);
  }
}

int main() {
  ifstream cin("exercise.in");
  cin>>N>>M;
  sieveMethod();
  for (int i=0; i<=q; i++) f[0][i]=1;
  for (int i=0; i<=N; i++) f[i][0]=1;
  for (int i=1; i<=q; i++){
    for (int x=1; x<=N; x++){
      f[x][i]=f[x][i-1];
      int m=(int)(log(x)/log(p[i]));
      int pj = p[i];
      while(pj <= x){
        ll add=((ll)(pj)*f[x-pj][i-1])%M;
        f[x][i]=(f[x][i]+add)%M;
        pj *= p[i];
      }
    }
  }
  ofstream fout("exercise.out");
  fout<<f[N][q];
}

your code ran on time.

1 Like
#3

Huh, interesting. I did some more tests and it does seem to have something to do with m and not the pow operation inside the loop, or the fact that it’s a for loop (while m-- is also too slow). I’ve spent more than an hour already trying to figure out what’s going on but I still have no idea. Can someone help please?

#4

Probably log is just slow?

Also, the solution in post #1 is wrong; the while loop in post #2 does not always take the same number of iterations as the solution in post #1 due to floating point inaccuracy.