BIT2B - Editorial

PROBLEM LINK:

Contest

Practice

Setter: Chiraag Mittal

Tester: Jatin Nagpal

Editorialist: Chiraag Mittal

DIFFICULTY:

Easy

PREREQUISITES:

2 pointers

PROBLEM:

For Each Test Case , we have been given N the number of boxes. The next line contains N numbers i.e. the number of candies in each box.
Third line contains an integer X i.e. the speed .
A eats candies in leftmost box with a speed X times faster than B. We need to find the number of boxes finished by A and B.

EXPLANATION:

We need to find for A as well as for B, the time they will start eating candies in each of the N boxes. If the time A will start eating candies in a box<=time B will start eating candies in that box ,then increase the count for A else increase the count for B.
A start eating candies from the left (index 0) with a speed X times faster than of B and B starts eating candies from the right (index n-1) .For each box, we need to find who will reach to that box faster as candies from a particular box can only be eaten by either of A and B. Whosoever reaches to a box faster will eat all the candies in that box.
Let at a given time,A has eaten P candies and B has eaten Q candies. 3 possible cases are as follows:
Case 1 : P < X * Q
In this case , A will eat all the candies from the next box form left.
Case 2 : P > X * Q
In this case , B will eat all the candies from the next box from right .
Case 3 : P = X * Q
In this case , as both A and B have reached to same box but candies in a box can eaten be only one of them, so we need to check who has eaten more number of boxes till now.

SOLUTION:

Setter
#include<iostream>
#include<bits/stdc++.h>
#define ll long long int
using namespace std;

int main()
{

int t;
cin>>t;
while(t--)
{
	int n,x;
	cin>>n;
	int i=0,j=n-1;
	int arr[n+1];
	for(int i=0;i<n;i++)
	cin>>arr[i];
            cin>>x;
	int count1=0,count2=0;
	ll sum1=0,sum2=0;
	while(i<j)
	{
	
		if(sum1>sum2)
		{
			sum2+=(x*arr[j]);
			count2++;
			j--;
		}
		else if(sum2>sum1)
		{
			sum1+=arr[i];
			i++;
			count1++;
		}
		else
		{
			
			sum2+=(x*arr[j]);
			count2++;	
			j--;
			sum1+=arr[i];
			i++;
			count1++;
		}
	}
	if(i==j && sum1<sum2)
	count1++;
	else if(i==j && sum1>sum2)
	count2++;
	else
	{ 
	    if(count1>=count2) count1++;
	    else count2++;
	}
	
	
	cout<<count1<<" "<<count2<<"\n";
}
return 0;

}

Tester
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define f1(i,a,b) for(i=a;i<b;i++)
#define f2(i,a,b) for(i=a;i>=b;i--)
int i,j;
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
    	int n;
    	cin>>n;
    	int a[n];
    	f1(i,0,n)
    	{
    		cin>>a[i];
    	}
    	int x;
        cin>>x;
    
    int left=0,right=n-1;
    int candy1=0,candy2=0;
    int box1=0,box2=0;
    while(left<=right)
    {
        if(candy1<x*candy2)
        {
            candy1+=a[left];
            box1++;
            left++;
        }

        else if(candy1>x*candy2)
        {
            candy2+=a[right];
            box2++;
            right--;
        }

        else
        {
            if(left!=right)
            {
                candy1+=a[left];
                left++;
                box1++;
            }
            else
            {
                if(box1<box2)
                {
                    candy2+=a[right];
                    box2++;
                    right--;
                }
                else
                {
                    candy1+=a[left];
                    left++;
                    box1++;
                }
            }
        }

    }
    cout<<box1<<" "<<box2<<endl;

}
return 0;

}

Feel free to share your approach, if you want to . Suggestions are welcomed as always had been. :slight_smile:

4 Likes

Can anyone please help me to figure out my fault?? Its give WA for which test case(s)??

import sys

def main():
  t = int(sys.stdin.readline())
  for _ in range(t):
    n = int(sys.stdin.readline())
    c = list(map(int, sys.stdin.readline().split()))
    x = int(sys.stdin.readline())
    if n == 1:
      print(1, 0)
      continue

    e1, e2 = c[0], c[n - 1]
    b1, b2 = 1, 1
    while b1 + b2 < n:
      if e1 < x * e2:
        e1 += c[b1]
        b1 += 1
      elif e1 > x * e2:
        b2 += 1
        e2 += c[n - b2]
      else: #e1 == x * e2:
        if b1 >= b2:
          e1 += c[b1]
          b1 += 1
        else: #b1 < b2:
          b2 += 1
          e2 += c[n - b2]

    print(b1, b2)

if __name__ == "__main__":
  main()

EDIT :
Solution link [WA]

[N.B.: Some portion of this code changed (but not logically) for clarification.]

UPD: Thanks to @coulson72 for find out the defect.

I have used array ta and tb to store the arrival time of A and B at a particular box… This passes only task 1 if sub-task 2… please point out the mistake

#include<bits/stdc++.h>
using namespace std;

int main(){
int t;cin>>t;while(t–){

    long n;cin>>n;float c[n];
    
    for(long i=0;i<n;i++){
        cin>>c[i];
    }
    
    float x;cin>>x;
    float ta[n];
    float tb[n];
    
    ta[0]=0;tb[n-1]=0;
    
    for(long i=1;i<n;i++){
        ta[i]=ta[i-1]+c[i-1]/x;
    }
    for(long i=n-2;i>=0;i--){
        tb[i]=tb[i+1]+c[i+1];
    }
    
    int a=0,b=0;
    for(long i=0;i<n;i++){
        if(ta[i]<=tb[i]){
            a++;
        }
        else{
            b++;
        }

    }

    cout<<a<<" "<<b<<'\n';
}

}

@chiraag3200 i request you to please explain the logic else no one can understand what your code is trying to do? please explain the logic brother

1 Like

Confusing macros wtf (i know ll is long long but editorial should be understood by everyone), why the hell you put them on the editorial ?? remove macros and post again with some explanation or comments

2 Likes

if n==1:
print(1, 0)
continue
elif n==2:
print(1, 1)
continue

Refer this (similar logic used) --> https://www.codechef.com/viewsolution/26688977

I think those are the test cases you’re missing for AC

My solution was only partially correct and I couldn’t figure out the reason behind it. Could anyone have a look at my solution, I have commented the code.
Here’s a link to my solution: https://www.codechef.com/viewsolution/26690132
Thanks in advance.

Prerequisites are "two pointers"at least. @chiraag3200

1 Like

#include<stdio.h>
#define ll long long
#define sd(n) scanf("%d",&n)

// its failing for last testcase can you help me out?

int main() {
int t,n,x,i,j;
sd(t);
while(t–)
{
sd(n);
int candy[n],visited[n];

   for(i=0;i<n;i++)
   {
        sd(candy[i]);
         visited[i]=0;
   }
    
    sd(x);
    i=0,j=n-1;
    
    int a=0,b=0,sum1=0,sum2=0;
   if(n==1)
   {
    printf("1 0\n");
    continue;
   }
    
    while(i<j)
    {
        
        if(!visited[i])
        {
            sum1+=candy[i];
            a++;
        }
        if(!visited[j])
        {
            sum2+=(x*candy[j]);
            b++;
        }
        
        visited[i]=visited[j]=1;
        
       
        if(sum1<sum2)
            i++;
            
        
        else if(sum1>sum2)
            j--;
            
        
            
        else
        {
            sum1=sum2=0;
            i++;
            j--;
            if(i==j)
            {
                    
                    if(a<b)
                        b++;
                    else
                        a++;
            }
        
        }
        
        
    }
  
        

    printf("%d %d\n",a,b);
    
    
}
return 0;

}

My code doesn’t pass last test case any suggestions or corner testcase
Scan s1 = new Scan();
StringBuilder sb = new StringBuilder();
int t = s1.scanInt();
while(t–!=0)
{
int n = s1.scanInt();
int ar[] = new int[n];
long sum =0;
for(int i=0;i<n;i++)
{
ar[i]=s1.scanInt();
sum+=ar[i];
}
int x = s1.scanInt();
int tempa=0;
int tempb=0;
int boxa=0;
int boxb=0;
int r=n-1;
int l=0;
while(l<=r)
{
if(tempa<xtempb)
{
boxa++;
tempa+=ar[l];
l++;
}
else if(tempa>x
tempb)
{
// r–;
boxb++;
tempb+=ar[r];
r–;
}
else
{
if(l!=r)
{
boxa++;
tempa+=ar[l];
l++;
}
else if(boxa<boxb)
{
boxb++;
tempb+=ar[r];
r–;
}
else
{
boxa++;
tempa+=ar[l];
l++;
}
}
}
sb.append(boxa+" “+boxb+”\n");
}
System.out.println(sb);

My code works well for both these test cases… Anyways Thanks… I think something’s wrong with my code calculating time of arrival…

my code is showing RE in test case 2 and 3. anyone please help me to figure out where is the error in code???
#include<bits/stdc++.h>
using namespace std;

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int t;
cin>>t;

while(t–){
int n;
cin>>n;

int c[n];
for(int i=0;i<n;i++)
  cin>>c[i];

int x;
cin>>x;

long long int suml,sumr;
suml=0;sumr=0;
int l=0;int r=n-1;
     
if(n==1)
  cout<<1<<" "<<0<<"\n";
else{
  if(n==2)
    cout<<1<<" "<<1<<"\n";
  else{
    suml=c[l];sumr=c[r];
    while(l!=(r-1)){

      if(suml<(x*sumr)){
        l++;
        suml+=c[l];
      }

      if((x*sumr)<suml){
        r--;
        sumr+=c[r];
      }

      if(((x*sumr)==suml)&&(l>=(n-r-1))){
        l++;
        suml+=c[l];
      }

      if(((x*sumr)==suml)&&(l<(n-r-1))){
        r--;
        sumr+=c[r];
      }


    }
    cout<<l+1<<" "<<n-l-1<<"\n";
  }
}

}
return 0;
}