MOOCHEF - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: rohan_217
Tester: wasd2401
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Chef likes integers between L and R.
Each time he sees one, his happiness increases by 1; each time he sees something else, it decreases by 1.

Given an array A of N integers, Chef will look at the elements in order from 1 to N.
Find the minimum and maximum happiness he’ll achieve in the process.

EXPLANATION:

This is a simple implementation task.

Store Chef’s current happiness (say H), the minimum happiness (M_1), and the maximum happiness (M_2).
Initially, all three of these are 0.
Then, for each i from 1 to N,

  • If L \leq A_i \leq R, increase H by 1.
  • Otherwise, decrease H by 1.
  • Then, update M_2 and M_2 with H appropriately.

At the end of this, print the values of M_1 and M_2.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n, l, r = map(int, input().split())
    cur, mn, mx = 0, 0, 0
    for x in list(map(int, input().split())):
        if l <= x <= r: cur += 1
        else: cur -= 1
        mn = min(mn, cur)
        mx = max(mx, cur)
    print(mx, mn)