Can anyone explain the solution to the problem IEMCO6C?
Link: CodeChef: Practical coding for everyone
PS:
I have seen some solutions which uses two for loops to find the next right index as given in the problem.
But worst case operations will be 5*10^8 , wont the solution get TLE?
First you need to calculate the “PerfectArray”. One way is to iterate from right to left while maintaining a record of where each value last appeared in the array. Then for each perfect square x in the range of [0..2\cdot 10^6], check where x - A_i last appeared and take the minimum of all these as the “PerfectNumber” of A_i.
To answer queries you need to count how many values in a range are > some k. This is a standard job for merge sort tree or Mo’s algorithm.
It’s just careless problem setting. They could have easily increased n (and decreased the limit of A_i if necessary) to prevent these solutions \mathcal{O}(n^2) solutions from passing. Even constraints are not followed (see comment by @sarthakmanna here).