# Problem

Avery has an array of N positive integers. The i-th integer of the array is Ai.

A contiguous subarray is an m-countdown if it is of length m and contains the integers m, m-1, m-2, …, 2, 1 in that order. For example, `[3, 2, 1]` is a 3-countdown.

Can you help Avery count the number of K-countdowns in her array?

# Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the integers N and K. The second line contains N integers. The i-th integer is Ai.

# Output

For each test case, output one line containing `Case #x: y`, where `x` is the test case number (starting from 1) and `y` is the number of K-countdowns in her array.

# Limits

Time limit: 20 seconds.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
2 ≤ KN.
1 ≤ Ai ≤ 2 × 105, for all i.

2 ≤ N ≤ 1000.

2 ≤ N ≤ 2 × 105 for at most 10 test cases.
For the remaining cases, 2 ≤ N ≤ 1000.

# Sample

Sample Input

`312 31 2 3 7 9 3 2 1 8 3 2 14 2101 100 99 989 6100 7 6 5 4 3 2 1 100`

Sample Output

`Case #1: 2Case #2: 0Case #3: 1`

Explanation

In sample case #1, there are two 3-countdowns as highlighted below.

• 1 2 3 7 9 3 2 1 8 3 2 1
• 1 2 3 7 9 3 2 1 8 3 2 1

In sample case #2, there are no 2-countdowns.

In sample case #3, there is one 6-countdown as highlighted below.

• 100 7 6 5 4 3 2 1 100

Code & Algorithm

`/* author : @akash */#include<bits/stdc++.h>using namespace std;#define ll long long int#define pb push_back#define mod 1000000007#define ld long doubleint main(){   int T;   cin>>T; //Test cases   for(int t=1;t<=T;++t)   {    int N,K;    cin>>N>>K;    int A[N];    for(int i=0;i<N;++i)    {     cin>>A[i];    }    int ans_counter=0;    int decr_counter=0;    for(int i=1;i<N;++i)    {       if(A[i]==A[i-1]-1)       {     decr_counter++;       }       else       {        decr_counter=0;       }       if(A[i]==1 && decr_counter>=K-1)       {        ans_counter++;       }    }    cout<<"Case #"<<t<<": "<<ans_counter<<"\n";   }   return 0;}// time complexity of this Algorithm is : T(n)=O(N)`

# Test Set 1

For each element Ai, we can check whether it is a start of a K-countdown. In other words, we check whether Ai + j = K — j for all 0 ≤ j ≤ K. If the element Ai satisfies the condition, we can can increment 1 to our answer counter. This solution runs in O(N × K).

# Test Set 2

To solve this test set, we can loop through the elements and keep track of the number of consecutive elements such that the next element is one less than the previous element. We can do this by keeping a counter. If the current element is one less than the previous element, we increment this counter by 1. Otherwise, we reset the counter to 0. If the current element is 1 and our counter is at least K — 1, we know that the current element is the end of a K-countdown. We can increment 1 to our answer counter in this case.

This approach works since any pair of K-countdown subarrays does not overlap. This solution runs in O(N).

# Pseudocode

`answer_counter = 0  decreasing_counter = 0  for (i = 1 to N) {    if (A[i] == A[i - 1] - 1) {      decreasing_counter = decreasing_counter + 1    } else {      decreasing_counter = 0    }    if (A[i] == 1 and decreasing_counter >= K - 1) {      answer_counter = answer_counter + 1    }  }  print answer_counter`

Thank You.

Akash Kumar

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

## Coding on Social Engine PHP? ## Choosing my first steps as a Software Engineer ## GoReleaser v1.9 — the 10k stars release ## Food for Agile Thought #222 ## Forkability: The Surprising Impetus of any Open Source Project ## Creating a Unity Project: Exploring the interface and making a simple scene  ## Before You Graduate! For Every Computer Science Student ## Algorithm: Solve Sudoku ## Coding Career Shift: Getting Started ## Are you ready for a coding Bootcamp? 