Can anyone explain me how to solve the following problem

Can anyone please explain me the suitable approach to the problem ?
Link : Contest Page | CodeChef

First note that the number which is perfect square has odd number of divisor
Like

1 = 1 -> 1
4 = 1 , 2 , 4 -> 3
36 = 1 , 2 , 3 , 4 , 6 , 12 ,36 -> 7
9 = 1 , 3 , 9 -> 3
49 = 1 , 7 , 49 -> 3

and so on

you was having to check if there exists at least two perfect square in array other wise answer is 0

if there exist perfect squares you was having to find two perfect squares
whose distance is greater than all other pairs

Here My solution

https://www.codechef.com/viewsolution/42002152

Where I first Checked if the given numbers is perfect square of not
if it is then I pushed its index in vector
and I repeated until the end of array

then if vector size is less than 2
means we have only one perfect square
so answer should be 0

if it is greater then 2
I just took difference between vector elements which are nothing but the the indices of perfect square numbers in given array and I printed Max difference between them
As max the difference max The elements i will get

In easy way
from sample
1 9 15 17 1

here 1 and 9 are perfect squares
if I choose 1 with index 0 and 9 with index1 I will get
1 9
only

but if I choose 1 at index 4
and 9 at index 1
will get
9 15 17 1

so we can get either 2 gifts or 4 gifts
but as we want max so 4 is the answer

I don’t understand the problem. Since you were allowed to include L and R. In example 1, the answer should be 5 instead of 4.

The Problem statement was somewhat ambiguos but still
If you read problem statement carefully it is given that L and R should be Subsequent

so If you take out elements according to condition that number of odd divisors
the sequence will be
1 9 15 17 1
1 9 1
so for first 1
9 is subsequent and
for 9 both first and last 1s
are subsequent
but as max elements exists between
9 and last 1 we take distance between them in consideration

So for
L = 1 at index 0
R = 9 at index 1
can be the pair as they are subsequent according to the condition
but for
L = 1 at index 0 and
R = 1 at index 4
cant be the pair as they are not subsequent as the number 9 which has odd number of divisors exist between them

i hope this will help you .

1 Like

Already got it after my previous post but still quite thanks.