CRIMSHIFT - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest

Author: Riddhish Lichade

DIFFICULTY:

EASY-MEDIUM

PROBLEM:

The crime has severely increased in city A in past few months. The number of criminals in the local prison of city A has increased beyond its limit, which has caused many problems in the jail. The commissioner decided to shift some criminals to a prison in city B.

There are N criminals in the local prison of city A. S criminals needs to be shifted to prison in city B. To decide which criminals should be shifted, the commissioner made all the N(1 to N) criminals to stand in a queue, with a number label A_i in their hands denoting the severity of the crime they had committed. Higher the value of A_i, higher is the severity of their crime.

The commissioner now asked your help to choose the S criminals who will be transferred to prison in city B. Before choosing, the commissioner imposed two conditions:

  • If the crime severity of any criminal exceeds x, then there is chance of them running while they are transferred to city B as they are very severe criminals.
  • The chosen criminals has to form a contagious segment of criminals. Find the number of ways you can choose the S criminals.

EXPLANATION:

The severity of crimes forms an integer sequence. Find all the contiguous sequences without any integer greater than S. If the length of any sequence is L, then we can choose x criminals from them in L - x + 1 ways.

SOLUTIONS:

Setter's Solution 
from sys import stdin
for _ in range(int(stdin.readline())):
    n, s, x = map(int, stdin.readline().strip().split())
    l = list(map(int, stdin.readline().strip().split()))
    z=[-1]
    for i in range(n):
        if(l[i]>x):
            z.append(i)
    z.append(n)
    ans=0
    for i in range(1,len(z)):
        diff=z[i]-z[i-1]-1
        ans+=max(diff-s+1,0)
    print(ans)