Dementia rated contest

help
64

Correction : Not the highest power of Prime but the highest multiple of prime (contirubte to make LCM (eg : n = 11, (7-(prime 7),8 (prime 2),9(prime 3),10(prime 5),11(prime 11) give LCM : 27,720)). so we can need to highest seprate multiple of prime )
(PS: correct me if I am wrong)

1 Like
65

Always you should pick the maximum element

2 Likes
66

Write the array in every step

67

@sebastian we can reach 1 2 3 420 420 420 420 from 1 2 3 4 5 6 7 using following pairs of indices in only 4 operations:
(4 5) , (6 7), (5 6) , (4 7). Correct me if I am wrong. So the answer should be 4+3=7.

1 Like
68

can u read english ?

69

bro you can only choose two numbers at a time.
you step two should be done like this:
1 2 3 20 20 6 7
1 2 3 20 20 42 42

70

Thanks for pointing that out.

1 Like
71

1 2 3 (20) (20) 6 7
1 2 3 20 20 (42) (42)
yeah proceed that is 2 steps then it will be like
1 2 3 (420) 20 (420) 42
1 2 3 420 (420) 420 (420)
(420) 2 3 420 420 420 (420)
420 (420) 3 420 420 420 (420)
420 420 (420) 420 420 420 (420)

72

+1 @therealnishuz

73

5 primes 2,3,5,7,11 so l=5 we can take the no.s which have maximum power of these primes tho this approach will give wrong ans for n=7 but got AC i don’t know how. I think it can also be solved using DSU

74

LCM = product of the highest powers of primes.
For n = 9, the highest power of 2 is 8.

1 Like
75 
bool isPrime(const int& a) {
	bool f = 1;
	for (int i = 2; i <= sqrt(a); i++) {
		if (a%i==0) {f=0;break;}
	}
	return f;
}
int p[1000005];
p[1] = 0;
for (int i = 2; i <= 1000000; i++) {
	if (isPrime(i)) p[i] = p[i-1]+1;
	else p[i] = p[i-1];
}

This worked for me

76

Can you please elaborate on this

77

How didn’t you get TLE? Your code is O(n\sqrt{n}).

78

we can reach 1 2 3 420 420 420 420 from 1 2 3 4 5 6 7 using following pairs of indices in only 4 operations:
(4 5) , (6 7), (5 6) , (4 7). Correct me if I am wrong. So the answer should be 4+3=7.

79

It seems correct bro, I agree with your above testcase answer.

80

I did the pre-computation before my test case loop. So for each test case, it is just O(1) and outside it is strongly O(sqrt(1000000))
My Solution

1 Like
81

in n=9 , highest power of 2 is 8 (2^3)
highest power of 3 is 9 (3^2)
highest power of 5 is 5 (5^1)
highest power of 7 is 7(7^1)

82

(4 5) , (6 7), (5 6) , (4 7)
bro pls be clear before saying something

for 7, ans is 7

1 2 3 (20) (20) 6 7
1 2 3 20 20 (42) (42)
1 2 3 (420) 20 (420) 42
1 2 3 420 (420) 420 (420)
(420) 2 3 420 420 420 (420)
420 (420) 3 420 420 420 (420)
420 420 (420) 420 420 420 (420)

pls disprove
@sebastian

2 Likes
83

Sorry apologies