Approach needed to IEMCO6C of IEM coding challenge

general
,
1

Can anyone explain the solution to the problem IEMCO6C?

Link: https://www.codechef.com/IEMCO6/problems/IEMCO6C

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?

2

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).

1 Like
3

@meooow ok could u please explain the approach?

4

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.

1 Like