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 ];
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.
9 Likes
can you guys tell me how you got this approach for Helping hand question???
1 Like
2 Likes
what is the need to sort the array?
Thanks for the logic
but for 7 its coming 7 as i have written (please if you can see that above and tell if its wrong then why?) and yours is 8.
1 Like
In my approach, I used binary search. You need to sort the array to use binary search. But DIDN’T sort anything because the array is already sorted in non-decreasing order.