Nams's blog

Counting the number of contiguous subarrays in which the largest element of that subarray occurs only once
By Nams, history, 9 years ago, In English

Hello all,

This is my first blog entry on Codeforces. So please forgive me if I am not following any regulation. I recently came across a question.Its statement goes like this:

Given an array A1,A2...AN. We are asked to count the number of contiguous subarrays Ai,Ai+1...Aj such that 1≤i≤j≤N and the largest element of that subarray occurs only once in that subarray.

For example: If N=3 A[3]={1 2 3} => Ans=6 || If N=4 A[4]={2 2 1 2} => Ans=6

Constraint: 1<=N<=10^5 and 1<=A[i]<=10^5

I have the Naive approach which works in O(n^2) but as evident from constraints it would give TLE. So please help to optimize the solution. Thanks.

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Nams (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

Let's fix some element which will be the maximum and will occur only once. This can be done with a for-loop over the elements. Say the current index is i. We need to find two integers — L (the length of the maximum contiguous subarray ending at index i-1 containing only elements which are less than A[i]) and R (the length of the maximum contiguous subarray starting from index i+1 containing only elements which are less than A[i]). Then obviously (L+1)*(R+1) should be added to the answer. Now we need to find those L and R fast. This is actually very similar to finding the largest rectangle in histogram so we can now solve the problem in O(N).

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

There was an issue with my first idea. This is the correct one:

For each i, calculate the amount of values smaller than v[i] before and after i and call it l[i] and r[i]. Add l[i]*r[i] to the answer. The naive implementation would be O(N2), but if you keep a segment tree and update it after each element is processed you get O(NlogA).

My accepted solution: http://ideone.com/gtfjYU

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Nams where can I submit the problem?

→ Reply