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';
}
}
Instead of binary search you can keep prefix array
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";
}
}
}
making the prefix array like : pref[ i ] = pref[ i-1 ] + prime[ i ];
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
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
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.
can you guys tell me how you got this approach for Helping hand question???