Brankonymous's blog

By Brankonymous, history, 5 years ago, In English

Hi, can someone help me solve this problem:

Input consist of integer n and array a of n integers. Output number of pairs (a[i],a[j]), i<j who are adjacent or for all k (i<k<j) this equation is true: a[k]<=min(a[i],a[j]).

1<=n<=10^6

0<=a[i]<=2^31

example:

8

4 1 2 3 6 5 1 2

Output: 11

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
Rev. 2   Vote: I like it -11 Vote: I do not like it

Since any adjacent element is considered as valid pair, ans is at least n-1. So initialize ans = n-1

Let the array be a[].
For such index b where a[b+1] < a[b], if you use index b as left border, calculate how many index you can use as right border. From index b+1 iterate to the right til the elements are non decreasing, i.e. stop at index i when a[i]<a[i-1]. From index b+2 till i-1 you can use any index as right border for the left border b. So, set ans = ans + (i-b-2); and b = i-1. Initially set b = -1, then if b != -1 only then you add i-b-2 to answer.

Also, for any contiguous segment [x,y] of length at least 3, where all elements are similar, you can use any index from x to y-2 as left border for right border y. So, set ans = ans + y - 1 - x

Complexity: O(n)

Code:
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If I understand you correctly, approach is wrong. If you see this test example: 5 4 2 3 2 5 Your answer will be 2 for i=1, you don't look pair (1,5), only (1,2),(1,3). I can't give you problem link beacuse I have problem written on paper, and problem is written on Serbian language.

»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Can you give the problem link ?