MISMEETA - EDITORIAL

PROBLEM LINK:

Practice
Contest

Author: Kapil Bansal
Tester: Sankalp

DIFFICULTY:

EASY

PREREQUISITES:

Math

PROBLEM:

There is an array of size N.

  • Choose two subsequent indices whose values have odd number of divisors.
  • Find the indices which have maximum sum(inclusive)

EXPLANATION:

Every perfect square has odd number of divisors.

Therefore, first we need to find two consecutive numbers which are perfect squares.
Then we will need to find the pair which will give us the maximum cards.

SOLUTIONS:

Setter's Solution
def getMaxCard(n,c):
    ec = []
    for i in range(n):
       # To ensure the number is a perfect square
        if c[i]**0.5 == int(c[i]**0.5):
            ec.append(i)
    
    if len(ec) <= 1:
        return 0
    
    maxCard = ec[1] - ec[0] + 1
    for i in range(1,len(ec)-1):
        if maxCard < ec[i+1] - ec[i] + 1:
            maxCard = ec[i+1] - ec[i] + 1
    return maxCard

for _ in range(int(input())):
    n = int(input())
    c = list(map(int,input().split()))
    print(getMaxCard(n,c))

Feel free to share your approach. Suggestions are always welcomed :grinning:

What do I think
It would be easy to understand if you use

Every Perfect Square has odd number of divisors

rather than

Every integer with odd no. of divisors is a Perfect Square

Though Question Was really Good .
appreciated .

1 Like

Feel free to share your approach. Suggestions are welcomed

1 Like

I have a confusion
Example input is

2
5
1 9 15 17 1
3
5 10 12

in the first test both 1 at 1 and 5 are perfect square so max length should be 5 and not 4 as both L and R is to be included , 4 i understand is the length for 2(9) and 5(1) which is second of two lengths available.

Its not mentioned card nos can not be same.

In the problem, it is mentioned that the indices should be subsequent. Therefore, the two pairs are (1,9) at indices 0 and 1 and (9,1) and indices 1,4

Yes you are right , now i got that.