AIRLINE - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: Daanish Mahajan
Tester: Istvan Nagy
Editorialist: Aman Dwivedi

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Chef has 3 bags that she wants to take on a flight. They weigh A, B, and C kgs respectively. She wants to check in exactly two of these bags and carry the remaining one bag with her.

The airline restrictions say that the total sum of the weights of the bags that are checked-in cannot exceed D kgs and the weight of the bag which is carried cannot exceed E kgs. Find if Chef can take all the three bags on the flight.

EXPLANATION:

Just do as the problem say and check all the possible combinations. If any of the combinations satisfy the airline rules, we can simply print YES otherwise NO.

The possible combinations that can be are as follows:

  • Bag A and Bag B are checked in while Bag C is carried.
  • Bag B and Bag C are checked in while Bag A is carried.
  • Bag A and Bag C are checked in while Bag B is carried.

If any of the combinations satisfy the airline rules then Chef can take all the three bags and hence print YES else NO.

TIME COMPLEXITY:

O(1) per test case.

SOLUTIONS:

Author 
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define rb pop_back
#define ti tuple<int, int, int>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define mp make_pair
#define mt make_tuple

using namespace std;

const int maxt = 36000;
const string newln = "\n", space = " ";

int main()
{   
    int t, a, b, c, d, e; cin >> t;
    while(t--){
        cin >> a >> b >> c >> d >> e;
        string ans = "No";
        if((a + b <= d && c <= e) || (a + c <= d && b <= e) || (b + c <= d && a <= e)){
            ans = "YeS";
        }
        cout << ans << endl;
    }
}
Tester 
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>

#ifdef HOME
#include <windows.h>
#endif

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T& a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T& a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

long long readInt(long long l, long long r, char endd) {
	long long x = 0;
	int cnt = 0;
	int fi = -1;
	bool is_neg = false;
	while (true) {
		char g = getchar();
		if (g == '-') {
			assert(fi == -1);
			is_neg = true;
			continue;
		}
		if ('0' <= g && g <= '9') {
			x *= 10;
			x += g - '0';
			if (cnt == 0) {
				fi = g - '0';
			}
			cnt++;
			assert(fi != 0 || cnt == 1);
			assert(fi != 0 || is_neg == false);

			assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
		}
		else if (g == endd) {
			assert(cnt > 0);
			if (is_neg) {
				x = -x;
			}
			assert(l <= x && x <= r);
			return x;
		}
		else {
			assert(false);
		}
	}
}

string readString(int l, int r, char endd) {
	string ret = "";
	int cnt = 0;
	while (true) {
		char g = getchar();
		assert(g != -1);
		if (g == endd) {
			break;
		}
		cnt++;
		ret += g;
	}
	assert(l <= cnt && cnt <= r);
	return ret;
}
long long readIntSp(long long l, long long r) {
	return readInt(l, r, ' ');
}
long long readIntLn(long long l, long long r) {
	return readInt(l, r, '\n');
}
string readStringLn(int l, int r) {
	return readString(l, r, '\n');
}
string readStringSp(int l, int r) {
	return readString(l, r, ' ');
}

int main(int argc, char** argv)
{
#ifdef HOME
	if (IsDebuggerPresent())
	{
		freopen("../in.txt", "rb", stdin);
		freopen("../out.txt", "wb", stdout);
	}
#endif
	int T = readIntLn(1, 36'000);
	int sumN = 0;
	forn(tc, T)
	{
		int A = readIntSp(1, 10);
		int B = readIntSp(1, 10);
		int C = readIntSp(1, 10);
		int D = readIntSp(15, 20);
		int E = readIntLn(5, 10);
		if ((A + B <= D && C <= E) ||
			(A + C <= D && B <= E) ||
			(B + C <= D && A <= E))
			printf("YES\n");
		else
			printf("NO\n");
	}
	assert(getchar() == -1);
	return 0;
}
Editorialist 
#include<bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
	int a,b,c,d,e;
	cin>>a>>b>>c>>d>>e;

	if(((a+b)<=d && c<=e) || ((a+c)<=d && b<=e) || ((c+b)<=d && a<=e))
		cout<<"YES"<<endl;
	else
		cout<<"NO"<<endl;
}

int32_t main()
{
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);

	int t;
	cin>>t;

	while(t--)
		solve();

return 0;
}
2

I tried the greedy approach. i.e I first find out the heaviest bag that can be carried(<=E), and then checked that sum of the left bags is less than D or not.
But the answer was not been accepted. Can anyone help me to find the corner case i.e where my answer will fail.
https://www.codechef.com/viewsolution/51008830
Thanks!!

3

I too implemented a simple straightforward solution which not accepted CodeChef: Practical coding for everyone

There was an ambiguity in the problem statement. Suppose all 3 bags weigh 6 Kgs, while the limits are D = 20 and E = 5. Chef can take all 3 bags on the flight, but will have to check all of them in, not what she ‘wants’. It was not obvious to me whether this case should be allowed.

4

Screenshot from 2021-09-14 08-45-40

5

@david_s , the answer for your example should be NO, as she is not able to carry any bag. But my question is "is there anything wrong in the greedy approach that I have taken? ".
@cherry0697 please guide me through it.

6

Here is the error

 if(arr[i]<=e)
	     {
	         sum-=arr[i];
	         sum-=arr[i];
	         break;
	         
	     }

Its the double subtraction that is causing the error

1 Like
7

Thanks, @themankrit it was my bad. I got it. :sweat_smile:

8

You say that you find the heaviest bag which can be carried, but you actually find the lightest bag. Suppose that the bags weight 5, 6, 7 Kg, with D = 12 and E = 6. She should carry the 6 Kg bag and check in the other two, not what you expect to do on an airplane. I made the same mistake.

9

why am i getting WA can anyone say pls

#include
using namespace std;

void solve(){
int a,b,c,d,e; cin>>a>>b>>c>>d>>e;

if((a+b<=d && c<=e )|| (c+b<=d && a<=e ) || (a+c<=d && b<=e))cout<<“YES\n”;
else cout<<“N0\n”;
}
int main(){
int tc; cin>>tc;
while(tc–>0)solve();
return 0;
}

1 Like