The last two sub-problems were harder than 2nd and 3rd sub-problem, I feel like it should’ve been another subtask for points.
If someone could be kind enough to point out what I missed in my solution, please.
I did this:
- Traversed from the end and stopped when pointer was less or equal to max count.
- Skipped 1’s.
- Skipped repeated elements.
Make long long integer instead and use scanf/printf instead of cin/cout
I thought long long calculations were slower than int. Also, cin and cout are faster with FastIO
It’s n^2 in worst case
What’s the complexity of correct code?
They are not as fast as scanf/printf even with fastIO
You can check my submissions I was also failing those cases till I optimized my code
A n^2 solution in worst case worked for me. You don’t have to check the MSV of an element If it was divisible by any other element which occurs later in the sequence.
Has no one posted an asymptotically optimal (or at least, good-enough) solution yet? Here’s mine - there’s no Editorial-style overview, but it’s hopefully clear what’s happening.
The computeFactors function can probably be replaced by a much simpler version - this is just one I had lying around (from FUZZYLIN, I think?) 
I don’t know if it is optimal, but my solution should be O(M(logM)(logN)), where M is the maximum value for a[i]. However, I think we could prove a closer bounds.
https://www.codechef.com/viewsolution/26936295
The approach is analogue to the one used for finding primes with the sieve of Eratosthenes.