TWOMERCHANTS - Editorial

PROBLEM LINK:

Contest - Division 4
Contest - Division 3
Contest - Division 2
Contest - Division 1

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Greedy

PROBLEM:

You are given two arrays A and B with distinct elements, and an integer C. You may perform the following operations - select an element in either array that is \le C and remove it. Then, increase the values of all elements in that array by 1, and decrease the values of all elements in the other array by 1.

Determine if it’s possible to empty both arrays.

EXPLANATION:

Firstly, observe that if a merchant has x items priced \le C, all x items can be purchased by buying from the greatest to smallest priced item.

How?

Let c_1<c_2<\dots<c_x\le C be the costs of the items.
Now, we can buy items from c_x to c_1, and it is easy to see that the cost of the items (increasing by 1 after each move) never exceeds C.

Without loss of generality, let’s say a valid solution [a_1,b_1,a_2,b_2,\dots] exists, where we buy a_1 items from A, followed by b_1 items from B, followed by a_2 items from A and so on (the case where we buy first from B can be handled similarly).

Claim: It is possible to simplify the above solution to [p,q,r], that is, we buy p items from A, followed by all q\ (q=M) items from B and finally the remaining r\ (r=N-p) items from A.

Proof

We show that any sequence of the form [a_1,b_1,a_2,b_2] can be done in \le 3 moves. This can then be applied recursively to any valid solution, to reduce it to a 3 move one.

Case 1: a_1\ge b_1
Here, it is easy to see that [a_1+a2,b_1+b_2] is a valid sequence of moves, that buys the same number of items from both merchants.

Why?

Since a_1\ge b_1, the price of all items in A after move 2 is more than the initial price. Thus, its trivial to deduce that the a_2 items purchased in move 3 could have be bought in move 1 itself, proving the validity of our simplified sequence.

Case 2: a_1<b_1
A bit of casework shows that [0,b_1-a_1,a_1+a_2,(b1-a_1)+b_2]\implies [b_1-a_1,a_1+a_2,(b1-a_1)+b_2] is an equivalent sequence of 3 moves, where we start by buying from B instead.

Why?

Since a_1<b_1, it is clear that there are atleast b_1-a_1 items in B originally, with cost \le C.
The cost of the items in A at the end of the first move (in our simplified sequence) decreases by b_1-a_1, which is the same amount it decreases by at the end of the second move in the original sequence.
Thus, it is possible to buy a_1+a_2 items from A in move 2, proving the validity of our new sequence.

With this claim, the solution is straightforward - A valid solution exists only if we can buy \max(0, B_M-C) elements from A (which is the minimum number of buys we need to be able to buy everything from B at once), and after buying everything from B, we can buy all remaining items in A (for this, the price of all items in A should be \le C).

Here’s an equivalent mathematical expression of the above.
Let p equal the number of items in A with price \le C. Also, let q=\max(0,B_M-C) Then, a valid solution exists iff:

(q\le p) \text{ and }( A_N+q-M\le C) \text{ holds.}

Don’t forget to check similarly for the case where we first buy from B!

TIME COMPLEXITY:

Since we iterate over the arrays exactly once, the time complexity is

O(N+M)

per test case.

SOLUTIONS:

Editorialist’s solution can be found here.

Author's solution
// WA

#include <bits/stdc++.h>
#define int long long
using pii=std::pair<int,int>;
using namespace std;

int t, n, m, h;

int solve(vector<int> a, vector<int> b)
{
    int need_rem_b = max(a.back() - h, 0ll);
    return (need_rem_b < b.size() && (need_rem_b == 0 || b[need_rem_b - 1] <= h) && b.back() + need_rem_b - ((int)a.size()) <= h);
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    for(int cases = 0; cases < t; cases++)
    {
        cin >> n >> m >> h;
        vector<int> a(n), b(m);
        for(int i = 0; i < n; i++)
            cin >> a[i];
        for(int i = 0; i < m; i++)
            cin >> b[i];
        if(solve(a, b) || solve(b, a))
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    return 0;
}
Tester's solution
// Super Idol的笑容
//    都没你的甜
//  八月正午的阳光
//    都没你耀眼
//  热爱105°C的你
// 滴滴清纯的蒸馏水

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,m,k;
int arr[500005];
int brr[500005];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int TC;
	cin>>TC;
	while (TC--){
		cin>>n>>m>>k;
		rep(x,0,n) cin>>arr[x];
		rep(x,0,m) cin>>brr[x];
		
		rep(zzz,0,2){
			if (arr[n-1]<=k && brr[m-1]-n<=k){
				cout<<"YES"<<endl;
				goto done;
			}
			
			int diff=brr[m-1]-k-1;
			if (0<=diff && diff<n && arr[diff]<=k && arr[n-1]-m+diff+1<=k){
				cout<<"YES"<<endl;
				goto done;
			}
			
			swap(n,m);
			rep(x,0,max(n,m)) swap(arr[x],brr[x]); //raised_eyebrows
		}
		
		cout<<"NO"<<endl;
		done:;
	}
	
}
2 Likes

I tried to apply a brute force approach to this.
I stored the items of merchant1 and merchant2 in 2 different sets and instead of decreasing or increasing the prices of the items , I am temporarily changing the values of C.

Can anyone help me figure out what’s wrong in the approach or in the code.
It just passes 2 test cases!

link to code

@infinitepro I think link to code is not working.

Fixed.

@infinitepro Please add proof!

1 Like