I understand that this problem uses the two pointers technique, but I don’t understand why the while loop in the solution has i <= j instead of i < j.
Solution:
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, w;
cin >> n >> w;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
sort(a.begin(), a.end());
int i = 0;
int j = n - 1;
int c = 0;
while (i <= j) {
if (a[j] + a[i] > w) j--;
else { i++; j--; }
c++;
}
cout << c << endl;
}
Just to avoid the odd element case.
i.e. if you put i<=j condition then it will work fine with all those cases which have odd n.
3 2 1 1 1
It will give output 2 and clearly 2 is the correct answer.
But if you take i<j then it will check the value at index 0,2, after this iteration i will be 1 and j will be 1 and condition i<j will fail, so your answer will be 1 which is wrong.
Edit: Platform like codeforces, leetcode, CSES will provide you testcase on which your submission is failing. So to figure out this type of query what else you could have done is, submitted you solution without this condition and checked those cases on which you get a WA and tried to figure out yourself why this condition matters.
Can someone please explain me why this solution works
in the while loop variable c is incrementing always whether the if condition or else condition gets passed .
Why not c variable contains the length of array as it is traversing the whole array irrespective of it is in the range w or not
still it is correct .
Thanks for reading
c denotes the count of gondolas.
In the loop we are finding the minimum gondolas required to contain all elements.
If you read the question a gondola cannot have more than 2 elements, which means minimum gondolas are always
n/2 if n is even
n/2 + 1 if n is odd
which means it doesn’t matter if the condition satisfies or not, our two pointer loop will always produce the minimum gondolas required.
You are missing out on the case when there is a possibility to allow a single child in a gondola. If you cannot add two children (their total weight exceeds the limit) then , you should check if the child with the greater weight can go alone in the gandola. if yes then ct ++, j++;
You can refer the solution here: GitHub - Phoenix009/CSES-Solutions
It is given in the question that px<= x so, child with the greater weight will always go in the condola.
Also, I got an AC when I did not include:
if i == j and p[i] <x: ans += 1
Lol
Why not try this binary search with greedy two pointer approach.
I am pasting just the solve function and the check function for binary search.
bool check(int *A,int n,int noc,int limit)
{
int count=0;
int fp=0;
int sp=n-1;
while (fp<=sp)
{
if (A[sp]+A[fp]<=limit)
{
count++;
fp++;
sp--;
}
else
{
sp--;
count++;
}
}
if (count<=noc)
return true;
return false;
}
void solve()
{
int n,limit;
cin>>n>>limit;
int *A=new int[n];
for(int i=0;i<n;i++)
{
cin>>A[i];
}
sort(A,A+n);
int l=1;
int r=1e9;
// show(A,n);
int ans=INT_MAX;
while (l<=r)
{
int mid=(l+r)/2;
// trace1(mid);
if (check(A,n,mid,limit))
{
ans=min(mid,ans);
r=mid-1;
}
else
{
l=mid+1;
}
}
cout<<ans;
}
@hblord787 can you please tell me if the capacity of 1 gondola is increased from 2 to 4 then how this problem is solved ?
Watch the code very carefully. This is two pointer method. So, c won’t be be the whole array because we are not traversing the whole array. Every time we are checking two elements but c is incrementing 1.
For example:
if(a[i] + a[j] <= x) then we took two children already so you can’t take any children anymore.
So, we are incrementing i by one and j by one. But if (a[i] + a[j] > x) here you have to think little. Because if(a[i] + a[j] > x) then for a[j] you won’t find any smaller value for which a[i] + a[j] <=x will be true because at present a[i] is the smallest. We worked previous a[i] so we can’t take them anymore. Next point is for a[j] I won’t find any a[i] right but for a[i] there is a chance that I can find any a[j] ( smaller than present a[j] ) for which a[i] + a[j] <= x will be true. That’s why we are incrementing c by one again and decrementing j not i.
Hope you got it.