Problem from ECPC qualifications day 2

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	165
2	maomao90	164
3	Um_nik	163
4	atcoder_official	161
5	adamant	160
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

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

15 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