Google Kickstart 2020 Round C - Countdown. Unable to understand why my solution is incorrect

Question

I have attempted google's kickstart 2020 challenge. Round C problem 1 has me stumped for some. I have tried many different ways of completing the challenge. The problem looks easy but I can't complete it. The problem is that I do not understand what I am doing wrong. Please point me in the right direction or point the issue in with my code.

Problem

Google Kickstart 2020 - Round C | Problem 1 https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff43/00000000003380d2

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.

Pseudocode

    get the number of cases
    Loop in range(number of cases):
        get the N (number of elements), K(initial countdown value)
        get the array of values
        generate an array of the countdown sequence [K ... 1] - signature
        counter = 0

        Loop elem in range(Number of elements):
            if elem == K:
                if there is space to slice the array (length of signature) - possible signature
                    if possible signature == signature:
                        counter += 1

        print(counter)

Python 3 Code:

#!/usr/bin/python
# -*- coding: utf-8 -*-
noc = int(input(''))  # getting the number of cases # NOC- number of cases

# Loop over the # of cases

for c in range(noc):
    (N, K) = [int(i) for i in input('').split(' ')]  # getting N, K

    # N - number of elements given
    # K - initial countdown value
    # getting the elements

    caseList = [int(i) for i in input('').split(' ')]

    # generating a 'signature' or list of factorial for the countdown

    steps = [i for i in range(1, K + 1)][::-1]

    # counter for number of matches

    countdown = 0  # init value

    # loop over each element i  n list

    for i in range(N):

        # if element == K(init countdown number)

        if caseList[i] == K:

            # make sure there is space to get the sliced array

            if i <= len(caseList) - len(steps):

                # get the next m numbers if

                if caseList[i:i + len(steps)] == steps:
                    countdown += 1  # increment
    print countdown  # print the number of matches

Answer 1

There is no issue in @MFK34 except print() requires brackets in python 3 and he prints the answer immediately at end of loop and solution is not as expected. below is my revised solution.

#!/usr/bin/python
# -*- coding: utf-8 -*-
noc = int(input(''))  # getting the number of cases # NOC- number of cases
op = []

# Loop over the # of cases

for c in range(noc):
    (N, K) = [int(i) for i in input('').split(' ')]  # getting N, K

    caseList = [int(i) for i in input('').split(' ')]

    steps = [i for i in range(1, K + 1)][::-1]

    # counter for number of matches

    countdown = 0  # init value
    # loop over each element i  n list

    for i in range(N):

    # if element == K(init countdown number)

    if caseList[i] == K:

        # make sure there is space to get the sliced array

        if i <= len(caseList) - len(steps):

            # get the next m numbers if

            if caseList[i:i + len(steps)] == steps:
                countdown += 1  # increment
op.append(countdown)

for i,d in enumerate(op):
    print("Case #"+str(i+1)+":",d)

I have just stored the results in an array and later printed at end of inputs in order expected.

Answer 2

when the constraint already says 2<=N doesn't it mean that there will be no test case with array length = 0 or 1

Answer 3

I was wondering the same as well.

Lets look at the constraint given:

1 ≤ T ≤ 100. # Testcases
2 ≤ K ≤ N. # Value of K
1 ≤ Ai ≤ 2 × 105, for all i. # Index- 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.

Now suppose we have a testcase

nums = [1]
k = 1

One might think for K=1 the countdown= 1 right ? Actually No.

Read carefully, 2<=N, which means,

Array length must be of minimum length=2.

Expected result,
nums = [1]
K    = 1
coutdown = 0

Answer 4

Your solution seems fine, except that the output isn't as specified and not for Python 3, but 2, simply change it to:

print(f'Case {c}: {countdown}')

Apart from that, you're doing a bit more work than is needed. You really only need to go through the entire list once to count K-countdowns.

For example:

import sys
from io import StringIO

sys.stdin = StringIO('3\n2 2\n2 1\n8 2\n0 2 1 2 2 1 2 1 0\n0 2\n\n')

t = int(input())
for c in range(t):
    (n, k) = [int(i) for i in input().split()]
    a = [int(i) for i in input().split()]
    # initialise goal, position in array and count
    goal, i, count = k, 0, 0
    while i < n:
        # if item in current position matches current goal
        if a[i] == goal:
            # then next goal item is one less
            goal -= 1
            # until all in K-countdown were found
            if goal == 0:
                # then start over and increase count
                goal = k
                count += 1
            # look at the next position
            i += 1
        # else (current item doesn't match goal), if already looking for start of K-countdown
        elif goal == k:
            # look at the next position
            i += 1
        # else (current item doesn't match goal, goal wasn't start of K-countdown)
        else:
            # look for start of K-countdown
            goal = k
    print(f'Case #{c}: {count}')

Answer 5

I don't find any issue with your solution. Might be something your output format.

You are supposed to output in the form of Case #x: y, where x is the test case number (starting from 1) and y is the number of K-countdowns in her array.

Example:

Case #1: 2

Case #2: 0

Case #3: 1

Note: Make sure you are using Python 2.x if you are using print x instead of print(x)