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;
}
2 Likes
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
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