KMAX2 - Editorial

PROBLEM LINK:

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

Author: Janmansh Agarwal
Tester: Anay Karnik
Editorialist: Mohan Abhyas

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You are given a sequence of integers A_1, A_2, \ldots, A_N and an integer K. Find the number of contiguous subsequences A_L, A_{L+1}, \ldots, A_R such that R-L+1 \ge K and the K-th element of the subsequence (A_{L+K-1}) is equal to the maximum of all elements of the entire sequence.

EXPLANATION:

Let A_{max} = max(A_1,\dots,A_N)

If A_i = A_{max} number of contiguous subsequences A_L, A_{L+1}, \ldots, A_R such that R-L+1 \ge K and the K-th element of the subsequence A_{L+K-1} = A_i is N-i+1 as L = i-k+1, i \le R \le N .

Final answer is sum of number of subsequences for such A_is

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

SOLUTIONS:

[details = “Editorial’s Solution”]

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define forn(i,e) for(ll i = 0; i < e; i++)

void solve()
{
	ll n,k;
    cin>>n>>k;
    vector<ll> A(n);
    forn(i, n) cin>>A[i];
    ll ans = 0;
    ll mx = A[0];
    forn(i, n)
    {
        mx = max(mx, A[i]);
    }
    for(int i = k-1; i < n; i++)
    {
        if(A[i] == mx)
        {
            ans += n-i;
        }
    }
    cout<<ans<<endl;
}

int main()
{
	ll t=1;
	cin >> t;
    forn(i,t) {
    	solve();
    }
    return 0;
}
1 Like

for n=6; and k=3;
1 2 3 1 2 3
it gives 5 how ?
as i can get this it should be 4 because as below
(1,2,3)
(1,2,3,1)
(1,2,3,1,2)
(1,2,3,1,2,3)
can someone explain…

1 Like

I tried something similar approach but it gave WA, as per asked in question the max value of original sequence should be kth value of our subsequence. So, I first searched the index of max value then checked if there are k-1 elements present before this, if yes I just did (n - maxPos) else answer is zero…

Simplifying that all the numbers after max(including it) are counted as answer but there should be at least k-1 elements before max element, right??

Any suggestions please.

Actually, for the first number 3, program gives 4 for elements 3, 1, 2, 3 and again when it reaches the last 3 for it also we get extra 1 which sums up to 5.

1 Like

ya that i understood programmatically it is correct but according to question it ask sum of all the subsequences, so subsequences we have only 4 then how above code is correct

Hello @sanjeev342. These are the sequences for your test case
(1,2,3) from L = 1 to R = 3
(1,2,3,1) from L = 1 to R = 4
(1,2,3,1,2) from L = 1 to R = 5
(1,2,3,1,2,3) from L = 1 to R = 6
(1,2,3) from L = 4 to R = 6

3 Likes

Can somebody explain what is wrong in my code:

#include
#include
#include

using namespace std;

typedef long long int great_int;

great_int solve(vector& arr, int K) {
int result = 0;
int xMax = arr[0];
vector max_index(1, 0);

for (int i = 1; i < arr.size(); i++)
{
if (arr[i] > xMax) {
xMax = arr[i];
max_index.clear();
max_index.push_back(i);
}
else if (arr[i] == xMax) {
max_index.push_back(i);
}
}

for (int i = 0; i < max_index.size(); i++)
{
if (max_index[i] >= K - 1) result += (great_int)arr.size() - (great_int)max_index[i];
}

return result;
}

int main() {
// your code goes here
ios::sync_with_stdio(0); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
int T;
string temp;
cin >> T;
getline(cin, temp);
while (T–)
{
int N, K;
vector arr;
cin >> N >> K;
getline(cin, temp);

  for (int i = 0; i < N; i++)
  {
  	int A;
  	cin >> A;
  	arr.push_back(A);
  }
  getline(cin, temp);

  cout << solve(arr, K) << endl;

}
return 0;
}

Why is this code not working on Task 2?

#include <vector>
#include <climits>
#include <iostream>
using namespace std;
typedef long long ll;

int solve(ll arr[], ll n, ll k)
{
    ll m = arr[0];
    for (ll i=0; i<n; i++)
    {
        m = max(m, arr[i]);
    }
    ll ans=0;
    for(ll i=k-1; i<n; i++){
        if(arr[i] == m){
            ans += n - i;
        }
    }

    return ans;
}

int main()
{
    ll t;
    cin >> t;
    while (t--)
    {
        ll n, k;
        cin >> n >> k;
        ll arr[n];
        for (ll i = 0; i < n; i++)
        {
            cin >> arr[i];
        }

        cout << solve(arr, n, k) << endl;
    }
    return 0;
}

1 Like

why isn’t this code working?

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair

void solve(){
    int n,k;
    cin>>n>>k;
    vector <int> v(n);        
    for (auto i = 0; i < n; i++){
        cin>>v[i];
    }
    
    int a = *max_element(all(v));
    int ans = 0;
    for (auto i = k - 1; i < n; i++){
        if (v[i] == a){
            ans += n - i;
        }
    }
    cout<<ans;
}

int main(){
    int t;
    cin>>t;
    while (t--){
        solve();
        cout<<'\n';
    }
}

can somebody help me to understand what the question is exactly saying? As I am a beginner, I am unable to understand the question properly.

How is my approach any different than the Editorial’s Approach.
Following is my code for each testcase:

        int n,k,m=INT_MIN,ind=-1;cin>>n>>k;
        vector<int>v(n);
        for(int i=0;i<n;i++){
            cin>>v[i];
            if(m==INT_MIN||m<v[i]){m=v[i];ind=i;}
        }
        int ans=n-ind;
        if(ind<k-1)ans=0;
        cout<<ans<<endl;

what about the the the test case where the array contains the same number.
for eg. if array size is 5 and k = 3 and arr[]: 5 5 5 5 5 your code give o/p = 0. but the correct o/p is 3

1 Like

Please refer the video editorial

Can int function return long long?

Number of sub arrays can exceed the limit of int data type, use long and get AC.

1 Like

Quick reminder:

2 Likes

thanks got it

Oh got it. Thank you

I’m confused, if N <= 2.10^5, how can we get subarrays more than N

Total number of sub-arrays in an array of length N are \cfrac{N\times(N + 1)}{2}.

Proof:
Number of Sub-arrays of length 1= N
Number of Sub-arrays of length 2 = N - 1
…
Number of Sub-arrays of length N = 1

Total number of Sub-arrays = 1+2+3+\dots+N = \cfrac{N\times(N + 1)}{2}

so., the worst case input for this problem would be

N = 2\times 10^5
K = 1
A_i = 1\ \forall\ i\isin[1, N]

1 Like