Need help with CSES Problem Set: Ferris Wheel

Link to problem

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.

1 Like

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: https://github.com/Phoenix009/CSES-Solutions

@hblord787 @phoenix_307. Thanks for the explanations I understood the solution now.

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;
}