STKSTR - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: rudra_1232
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You have an array A of length N. At most once, you can multiply one of its elements by K.
Find the longest possible length of a non-decreasing subarray of A if the operation is performed optimally.

EXPLANATION:

Note that N \leq 1000, so the constraints allow for an \mathcal{O}(N^2) solution.
There are only N possible moves at all (choose an element and multiply it by K, so we can try each one of them and compute the answer for the resulting array i linear time; then take the maximum across everything.

So, suppose A_i has been multiplied by K.
We now want to find the longest subarray of A that’s non-decreasing.
This can be done using the following simple algorithm:

  • Let \text{cur} denote the current length of the non-decreasing subarray.
  • For each index j from 1 to N,
    • If A_j \geq A_{j-1}, increase \text{cur} by 1, since A_j can just be appended to the current non-decreasing subarray to increase its length.
    • Otherwise, set \text{cur} = 1 since we must start a new non-decreasing subarray.

The maximum value of \text{cur} during this process is the length of the longest non-decreasing subarray of the array.

This algorithm clearly takes linear time, so we have an \mathcal{O}(N^2) time algorithm, as we wanted.

Don’t forget to reset the value of the multiplied element before multiplying some other element!

It’s also possible to solve the problem in \mathcal{O}(N) time overall, this is left as an exercise to the reader.

Hint

If you multiply A_i by K, which subarrays can become non-decreasing that weren’t previously so?
Think of what information you need to store to find these subarrays (and their lengths) quickly.

TIME COMPLEXITY:

\mathcal{O}(N^2) per testcase.

CODE:

Editorialist's code (PyPy3) 
def calc(a):
    ans, cur = 1, 1
    for i in range(1, len(a)):
        if a[i] >= a[i-1]: cur += 1
        else: cur = 1
        ans = max(ans, cur)
    return ans

for _ in range(int(input())):
    n, x = map(int, input().split())
    a = list(map(int, input().split()))
    
    ans = calc(a)
    for i in range(n):
        a[i] *= x
        ans = max(ans, calc(a))
        a[i] //= x
    print(ans)
2 
#include<bits/stdc++.h>
using namespace std;
int main(){
    int tc; cin >> tc;
    for(int i = 1; i <= tc; ++i){
        int n, x; cin >> n >> x;
        vector<int> v(n);
        for(int i = 0; i < n; ++i) cin >> v[i];
        int ans = 1, curans = 1;
        for(int i = 1; i < n; ++i){
            if(v[i] >= v[i - 1]) curans++;
            else{
                int j;
                if(v[i] * x >= v[i - 1]){
                    curans++;
                    v[i] *= x;
                    for(j = i + 1; j < n; ++j){
                        if(v[j] >= v[j - 1]) curans++;
                        else break;
                    }
                    ans = max(ans, curans);
                    curans = (j - i);
                    v[i] /= x;
                    i = j - 1;
                }
                else{
                    ans = max(ans, curans);
                    curans = 1;
                }
            }
        }
        ans = max(ans, curans);
        cout << ans << '\n';
    }
}

O(n) approach kind of one pass
correct me if i am wrong…