Dementia rated contest

help
21
2 Likes
22

what is the need to sort the array?

23

Thanks for the logic

24

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
25

@therealnishuz pls give your helping hand intution

26

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.

27

abey dekh lo yaar

28

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

29

please if anyone can tell

30

Please help where i am wrong

Link to solution:
https://www.codechef.com/viewsolution/36694740

31

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
32

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.

33

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";
}
34

jst sort in descending order

35

First lcm(20,42)!=420

1 2 3 4 5 6 7
ā€¦
1 2 3 20 20 42 42
1 2 3 20 420 420 42
1 2 3 420 420 420 42
1 2 3 420 420 420 420
ā€¦
420 420 420 420 420 420 420 (total=8)

36

oops what the hell i did :sweat_smile:

37

Not much. Just tried it for 2 hours XD

38

@sebastian can we find lcm of hole array n then count all elementā€™s lcm_of_array/a[i] ?

39

it should be 7 mine is correct

40

I didnā€™t understand. Can you show for some n as a example