PERRANGES - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Dynamic programming

PROBLEM:

A pair of arrays A and B of the same length are said to be perfect if it’s possible to create an array C such that:

  • For each i, either C_i = A_i or C_i = B_i.
  • C_i \lt C_{i+1} for each 1 \leq i \lt |C|

You’re given two arrays A and B of length N.
Count the number of pairs (L, R) such that 1 \leq L \leq R \leq N and the arrays A[L\ldots R] and B[L\ldots R] are perfect.

EXPLANATION:

First, let’s understand how to decide when a pair of arrays A and B can be perfect, by constructing a valid C.
It’s not hard to see that a simple greedy algorithm works - that is, for each i, choose C_i = \min(A_i, B_i) if this satisfies C_i \gt C_{i-1}, and choose C_i = \max(A_i, B_i) otherwise.
If even the latter fails for some i, (A, B) is not perfect; otherwise it can be.
The proof of this is simple via an exchange argument, applied from left to right.

We now extend this idea to counting the number of valid pairs.

The key observation here is that in our above greedy algorithm, we only really cared about the last element of the array, i.e. when trying to decide the value of C_i, only C_{i-1} matters.
This allows for the use of dynamic programming.

First, for convenience, let’s assume A_i \lt B_i for all i (if not, swap them).
Now define dp(i, 0) to be the number of left endpoints such that the pair (A[L\ldots i], B[L\ldots i]) is perfect, with the last element of the greedily constructed array being A_i.
Similarly, define dp(i, 1) to be the number of valid left endpoint such that the last element of the constructed array is B_i.

To compute dp(i, 0) and dp(i, 1):

  • We always have one valid left endpoint for ending with A_i: L = i.
  • As for L \lt i, there are a couple of possibilities.
    1. If A_i \gt B_{i-1}, then it’s always possible to extend a valid subarray ending at i-1, to a valid subarray ending at i by appending A_i.
      So, dp(i, 0) = dp(i-1, 0) + dp(i-1, 1) + 1 here.
      dp(i, 1) will just be 0.
    2. If B_{i-1} \gt A_i \gt A_{i-1}, only those subarrays ending with A_{i-1} can be extended.
      So, dp(i, 0) = dp(i-1, 0) + 1.
      dp(i, 1) will be either 0 or dp(i-1, 1), depending on how B_i compares to B_{i-1}.
    3. If A_i \lt A_{i-1}, no extension from smaller indices is possible; so dp(i, 0) = 1.
      dp(i, 1) will be the sum of dp(i-1, 0) and/or dp(i-1, 1), depending on how B_i compares to A_{i-1} and B_{i-1}.

Once all the dp values are known, the final answer is simply the sum of
dp(i, 0) + dp(i, 1)
across all 1 \leq i \leq N.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    for i in range(n):
        if a[i] > b[i]: a[i], b[i] = b[i], a[i]
    
    dp = [[1, 0] for i in range(n)]
    ans = 1
    for i in range(1, n):
        if a[i] > b[i-1]: dp[i][0] += dp[i-1][0] + dp[i-1][1]
        elif a[i] > a[i-1]:
            dp[i][0] += dp[i-1][0]
            if b[i] > b[i-1]: dp[i][1] += dp[i-1][1]
        else:
            if b[i] > a[i-1]: dp[i][1] += dp[i-1][0]
            if b[i] > b[i-1]: dp[i][1] += dp[i-1][1]
        ans += dp[i][0] + dp[i][1]
    print(ans)
2

I solved it using SLIDING-WINDOW, heres my code :

void solve() {
  ll n;
  cin >> n;
  vector<ll> a(n), b(n);
  rep(i,n) cin >> a[i];
  rep(i,n) cin >> b[i];
  
  ll l = 0, r = 0;
  vll prev(n, LLONG_MAX);
  
  auto check = [&](ll idx) {
      prev[idx] = min(a[idx], b[idx]);
      for(ll i = idx+1; i<=r; i++) {
          ll mn = min(a[i], b[i]);
          ll mx = max(a[i], b[i]);
          if(prev[i-1] < mn) prev[i] = mn;
          else if(prev[i-1] < mx) prev[i] = mx;
          else return true;
      }
      return false;
  };
  
  auto update = [&]() {
      if(!r) {prev[0] = min(a[0], b[0]); return;}
      
      ll mn = min(a[r], b[r]);
      ll mx = max(a[r], b[r]);
      
      if(mn > prev[r-1]) {prev[r] = mn; return;}
      else if(mx > prev[r-1]) {prev[r] = mx; return;}
      
      while(l < r && check(l)) l++;
  };
  
  ll ans = 0;
  while(r < n) {
      update();
      ans += r-l+1;
      r++;
  }
  print(ans);
}
3

Can someone please help me to find why my code fails at latter cases. Would be a big help

include <bits/stdc++.h>
using namespace std;

int main() {
// your code goes here
int T; cin>>T;
while(T–){
int n;cin>>n;
if(n==1) cout<<1<<endl;
vector a(n),b(n);
for(auto &x:a) cin>>x;
for(auto &x:b) cin>>x;
vector<pair<int,int>> c(n,{1,1});//{mx,mn}
c[n-1]={1,1};
for(int i=n-2;i>=0;i–){
int mx=max(a[i],b[i]);
int mn=min(a[i],b[i]);
if(mx<max(a[i+1],b[i+1])){
c[i].first=c[i+1].first+1;
}
if(mx<min(a[i+1],b[i+1])){
c[i].first=max(c[i].first,c[i+1].second+1);
}
if(mn<max(a[i+1],b[i+1])){
c[i].second=c[i+1].first+1;
}
if(mn<min(a[i+1],b[i+1])){
c[i].second=max(c[i].second,c[i+1].second+1);
}
}
//for(auto [x,y]:c) cout<<x<<" "<<y<<endl;
//cout<<endl<<endl;
int ans=0;
for(auto& [x,y]:c) ans+=max(x,y);
cout<<ans<<endl;
}
}

4

Avoid pasting your whole code. Instead you can just paste your submission link.
Regarding your solution, can you define your dp states once, so that I can understand it effectively.

1 Like
5

Okay i will keep that in mind. The dp states in the code are like dp(i,0)=num of perfect range from i to n if i take the maximum element at ith index. For dp(i,1) i take the minimum of the both element

6

I didnt taught this would be a DP one,

I just tried finding all windows and calculating all subarrays in those.

7

The worst case complexity is O(n*n), Why is this even getting accepted? The test cases might be weak

9

I think that you analyzed its complexity in wrong way… for it to be O(n*n) it should approximately run a O(n) loop every time… suppose we get a such then it would obviously run a for loop of about O(n) but after that next O(n) can’t happen as now l==r, so, it would now run around O(1) approx… if every index is bad then l==r holds every time and my loop runs from (l–>r) so TC = O(n) overall!!

10

include <stdio.h>
include <stdlib.h>

typedef long long ll;

ll count_perfect_pairs(int *A, int *B, int N) {
ll dp0 = 0, dp1 = 0; // dp values at (i-1)
ll total = 0;

for (int i = 0; i < N; i++) {
    if (A[i] > B[i]) {
        // Ensure A[i] < B[i] by swapping
        int t = A[i];
        A[i] = B[i];
        B[i] = t;
    }

    ll new0 = 1, new1 = 0;

    if (i > 0) {
        // Extend with A[i]
        if (A[i] > A[i-1] && A[i] > B[i-1]) {
            new0 = dp0 + dp1 + 1;
        } else if (A[i] > A[i-1]) {
            new0 = dp0 + 1;
        } // else new0 stays as 1 (only new segment)

        // Extend with B[i]
        if (B[i] > A[i-1] && B[i] > B[i-1]) {
            new1 = dp0 + dp1;
        } else if (B[i] > B[i-1]) {
            new1 = dp1;
        } // else new1 = 0
    }

    dp0 = new0;
    dp1 = new1;
    total += dp0 + dp1;
}

return total;

}

int main() {
int N;
scanf(“%d”, &N);

int *A = malloc(N * sizeof(int));
int *B = malloc(N * sizeof(int));

for (int i = 0; i < N; i++) scanf("%d", &A[i]);
for (int i = 0; i < N; i++) scanf("%d", &B[i]);

ll result = count_perfect_pairs(A, B, N);
printf("%lld\n", result);

free(A);
free(B);
return 0;

}

11

https://www.codechef.com/viewsolution/1182801133
can you please check why is it failing

12

just use ll (long long) instead int