LEXILARGEST has weak test cases

Problem Link: LEXILARGEST Problem - CodeChef


CodeChef: Practical coding for everyone this submission should give tle, problem has weak test cases

Why do you think that should give tle?

Creating new list instead of inserting element,it will be n^2 process,and when he is calculating ans[i],b is reduced till its gcd becomes 1 ,here m=10^9, so it should give tle as well

Couple of things right.

  1. Afaik, code is just inserting the elements into the array not creating a new list. Where do you think he is creating a new list, I don’t see it.
  2. b is reduced till it’s gcd becomes A_i not 1, and this reduction will happen log(A_0) times and b can reduced by upper limit of 3000, which is reasonably fast.

I just gave high level of time complexity, if you wanna read it in detail read its editorial.

1> ans+=[b]

I’m read it as Append operation.
If you do a print it’s the same