INOI1902-Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice

Editorialist: Adithya Dsilva

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Binary Search (generalized version), Dynamic Programming, Longest Increasing Subsequence

PROBLEM:

You are given an array A consisting of N integers. You are also given an integer L.
A sequence of indices (i_1,i_2,\dots,i_k) is said to be an interesting sequence of size k if

A_{i_1}\ge A_{i_2}\ge \dots \ge A_{i_k}

The cost of an interesting sequence is defined as

\min\{|i_2-i_1|, |i_3-i_2|,\dots,|i_k-i_{k-1}|\}

Find the maximum possible cost over all interesting sequences of size L.

QUICK EXPLANATION:

We start by considering the case where all elements in A are distinct.

We maintain an array P such that

A_{P_1}>A_{P_2}>\dots>A_{P_N}

Thus, P_i refers to the index of the i^{th} largest element in array A.

Any subsequence of the set (P_1,P_2,\dots,P_N) is thus an interesting sequence. Also, if (i_1,i_2,\dots,i_k) is an interesting sequence, then it is a subsequence of array P.

For a given cost D, we try to determine if there exists a subsequence (P_{i_1},P_{i_2},\dots,P_{i_L}) of P with cost \ge D. We can determine this using DP in O(N^2). The monotonic condition over D enables us to binary search over the valid values of D to determine the maximum possible cost in O(N^2\log N).

For the case where elements are non-distinct, we determine valid values i,j such that A_{P_i}=A_{P_j} and |P_i-P_j| is maximum. We then set the lower bound of our search space to |P_i-P_j| and proceed binary searching as usual.

EXPLANATION:

Note : We use 1-based indexing in the editorial.

We start by only considering the case where all elements in A are distinct.

We know that sequence (i_1,i_2,\dots,i_k) is an interesting sequence only if A_{i_1}>A_{i_2}>\dots>A_{i_k} (the equality sign has been removed as we are only dealing with distinct elements in array A)

We maintain an array P such that, P_i refers to the index of the i^{th} largest element in array A.
In other words,

A_{P_1}>A_{P_2}>\dots>A_{P_N}

should hold.

How do we construct array P?

This can be achieved by making an array of pairs B, where B_i\text{.first}=A_i and B_i\text{.second}=i. We can then sort B in non-decreasing order of the first term of the pairs. Then,

B_1\text{.first}>B_2\text{.first}>\dots>B_N\text{.first}

which implies

\large A_{B_1\text{.second}}>\dots>A_{B_N\text{.second}}

Therefore, P_i=B_i\text{.second} for all valid i.

Claim : Any subsequence of the set (P_1,P_2,\dots,P_N) is an interesting sequence.

Proof

As per our definition of array P,

A_{P_1}>A_{P_2}>\dots>A_{P_N}

Thus, A_{P_a}>A_{P_b} if and only if a<b.

Now, if (P_{i_1},P_{i_2},\dots,P_{i_k}) is a subsequence of the aforementioned set, then i_1<i_2<\dots<i_k must hold.

This would imply

A_{P_{i_1}}>A_{P_{i_2}}>\dots>A_{P_{i_N}}

which means this subsequence is an interesting sequence!

Note that the converse of the above claim is also true. If any sequence (i_1,i_2,\dots,i_k) is an interesting sequence, it is a subsequence of array P.

Proof

Let (i_1,i_2,\dots,i_k) be an interesting sequence. Let j_1,j_2,\dots,j_k be values such that P_{j_x}=i_x for all valid x.

Now, as (i_1,i_2,\dots,i_k) is an interesting sequence,

\large A_{P_{j_1}}>A_{p_{j_2}}>\dots>A_{p_{j_k}}\tag1

holds.

In our previous claim, we proved that A_{P_a}>A_{P_b} if and only if a<b. Thus, from (1) we incur that, j_1<j_2<\dots<j_k.

Thus, sequence i_1,i_2,\dots,i_k is a subsequence of array P!

The answer to this problem is thus, the maximum possible cost, over all subsequences of array P of size L.

Can we determine for some fixed value D, if there exists an subsequence of P with cost \ge D? We could then simply find the largest value of D, such that a subsequence of size L with cost D exists.

More formally, for a particular value of D, we try to determine if there exists a subsequence (P_{i_1},P_{i_2},\dots,P_{i_L}) such that

\large D\ge \max\{|P_{i_2}-P_{i_1}|,|P_{i_3}-P_{i_2}|,\dots,|P_{i_L}-P_{i_{L-1}}|\}

How do we do this? This can be solved in O(N^2) by tweaking the DP solution of the Longest Increasing Subsequence problem.

Note : Readers are requested to acquaint themselves with the DP solution of the LIS problem, as the states of the DP shall not be discussed in-depth here.

Define DP_i as the longest subsequence of P with cost \ge D, where the last term of the subsequence is P_i. DP_i is defined as 1+DP_x\space(x<i), where |P_i-P_x|\ge D and DP_x is maximum possible. If there exists no valid value for x, DP_i=1, which is the base case of our DP solution.

Formally, we define

\large DP_i=\max(1,\max^{1\le x<i}_{|P_i-P_x|\ge D}(DP_x+1))

Then we check if there exists a valid i such that DP_i\ge L. If yes, it implies that it is possible to have an interesting sequence of size L with cost \ge D. Otherwise, it is impossible.

Call the above DP solution \text{Possible}(). \text{Possible}(D) returns true if it is possible to have an interesting sequence of size L with cost \ge D and returns false otherwise. Thus, we simply have to find the largest valid value D such that \text{Possible}(D) returns true.

However, since we are checking over all possible values of D, this solution is not efficient enough to pass the last subtask! Before delving into the optimal solution, let us analyze what we have done so far.

Analysis of above approach

Computing the values of array P can be done in O(N\log N) by sorting array A.

The DP solution takes O(N^2) time to determine the size of the largest subsequence with cost \ge D. As there are N different valid values for D (the lower and upper bounds on D are 0 and N-1 respectively), determining the maximum possible cost takes O(N^2*N)=O(N^3) time.

Thus, the overall time complexity is

O(N\log N+N^3)\approx O(N^3)

which won’t pass in the last 2 subtasks!

We can greatly optimize our solution by making one vital observation.

Claim : If \text{Possible}(D) returns false for some D, then \text{Possible}(D') also returns false for all D'\ge D.

Proof

Let us assume the contrary. Imagine \text{Possible}(D) return false and assume there exists a D'\ge D such that \text{Possible}(D') returns true.

\text{Possible}(D') returns true means that the maximum cost possible over all subsequences of size L is \ge D'. This would imply that maximum cost possible is \ge D, since D'\ge D.

Hence, \text{Possible}(D) should actually return true. Thus contradiction and we are done!

As our claim proves the monotonicity of the problem, we can efficiently reduce the search space by binary searching on the maximum possible cost (the lower and upper bounds of the search space are 0 and N-1 respectively)! A tutorial on this technique has been linked in the prerequisites above.

Coming back to the original constraints, let us handle the case where the elements in A are non-distinct. When elements are non-distinct,

P_1\ge P_2\ge\dots\ge P_N

and the equality condition tells us that there might exist valid integers i,j\space(i\ne j) such that A_{P_i}=A_{P_j}.
This would imply, (P_i,P_j,P_i,\dots) is an interesting sequence which is not a subsequence of P.

Take for example N=3,L=3 and A=\{5,5,5\}.
The solution discussed earlier would yield answer 1. However, the best sequence is (1,3,1) with cost 2.

Thus, we have to handle the case where equality holds separately. Imagine there exists integers i,j such that, A_{P_i}=A_{P_j} and i\ne j.

Claim : An optimal interesting sequence with maximal cost, where the first two elements are P_i and P_j is (P_i,P_j,P_i,P_j,P_i,\dots)

Proof

The proof is simple.

The cost of an interesting sequence where the first two elements are P_i and P_j can never exceed |P_i-P_j|. Thus (P_i,P_j,P_i,\dots) is an optimal interesting sequence as the cost is ensured to not fall below |P_i-P_j|, which is the maximum possible cost.

So, we consider all pairs P_i,P_j such that A_{P_i}=A_{P_j}, and determine the maximal possible value of |P_j-P_i|. Call this value low.

We then set low as the lower bound of our search space and then binary search, as we now know that there exists an interesting sequence with cost greater than or equal to low.

SOLUTION SNIPPET:

bool Possible(vii A, int delta, int N, int L){
    vi DP(N, 1); //Base case DP[] = 1
    
    for(int x = 1; x < N; x++){
        for(int i = 0; i < x; i++){
            if(abs(A[x].second - A[i].second) >= delta){
                //If Absolute difference >= delta
                DP[x] = max(DP[x], DP[i] + 1);
            	//DP recurrence relation
            }
        }
        if(DP[x] >= L) //Interesting sequence with cost >= delta found
            return 1;
    }
    return 0; //Not possible to have cost >= delta
}

vii A(N); //Vector of pairs
for(int x = 0; x < N; x++){
    cin >> A[x].first;
    A[x].second = x;
}
sort(A.rbegin(), A.rend()); //Sort in decreasing order

int low = 0; //Lower bound for the binary search
for(int x = 0; x < N; x++){
    for(int i = x + 1; i < N; i++){
        if(A[x].first != A[i].first) break;
        //If non-distinct elements exist
        low = max(low, abs(A[x].second - A[i].second));
    }
}

int left = low, right = N - 1; //The upper bound on the cost
while(left < right){
    int mid = (left + right + 1) / 2;
    // Ceil(a/b) is equivalent to (a + b - 1) / b
    //Implementation Trick

    if(Possible(A, mid, N, L)) left = mid; //Possible
    else right = mid - 1; //Not possible
}
cout << left << endl; //The answer!

TIME COMPLEXITY:

Sorting the input array takes O(N\log N)

Finding the lower bound low takes O(N^2) time as there are 2 nested loops iterating over the sorted array.

There are at max, O(\log N) calls to function Possible() as the search space is reduced by half after each query. Function Possible() takes O(N^2) time as discussed in the EXPLANATION section.

Thus, the overall complexity is

O(N\log N+N^2+N^2\log N)\approx O(N^2\log N)

SOLUTIONS:

Editorialist’s solution can be found here.

SIMILAR PROBLEMS:

760B
1260D
1189F

Did you like the editorial? Do you have any other approaches to the problem? Any suggestions? Comment them below!

Experimental: For better evaluation of my editorials, I request all readers to rate the editorial (on a scale from 1-5, where 5 represents an awesome :star_struck: editorial)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters

Also don’t forget to up-vote this post if you liked it ! :smile:

10 Likes
2

Hi,

Can you please tell me why I have got a WA in this implementation.

#include <bits/stdc++.h>
using namespace std;
const int N = 3010;
int bs[N], n, len, dp[N];
vector<pair<int, int> >a;

bool cost(int dist) {
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(a[i].first == a[j].first && abs(a[i].second - a[j].second) >= dist)
                return true;
        }
    }
    for(int i = 1; i <= n; i++) {
        dp[i] = 1;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(a[i].first >= a[j].first && abs(a[i].second - a[j].second) >= dist) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        ans = max(ans, dp[i]);
    }
    return ans >= dist;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--) {
        cin >> n >> len;
        a.clear();
        a.push_back(make_pair(0, 0));
        for(int i = 1; i <= n; i++) {
            int x;
            cin >> x;
            a.push_back(make_pair(x, i));
            bs[i] = 0;
        }
        sort(a.begin() + 1, a.end());
        int l = 1, r = n;
        while(l <= r) {
            int mid = (l + r) / 2;
            bs[mid] = (cost(mid)) ? (1) : (0);
            if(bs[mid] == 1) {
                l = mid + 1;
            }
            else {
                r = mid - 1;
            }
        }
        int ans = 0;
        for(int i = n; i > 0; i--) {
            if(bs[i] == 1) {
                ans = i;
                break;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Thanks in advance for helping me!!

3

Please link your submission over here!
Will check and tell after that.

4

Here you go:
CodeChef: Practical coding for everyone.

5

Thanks for your time, but I found out my mistake.

It was in line 29.

I had written

if(ans >= dist)

The correct statement was

if(ans >= len)

It was a dumb mistake, still thanks for giving time and sorry for taking your time. :stuck_out_tongue:

1 Like
6

can you provide some more similar type of problems?

7

It is provided at the end.

1 Like