You are not logged in. Please login at www.codechef.com to post your questions!

×

Help for solving this subarray inversion problem

You are given an array consisting of N integers. Now, you need to find the length of largest sub array of this array where first element of this sub array is ≥ than the last element of that sub array.

Let us consider a sub array from index i to j. You need to find the length of the maximum length sub array, such that A[i]≥A[j].

Sample Input:

The first line contains a single integer T denoting the number of test cases in a single test file. Each test case is spread over 2 lines, in the following format :

The first line of each test case contains a single integer N denoting the size of the given array A. The next line contains N space separated integers, where the ith integer denotes A[i].

Sample Output:

For each test case output answer in new line.

Constraints:

  • 1≤T≤10
  • 1≤N≤105
  • −109≤A[i]≤109

Example test case:

Input:

1
5
5 4 3 2 1

Output :

5

Explanation:

The max length sub array which can be chosen is from index 1 to 5.

asked 08 Mar '17, 00:32

arpit728's gravatar image

2★arpit728
6831462
accept rate: 10%


[Rewrote the answer, I hope this is easier to understand :)]

First we apply coordinate compression on the values in array $A$. Now all values are within the bound of $10^5$. This will be helpful because we will need to use the values in $A$ as array indices. We will use an array $last$ that will store the last occurrences of each value in $A$. So $last[v]$ will contain the last index at which $v$ occurs in $A$. If it does not occur in $A$, we can set $last[v]=-1$. This can be done with a loop in linear time.

Now suppose we are at an index $i$ of array $A$, then $last[A[i]]$ contains the last index at which $A[i]$ occurs. So $last[A[i]]-i+1$ will be the length of the longest subarray that starts at $i$ with $A[i]$ and also ends with $A[i]$.
However the problem statement says that the last value of the subarray can be any value $\le A[i]$, not just $A[i]$ itself. So the length of the longest subarray starting at $i$ with $A[i]$ and ending with some value smaller than $A[i]$ would be $max(last[0], \; last[1], \; ... last[A[i]-1], \; last[A[i]]) - i + 1 $. Running a loop from $0$ to $A[i]$ for each $i$ will be too slow. So we need a smarter way.

We will make another array $pre$ (reusing the same array is also possible) such that $pre[v]$ will contain the last index of any value $\le v$. So $pre[v]=max(last[0],\;last[1],\;...last[v-1],\;last[v])$. We can do this in linear time again, using the following loop

p[0] = last[0]
for i in [1,n)
    p[i] = max(p[i-1], last[i])

Now the only part left is to iterate over array $A$ and find the answer. For index $i$, $pre[A[i]]-i+1$ will be the length of the longest subarray that starts at $i$ with $A[i]$ and ends with a value $\le A[i]$. Choose the maximum such value as answer.

Here is the code.

link

answered 08 Mar '17, 01:11

meooow's gravatar image

6★meooow ♦
7.0k717
accept rate: 48%

edited 08 Mar '17, 21:43

1

@meooow I understood the coordinate compression thing and making the last occurrence array. But I didn't understand anything beyond that.

what does this mean "Generate a prefix max array pp on this last occurrence array."

(08 Mar '17, 08:37) arpit7282★

@meooow i think you should count for first occurrence of each integer if you are running a loop from backward so that maximum distance can be achieved.

(08 Mar '17, 10:27) bansal12325★
1

Maybe by last occurance @meooow meant "last occurance from w.r.t front" (or "first occurance from last"), cause I didn't felt the anomaly until you pointed it out @bansal1232.

@meooow, can you clarify here, please :)

(08 Mar '17, 10:39) vijju123 ♦♦5★

I also think that @meooow has misinterpreted the question as he is taking all the value from i to j in sub-array such that $A[i]>=A[j]$

(08 Mar '17, 10:46) bansal12325★

Quite Possible.

(08 Mar '17, 10:47) vijju123 ♦♦5★
1

I have replaced the sort of ambiguous line about the last occurrence, thanks for pointing it out. The answer is quite correct though, @bansal1232.

(08 Mar '17, 14:40) meooow ♦6★

@meooow can you please explain this part p[A[i]]−i+1. what does this statement mean and what are we trying to achieve using this statement.

(08 Mar '17, 21:02) arpit7282★

@arpit728 I have edited the answer, please tell me if it is clearer now :)

(08 Mar '17, 21:42) meooow ♦6★

Hey! @meooow, It had been a great help and got to learn new concept of coordinate compression. Can you share some more cooler problems based on the same concept.

Thank you very much.

(08 Mar '17, 23:02) arpit7282★
showing 5 of 9 show all
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,020
×1,642
×833
×770
×228

question asked: 08 Mar '17, 00:32

question was seen: 1,024 times

last updated: 08 Mar '17, 23:02