Problem from ECPC qualifications day 2

#	User	Rating
1	tourist	4009
2	jiangly	3839
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3612
7	Geothermal	3569
8	ecnerwala	3494
9	Um_nik	3396
10	gamegame	3386

#	User	Contrib.
1	Um_nik	164
2	-is-this-fft-	162
3	maomao90	159
3	atcoder_official	159
5	cry	158
5	awoo	158
7	adamant	155
8	nor	154
9	TheScrasse	153
10	Dominater069	152

Hello codeforces. I am trying to upsolve the problems of qualification day2 of ECPC and i need some help on this problem.

The solution that i implemented was a dp solution where dp[i] is the answer for i. so before run any testcase i calculate the dp from 1 to 1e6, and to do this i cal min(dp[i-1]+1, dp[i/j]+j) where j is every divisor of i.

I tried different codes to make this fast and the fasted code that came in my mind was by generate all the prime divisors of i and then calculate the all the divisors of each i from its prime divisors.

But even this code take around more than 3 seconds on my machine. Can anyone please help me with this problem? I want to know if my idea was right and if so will this solution pass in the contest? unfortunately they don't write the time for each test case

Here is my CPP code

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

#define INF 1e18

using ull = unsigned long long;
using ll = long long;
using ui = unsigned int;

#define endl '\n'
#define newl cout<<endl;

void ICPC();

#define N 1000001
int dp[N+10];
int sp[N+10];
bool primes[N+10];

vector<int> getPD(int x) {
    vector<int> ret;
    while(x > 1) {
        ret.push_back(sp[x]);
        x /= sp[x];
    }
    return ret;
}

vector<int> st;
vector<int> tmp;

void genDiv(int ind, int val) {
    if(ind == tmp.size()) {
        st.push_back(val);
        return;
    }
    genDiv(ind+1, val);
    genDiv(ind+1, val*tmp[ind]);
}

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

    memset(primes, 1, sizeof(primes));
    primes[0] = primes[1] = 0;
    sp[1] = 1;
    for(int i = 2; i <= N; i+=2) sp[i] = 2;
    for(ll i = 3; i <= N; i+=2) {
        if(primes[i]) {
            sp[i] = i;
            for(ll j = i; j*i <= N; j+=2)
                if(primes[j*i]) primes[j*i] = 0, sp[j*i] = i;
        }
    }
    dp[0] = dp[1] = 0;
    for(int i = 2; i < N; i++) {
        dp[i] = dp[i-1]+1;
        tmp = getPD(i);
        st.clear();
        genDiv(0, 1);
        for(auto &x : st) {
            dp[i] = min(dp[i], dp[i/x]+x);
        }
    }

    int t = 1;
    cin >> t;
    for(int i = 1; i <= t; i++) {
        ICPC();
        newl;
    }
}

void ICPC() {
    int n;
    cin >> n;
    int ans = 0, tmp;
    for(int i = 0; i < n; i++) {
        cin >> tmp;
        ans += dp[tmp];
    }
    cout << ans;
}

Comments (1)

Show archived | Write comment?

MidoriFuse

14 months ago, # |

← Rev. 2 →

Your idea is good, and DP formula is correct. For simplicity, let $$$N = 1e6$$$, then your algo complexity is somewhere $$$N + N/2 + N/3 + ... + N/N = O(NlogN)$$$, which is pretty good.

The problem is that you also used that much push_back operations, which is kind of expensive (even if you only work on primes). You can run the same DP without using any push backs whatsoever like this:

Code

vector<int> dp(N+10, INF);
dp[0] = dp[1] = 0;
for (int i = 1; i <= N; i++) {
    dp[i+1] = min(dp[i+1], dp[i]+1);
    for (int j = i; j <= N; j += i) {
        dp[j] = min(dp[j], dp[i] + j/i);
    }
}

Should run way faster for the same time complexity. Note that I don't need to use only primes for divide operation, since they only yield worse answers, so the DP wouldn't catch that answer anyway.

→ Reply

Chess.Master's blog