JONHLP - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Jaymeet Mehta

DIFFICULTY:

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
test=int(stdin.readline())
for _ in range(test):
    N,E = map(int,stdin.readline().split())
    A= [int(x) for x in stdin.readline().split()]
    dp=defaultdict(int)
    for i in A:
        dp[i]=dp[i//E]+1
    ans=max(list(dp.values()))
    print(ans)