 # Dementia rated contest

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.

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 == a) cout << "draw\n";
else cout << "first\n";
} else {
long long x = 0, y = 0;
x += a;
y += a+a;
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