PIPSQUIK - Editorial

Practice
Contest: Division 1
Contest: Division 2

Author: Sachin Yadav
Tester: Vraj Patel
Editorialist: Nishikant Parmar

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Simple conditional operators

PROBLEM:

There is a man of height H. He can duck by Y_{1} and jump by Y_{2}. There are barriers of two types namely t= 1 and t = 2. The barriers of type 1 start from a height X above the ground while the barriers of type 2 start from the ground and extend up to the height X above the ground. (Refer to the figure given in problem for better understanding )
He has life L and every time he can’t pass a barrier by bending or jumping he smashes into the barrier, breaking it, which costs him a single life and the barrier is considered passed. He can pass the barrier even if the barrier merely touches him on bending or jumping.
If after breaking a barrier no life is left, the man dies immediately, unable to pass that barrier.

How many barriers can he cross before dying finally?

QUICK EXPLANATION:

For each barrier, we look for condition in which man can pass it and decrease the life count if he can not pass. As soon as life becomes zero we stop traversing.

EXPLANATION:

This problem can be solved by traversing through the barriers one-by-one and checking the given conditions.

Case 1 : When t = 1

Since the barrier starts from a height X above the ground, the man can cross the barrier only if his height is less than or equal to X, the minimum height the man can achieve is H-Y_{1}, so if his minimum height is more than X then decrease the life by 1.

Case 2: When t = 2

Since the barrier extends up to a height X from the ground; the man can cross the barrier only if he jumps a height more than or equal to X. Thus, if Y_{2} is less than X, then decrease the life by 1.

While traversing the array if life becomes zero, then you should stop traversing. In the end, the answer is the number of barriers traversed.

Note: Do not count the barrier at which life becomes zero.

TIME COMPLEXITY

O(N)

SOLUTIONS:

Setter's Solution
#include<iostream>
using namespace std;
int arr[1001], types[1001];
int main()
{
    int T; cin>>T;
    while(T--)
    {
        int N,H, Y1, Y2, L; cin>>N>>H>>Y1>>Y2>>L;
        int count=0;
        for(int i=0; i<N; i++) cin>>types[i]>>arr[i];
        for(int i=0; i<N; i++)
        {
            if(types[i]==1 && arr[i]<H-Y1)
                --L;
            else if(types[i]==2 && arr[i]>Y2)
                --L;
            if(L==0) break;
            ++count;
        }
        cout<<count<<"\n";
    }
    return 0;
}
Tester's Solution
for _ in range(int(input())):
	N,H,y1,y2,L = [int(i) for i in input().split()]
	barr_l = [[int(i) for i in input().split()] for j in range(N)]
	bc = 0
	for bt,x in barr_l:
		if(bt==1):
			if(x<H-y1):
				L-=1
		else:
			if(y2<x):
				L-=1
		if L>0:
			bc+=1
		if L<=0:
			break
	print(bc) 
Editorialist's Solution
T=int(input())
for k in range(T):
    N, H, Y1, Y2, L = map(int,input().split())
    barriers = [(0,0)]*N
    for i in range(N):
        t,X = map(int,input().split())
        barriers[i]=(t,X)
    ans = 0
    for j in range(N):
        t = barriers[j][0]
        X = barriers[j][1] 
        if t==1:
            if H-Y1 > X:
                L = L - 1    
        else:
            if Y2 < X:
                L = L - 1
        if L==0:
            break
        ans = ans + 1

    print(ans)
 
1 Like

I have doubt in this problem,@sachin_yadav
Not able to figure out where i went wrong:
Here is the code:

#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long int
int t;
cin>>t;
while(t–)
{
vector<pair<int,int>>v;
int n,h,d,u,li,x,bar,cnt=0,b,xi,flag=1;
cin>>n>>h>>d>>u>>li;
for(int i=0;i<n;i++)
{
cin>>bar>>x;
v.push_back(make_pair(bar,x));
}
for(int i=0;i<n;i++)
{
flag=1;
b=v[i].first; xi=v[i].second;
if(b==2)
{
if(u>=xi){flag=0;cnt++;}
}
else if(b==1)
{
if(h<=xi || h-d<=xi){flag=0;cnt++;}
}
if(flag==1 && li!=1)
{
li–;
cnt++;
}
}
cout<<cnt<<endl;
}
return 0;
}

What is wrong with this code? Please someone review this.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--){
    	int n,h,y1,y2,f,cnt=0,i;
        cin>>n>>h>>y1>>y2>>f;
        for(int i=0;i<n;i++){
            int z,x;
            cin>>z>>x;
            if(z==1){
                if((h-y1)<=x)
                    cnt++;
                else{
                    f--;
                    if(f==0) break;
                    cnt++;
                }
            }
            else{
                if(y2>=x) 
                    cnt++;
                else{
                    f--;
                    if(f==0) break;
                    cnt++;
                }
            }
        }
        cout<<cnt;
    	cout<<'\n';
    }
    return 0;
}
1 Like

You need to scan all the input.
Here you skip by breaking loop so all barrier values might not be scan so, WA …

Try this… in conditions
It will scan all inputs for barrier and answer will not be affected …:grinning:

if((h-y1)<=x && f>0)

if((y2 >= x && f>0)

it still gives partially correct answer.

this is what I did: Link

What is wrong in this code.Which test case does it fail?

#include
using namespace std;

int main() {
// your code goes here
long long int t,n,h,y1,y2,l;
cin>>t;
while(t–){
cin>>n>>h>>y1>>y2>>l;
l–;
long long int arr[n],arr1[n],reduce,counter=0;
reduce=h-y1;
for(long long int i=0;i<n;i++){
cin>>arr[i]>>arr1[i];
}
for(long long int i=0;i<n;i++){
if(arr[i]==1){
//cout<<"–"<<endl;
if(reduce<=arr1[i]){
counter++;
}
else if(l!=0){
counter++;
l–;
}
}
if(arr[i]==2){
//cout<<"**"<<endl;
if(y2>=arr1[i]){
counter++;
}
else if(l!=0){
counter++;
l–;
}
}
}
// cout<<reduce<<endl;
cout<<counter<<endl;

}
return 0;

}

Give link to your solution instead. ( By submitting it on practice link if not submitted yet)

what is wrong in this solution @sachin_yadav

https://www.codechef.com/viewsolution/27674244

Bro. I think that is codechef bug.
I have solved 2 questions both of them are partially correct…

1 Like

ya! saw this just now after running setter’s solution. Thanks a lot!

1 Like

python solution:
time complexity: O(N)

t=int(input())
for _ in range(t):
n,h,y1,y2,l=map(int,input().split())
res=0
for i in range(n):
tp,x=map(int,input().split())
if(tp==1 and l>0):
if(h-y1<=x):
res=res+1
else:
res=res+1
l=l-1
if(l==0):
res=res-1
elif(tp==2 and l>0):
if(y2>=x):
res=res+1
else:
res=res+1
l=l-1
if(l==0):
res=res-1
print(res)

you have to break the loop as soon as the value of l becomes zero because you would be having no power to move forward
P.S. - If your power if l and you are using it then l becomes equal to zero and you would not be able to walk pass the barrier

Can you post GRUMPMA editorial soon please , thanks.

I have posted an UNOFFICIAL EDITORIAL for that, you may check it out if you wish to do so.

1 Like

What is Wrong With My Code

// Cooked By Divyanshu Pandey

import java.util.Scanner;
import java.io.IOException;

public class FullBarrierAlchemist{
public static void main(String[] args) throws IOException {
try{
Scanner scan = new Scanner(System.in);
//Defining Variables Names
int NoOfTestCases = scan.nextInt();
int[] NumberOfBarriers = new int[NoOfTestCases];
int[] HeightOfGuy = new int[NoOfTestCases];
int[] MaxDuckHeight = new int[NoOfTestCases];
int[] MaxJumpHeight = new int[NoOfTestCases];
int[] LifeForces = new int[NoOfTestCases];
int[][] BarrierType = new int[NoOfTestCases][1000];
int[][] HeightOfBarrier = new int[NoOfTestCases][1000];
int[] NoOfBarriersCrossed = new int[NoOfTestCases];
int[] FinalAnswer = new int[NoOfTestCases];
//Taking User Inputs
for(int i = 0 ; i < NoOfTestCases ; i++){
NumberOfBarriers[i] = scan.nextInt();
HeightOfGuy[i] = scan.nextInt();
MaxDuckHeight[i] = scan.nextInt();
MaxJumpHeight[i] = scan.nextInt();
LifeForces[i] = scan.nextInt();
for(int j = 0 ; j < NumberOfBarriers[i] ; j++){
BarrierType[i][j] = scan.nextInt();
HeightOfBarrier[i][j] = scan.nextInt();
}
}
//Calculating Results
for(int i = 0 ; i < NoOfTestCases ; i++){
NoOfBarriersCrossed[i] = 0;
for(int j = 0 ; j < NumberOfBarriers[i] ; j++){
if(BarrierType[i][j] == 1){
if(HeightOfGuy[i] - MaxDuckHeight[i] <= HeightOfBarrier[i][j] && LifeForces[i] > 0){
NoOfBarriersCrossed[i] = NoOfBarriersCrossed[i] + 1;
}
if(HeightOfGuy[i] - MaxDuckHeight[i] > HeightOfBarrier[i][j] && LifeForces[i] > 0){
NoOfBarriersCrossed[i] = NoOfBarriersCrossed[i] + 1;
LifeForces[i] = LifeForces[i] - 1;
}
}
if(BarrierType[i][j] == 2){
if(HeightOfGuy[i] + MaxJumpHeight[i] >= HeightOfBarrier[i][j] && LifeForces[i] > 0){
NoOfBarriersCrossed[i] = NoOfBarriersCrossed[i] + 1;
}
if(HeightOfGuy[i] + MaxJumpHeight[i] < HeightOfBarrier[i][j] && LifeForces[i] > 0){
NoOfBarriersCrossed[i] = NoOfBarriersCrossed[i] + 1;
LifeForces[i] = LifeForces[i] - 1;
}
}
}
}
// Printing Output
for(int i = 0 ; i < NoOfTestCases ; i++){
System.out.println(NoOfBarriersCrossed[i]);
}
}catch(Exception e){}
}
}

Please send a link to your code or format it.

https://www.codechef.com/viewsolution/27685169

What case does this fail?

thanks man!

Hey can someone check why wrong with my code?

https://www.codechef.com/viewsolution/27760826