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.
abey dekh lo yaar
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
please if anyone can tell
if there are l primes if we only have to deal with these primes we have to do minimum l-1 no. of operations and we can make 1 of them the required LCM. then for n-1 remaining no.s we have to do at least n-2 operations so total l-1+n-2 operations. Why it is optimal? First l-1 operation can’t be omitted as they are all primes and other n-2 operation are also required because every n-1 remaining no.s has some prime no. missing because the product of primes up to n is always greater than n so there is no no. with all the primes as its divisor.
2 Likes
Helping Hands:
We need the highest power of all primes b/w [1,n] in the final lcm. It can be proved that a number [1,n] cannot have the highest power of two or more primes.
Let’s prove it by contradiction. Suppose X contains highest power of two primes, X = (a^m)*(b^n); (m>=1 and n>=1). Let’s take numbers Y = a^(m+1) and Z = b^(n+1). For our claim to be false, there should not exist a number less than X with power of a or b higher than m and n respectively. If our claim is false then X < Y and X < Z => (b^n) < a and (a^m) < b => a^(mn) < a. This is not possible for m >=1 and n>=1. Hence, our claim is correct.
Now, steps to join all numbers with the highest power of primes => p-1. After these p-1 steps, 2 numbers are equal to the final LCM. We need to perform additional n-2 steps to make the rest of the n-2 steps equal to the lcm.
Hence, the answer is n+p-3. p = | {x | x is primes, 1<=x<=n} |.
For n = 1, answer is 0.
For n = 2, answer is 1.
Problem CodeChef: Practical coding for everyone
what’s wrong with this solution?
void solve() {
/// write your code here
int n;
cin >> n;
vector<int64_t> arr(n);
for(int i = 0; i < n; i++) cin >> arr[i];
sort(arr.begin(), arr.end());
uint64_t p1 = 0, p2 = 0;
p1 += arr[0];
p2 += arr[1] + arr[2];
for(int i = 3; i < n; i++) {
if (i % 2) {
p1 += arr[i];
} else {
p2 += arr[i];
}
}
if (p1 == p2) cout << "draw\n";
else if (p1 > p2) cout << "first\n";
else cout << "second\n";
}