CHGCDG - Editorial

general
, , , , ,
44

Thank you. :slight_smile:

45

k.n is of the order n.log(n) as any number can have at-most log(n) factors.
So, the actual complexity is n.log(n).log(h).

46

Not very straightforward dear. If you assume that the for(int k:id[x]) runs for all N numbers everytime, what is the maximum number of times it can run?

A number can be product of <20 distinct prime numbers if A_i \ {10}^{6}. So the complexity becomes O(20*N*LogN) \equiv O(NLogN) as shown in editorial.

1 Like
47

If binary search part isnt clear, then you dont fulfil the pre-requisites to solve the question. Please refer to links in pre-requisites.

48

@codebreaker123 Very nice observation. And thanks @vijju123 for the awesome editorial :slight_smile:

1 Like
49

@vipin_bhardwaj exactly, i am also getting similar kind of doubtā€¦

1 Like
50

@vijju123 Bro, see these linesā€“>
for (int k : id[x])
if (k >= h)
now += ((k - h) >> 1); // sum, that we can use
for (int k : id[x])
if (k < h)
now -= (h - k); // sum, that we need

in idx[x] where x is prime, holds exponent of x in every A[i](excluding if exponent is 0)

so i guess overall complexity will be O(NLogN+k.(summation of number of element id[x] for each prime)*logH)ā€¦

if i am right, can u prove that this solution will not give TLE ?

51

The vector array power needs to be cleared for every new testcase

1 Like
52

Thank you :slight_smile:

53

please someONe reply?

54

I had answered this already in an ans on next page.

I say, lets try to get an upper bound on number of iterations. It cannot be O(N*K) as thatā€™d mean every array element A_i is divisible by each of k primes - not possible based on my previous arguments.

At max, how many iterations can it go then? Each element A_i is divisible by <log_2N primes. So worst case calculated by me was select logN smallest primes such that their product is <{10}^{6}. Let it be X. Make an array with N-1 elements X and one element 1. That gave O(NLogN) complexity.

1 Like
55

Convert recursive to iterative one.

56

@vijju123 got Ac, my finding smallest factor for each number using seive was slow regarding max A[i]=10^6ā€¦

*O(A[i].log[Ai]) ~~ 2 * 10^8 ==tle
so optimised my code little bit, got ac

57

now my code is fastest among all java submission for this problemā€¦ thanks for replying

58

I found this method also; shake out the initial gcd and then only primes below the cuberoot of the limit can support the 2-for-1 deal.