Google Kick start Round C 2020

List of Algorithms and data structures for Competitive Programming

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?

Solution:

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 per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
2 ≤ K ≤ N.
1 ≤ Ai ≤ 2 × 105, for all i.

Test set 1

2 ≤ N ≤ 1000.

Test set 2

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

Sample

Input

Output

3
12 3
1 2 3 7 9 3 2 1 8 3 2 1
4 2
101 100 99 98
9 6
100 7 6 5 4 3 2 1 100
Case #1: 2
Case #2: 0
Case #3: 1

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:

#include <bits/stdc++.h>

using namespace std;

int main() {
int t;
cin>>t;
int n,k;
for(int i=0;i<t;i++){
cin>>n>>k;
int ans=0;
int arr[n];
for(int j=0;j<n;j++){
cin>>arr[j];
}
for(int j=0;j<n;j++){
if(arr[j]==k){
int x=k;
for(int a=j;a<j+k;a++){
if(arr[a]==x){
x — ;
}
else{
break;
}
}
if(x==0){
ans++;
}
}
}
cout<<”Case #”<<i+1<<”: “<<ans<<endl;
}
}

Tags:

kickstart round c,kickstart google coding competition,kickstart round b,kickstart 2020,kickstart 2020 round a,kickstart 2020 round b,kickstart 2020 round c,kickstart 2020 answers,kickstart 2020 round b solution,kickstart 2020 round c solution,google kickstart round c,google kickstart 2020 round c,google kickstart 2020 solutions,google kickstart 2020 round a solutions java,google kickstart 2020 python,google kickstart 2020 java,google code jam 2020,google code jam round 2,