Dementia rated contest

how to solve 2nd problem helping hand?? please help

Precompute all primes till 1000000. Store them in a vector (sorted). For each n, binary search the number of primes less than or equal to n. Call that number p.
The answer is n+p-3.

Edge cases

If n is 1 or 2, print n-1.

Code
#include <bits/stdc++.h>

using namespace std;

int main()
{
    vector <int> f(1e6+1, 1), p(0);
    for (int i = 2; i <= 1e6; ++i) for (int j = i; j <= 1e6; j += i) f[j]++;
    for (int i = 2; i <= 1e6; ++i) if (f[i] == 2) p.push_back(i);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        auto ans = lower_bound(begin(p), end(p), n+1)-begin(p);
        cout << (n == 1 || n == 2? n-1 : n+ans-3) << '\n';
    }
}
6 Likes

Instead of binary search you can keep prefix array

9 Likes

can you explain for 8 why ans is 9 please

Why this approach, can you explain a bit please.

let l= no. of primes upto n then ans=l+n-3

lower_bound() has a short implementation (and the vector was sorted ;)). Also, how exactly did you use prefix array?

Can you help with the 1st problem as well? Thanks in advance.

could you explain how the output is 8 for n=7

Just greedy and do what the problem statement says.

int main()
{
    usaco();
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector <int> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        sort(rbegin(a), rend(a));
        if (n == 1) cout << "first\n";
        else if (n == 2) {
            if (a[0] == a[1]) cout << "draw\n";
            else cout << "first\n";
        } else {
            long long x = 0, y = 0;
            x += a[0];
            y += a[1]+a[2];
            for (int i = 3; i < n; i += 2) x += a[i];
            for (int i = 4; i < n; i += 2) y += a[i];
            if (x > y) cout << "first\n";
            else if (x < y) cout << "second\n";
            else cout << "draw\n";
        }
    }
}

@therealnishuz can you please explain why -3 in (n+p)?

making the prefix array like : pref[ i ] = pref[ i-1 ] + prime[ i ];

2 Likes

There are 4 primes less than 8. The answer is 8+4-3 = 9.

precompute the no of primes for each i (1 to n) also then you dont need binary search and can answer query in O(1) time instead of logn.
here is link to my code:
https://www.codechef.com/viewsolution/36681721

1 Like

yes mine is coming 7
1 2 3 4 5 6 7
LCM(4,5)=20;
LCM(6,7)=42;
1 2 3 20 20 42 4 2
LCM(20,42);
LCM(20,42)=420;
1 2 3 420 420 420 420
4 + 3 = 7 operations.
can anybody tell where i am wrong

2 Likes

Can you please give derivation for the formula

yeah even Im getting it that way

Why this method but ?
And how did u think of this approach ?

If you write down all numbers from 1 to n, you will notice that only the highest multiple of primes contribute to the LCM. Let’s say that there are p such numbers. It is optimal to convert these to the LCM first rather than the other numbers. In p-1 operations, you can make the last and second-to-last numbers equal to the LCM. Then we can make the other n-p+p-2 = n-2 numbers equal to the LCM. We also used p-1 operations to make the last number equal. So
the formula is p-1+n-2 = n+p-3
The edge cases are n = 1, \ 2.

6 Likes

can you guys tell me how you got this approach for Helping hand question???

1 Like