LMP2E - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: kingmessi
Tester: pols_agyi_pols
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Chef feels comfortable without a jacket if the temperature is at least A, and feels comfortable with the jacket if the temperature is at most B.

Given a sequence of temperature changes, find the minimum number of times Chef needs to put on his jacket, while still being always comfortable.

EXPLANATION:

Observe that if the temperature is \lt A, then Chef must wear his jacket to be comfortable.
On the other hand, if the temperature is \gt B, then Chef must not wear his jacket to be comfortable.

If the temperature is in [A, B], it doesn’t matter if Chef is wearing his jacket or not.

Thus, we can simply simulate the process, only changing the state of Chef’s jacket when we’re forced to.
That is,

  • Iterate i from 1 to N.
  • When looking at T_i,
    • If A \le T_i \le B, Chef will always be comfortable. Nothing needs to be done.
    • If T_i \lt A, Chef is forced to wear his jacket.
      If Chef is not already wearing his jacket, increment the answer by 1.
    • If T_i \gt B, Chef is forced to remove his jacket.
      Note that this doesn’t increment the answer; it only forces Chef to remove the jacket.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, a, b = map(int, input().split())
    temps = list(map(int, input().split()))
    
    ans = 0
    jacket = 0
    for x in temps:
        if x < a:
            if jacket == 0:
                ans += 1
            jacket = 1
        if x > b:
            jacket = 0
    print(ans)
2

include <stdio.h>

int main() {
// your code goes here
int A,B,N;
int test;
int ans=0;
scanf(“%d”,&test);
for(int i=1;i<=test;i++){
scanf(“%d”,&N);
scanf(“%d”,&A);
scanf(“%d”,&B);
int arr[N];
for(int j=0;j<N;j++){
scanf(“%d”,&arr[j]);

//wear1,notwear2
if(j==0 && arr[j]<A){ans++;arr[0]=1;}
else if(j==0 && arr[j]>=A){arr[0]=2;}
else if(j!=0 && arr[j-1]==2 && arr[j]<A){ ++ans;arr[j]=1;}
else if(j!=0 && arr[j-1]==2 && arr[j]>=A){ arr[j]=2;}
else if(j!=0 && arr[j-1]==1 && arr[j]<=B){ arr[j]=1;}
else if(j!=0 && arr[j-1]==1 && arr[j]>B){ arr[j]=2;}
}

    	printf("%d \n",ans);

    	ans=0;
}

return 0;

}…why is this code not working? question was that codechef jacket wearing one