 # JONHLP - Editorial

Author: Jaymeet Mehta

EASY

# PREREQUISITES:

Simple observations , DP

# PROBLEM:

You are given an array A of N integers and Energy e, a special sequence is defined as [x,x*e,x*e^2,...,x*e^k] for any integer x and k. You have to find maximum length of such sequence among all sub sequences of A.

# QUICK EXPLANATION:

We can generate the hash table of the elements in the array and generate dp with 0 as initial value and the dp equation as dp[i]=dp[i/E]+1. and print the max value of dp

# EXPLANATION:

Observation
We can see that the special sequence is in the form of Geometric Progression with r=e.
So, We have to find the longest GP in the given Array.

Logic
As the sequence is in the form of GP, In GP we know that the G_i=G_{i-1}*r where G_i is the i^{th} term of GP.

We can use dp for this question. We can use the previous result to get the result of the current element of the array.

Let dp[x] be the answer maximum length of GP until element x.

So when we encounter x*e we can use dp[x] as a sub problem.

Then we have an easy solution,let’s store dp in a map (unordered_map in c++) and initialize the map with the value 0 for every key.
dp[i]=dp[floor(i/E)]+1

Then the maximum element of dp will be our answer.

# TIME COMPLEXITY:

Time Complexity is O(N*logN) in average as the time of storing an element in a map is O(logN) in average.

# SOLUTIONS:

Setter's Solution
``````#ILLUMINATI SEASON 6
'''
codechef id :mj_13
Problem : Jonesy Wants Help
'''
from collections import defaultdict
from sys import stdin,stdout