WEIRDSUBARR - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: Jeevan Jyot Singh
Testers: Tejas Pandey, Hriday
Editorialist: Nishank Suresh

DIFFICULTY:

TBD

PREREQUISITES:

(Optional) Dynamic programming

PROBLEM:

You have a permutation P of \{1, 2, \ldots, N\}. In one move, you can negate any of its elements.
A subarray is called weird if it can be sorted in ascending order by applying this move several times. Count the number of weird subarrays in P.

EXPLANATION:

In tasks like this which require you to count objects satisfying a certain property, it’s useful to get a simpler criterion of that property.

Let’s look at a weird array A = [A_1, A_2, \ldots, A_k]. What does this tell us about the elements of A?
One obvious fact is that in the final array, all the negative elements must come before all the positive elements — otherwise, there’s no way for the final array to be sorted.
So, there is some index p such that A_1, A_2, \ldots, A_p are negated, and A_{p+1}, \ldots, A_k are not. Looking at each of those parts individually,

  • We want -A_1 \lt -A_2 \lt \ldots \lt -A_p, i.e, A_1 \gt A_2 \gt \ldots \gt A_p
  • We also want A_{p+1} \lt A_{p+2} \lt \ldots \lt A_k

In other words, A must look like a ‘valley’: first decreasing, then increasing (purely increasing/decreasing is also ok). It’s also obvious that any such array is weird, since it can be sorted by negating the first part.

So, we just need to count the number of valleys in P. There are several ways to do this, a couple will be mentioned below:

  • Let’s call an index i a hill if P_{i-1} \lt P_i \gt P_{i+1}. Note that a subarray is a valley if and only if it doesn’t contain a hill index along with both of its neighbors.
    • Suppose we find all hill indices. Then, we can simply count the number of weird indices between each adjacent pair of them to obtain our answer.
    • Counting the number of subarrays between two hills is simple combinatorics.
    • You may refer to the setter’s code (below) for this approach.
  • Another method is to directly count valleys.
    • Suppose we fix the deepest point of the valley to be index i. Let’s count the number of valleys like this.
    • The left of i should be some decreasing sequence, and the right should be increasing.
    • Let left_i denote the longest decreasing sequence ending at i, and right_i denote the longest increasing sequence starting at i. These two can be found with dynamic programming in \mathcal{O}(N).
    • Then, we add left_i \times right_i to the answer, to account for all choices of subarrays with i as the deepest point (also including purely increasing/decreasing subarrays)
    • Adding up left_i \times right_i across all 1 \leq i \leq N gives us the answer
    • You may refer to the editorialist’s code (below) for this approach.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Setter's code (C++)
#ifdef WTSH
    #include <wtsh.h>
#else
    #include <bits/stdc++.h>
    using namespace std;
    #define dbg(...)
#endif

#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;

// -------------------- Input Checker Start --------------------

long long readInt(long long l, long long r, char endd)
{
    long long x = 0;
    int cnt = 0, fi = -1;
    bool is_neg = false;
    while(true)
    {
        char g = getchar();
        if(g == '-')
        {
            assert(fi == -1);
            is_neg = true;
            continue;
        }
        if('0' <= g && g <= '9')
        {
            x *= 10;
            x += g - '0';
            if(cnt == 0)
                fi = g - '0';
            cnt++;
            assert(fi != 0 || cnt == 1);
            assert(fi != 0 || is_neg == false);
            assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
        }
        else if(g == endd)
        {
            if(is_neg)
                x = -x;
            if(!(l <= x && x <= r))
            {
                cerr << "L: " << l << ", R: " << r << ", Value Found: " << x << '\n';
                assert(false);
            }
            return x;
        }
        else
        {
            assert(false);
        }
    }
}

string readString(int l, int r, char endd)
{
    string ret = "";
    int cnt = 0;
    while(true)
    {
        char g = getchar();
        assert(g != -1);
        if(g == endd)
            break;
        cnt++;
        ret += g;
    }
    assert(l <= cnt && cnt <= r);
    return ret;
}

long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
string readStringSp(int l, int r) { return readString(l, r, ' '); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
void readEOF() { assert(getchar() == EOF); }

vector<int> readVectorInt(int n, long long l, long long r)
{
    vector<int> a(n);
    for(int i = 0; i < n - 1; i++)
        a[i] = readIntSp(l, r);
    a[n - 1] = readIntLn(l, r);
    return a;
}

// -------------------- Input Checker End --------------------

int sumN = 0;

void solve()
{
    int n = readIntLn(1, 1e5);
    sumN += n;
    vector<int> p = readVectorInt(n, 1, n);
    assert(set<int>(p.begin(), p.end()).size() == n);
    vector<int> hills{0};
    for(int i = 1; i + 1 < n; i++)
        if(p[i] > p[i - 1] and p[i] > p[i + 1])
            hills.push_back(i);
    hills.push_back(n - 1);
    int ans = 0;
    for(int i = 0; i + 1 < sz(hills); i++)
    {
        int len = hills[i + 1] - hills[i] + 1;
        ans += len * (len - 1) / 2;
    }
    ans += n;
    cout << ans << endl;
}

int32_t main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0);
    int T = readIntLn(1, 1e5);
    for(int tc = 1; tc <= T; tc++)
    {
        // cout << "Case #" << tc << ": ";
        solve();
    }
    assert(sumN <= 2e5);
    readEOF();
    return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
    n = int(input())
    p = list(map(int, input().split()))
    left, right = [1]*n, [1]*n
    for i in range(1, n):
        if p[i] < p[i-1]: left[i] += left[i-1]
        if p[n-1-i] < p[n-i]: right[n-1-i] += right[n-i]
    print(sum(left[i] * right[i] for i in range(n)))
4 Likes

The observation for this problem is very very cool. Thanks for coming up with this problem!

1 Like

video solution is not that clear

1 Like

What is wrong with this solution ?

I am counting all decreasing then increasing subarrays. the decreasing array can be than given negative values. 5 out of 6 are passing only. Can someone point out case missing !

#include
using namespace std;

int main() {
int t ; cin >> t;
while(t–){
int n ;
cin >> n ;
int a[n] ;
for(int i=0 ; i<n ; i++){
cin >> a[i] ;
}
int ans = n , count=1 ;
int i=0 ;
while(i<n-1){
count=1 ;
while(i+1<n && a[i+1]<=a[i]){
count++ ;
i++ ;
}
while(i+1<n && a[i+1]>=a[i]){
count++ ;
i++ ;
}
ans = ans + count*(count+1)/2 -count;
}
cout << ans << “\n”;
}
return 0;
}

The answer can exceed the range of int, use a 64-bit datatype like long long instead.

I followed the Editorial, and understood the approach. But still facing one test case is getting wrong. Can anyone please help me where is my code is failing.
`#include <bits/stdc++.h>
using namespace std;

int main() {

ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int test_cases;
cin >> test_cases;
while(test_cases--!=0)
{
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i=0;i<n;i++)
    cin >> v[i];
    vector<int> hills;
    hills.push_back(0);
    for(int i=1;i<n-1;i++)
    {
        if(v[i-1]<v[i] && v[i]>v[i+1])
        hills.push_back(i);
    }
    hills.push_back(n-1);
    long long int ans=0;
    for(int i=0;i<hills.size()-1;i++)
    {
        int len=hills[i+1]-hills[i]+1;
        ans+=(len*(len-1))/2;
    }
    ans+=n;
    cout << ans << "\n";
}
return 0;

}
`