Tug of War Editorial.
PROBLEM LINK:
Author: Aman Singhal
Tester: Abhishek Jugdar, Reyaan Jagnani
Editorialist: Reyaan Jagnani
DIFFICULTY:
EASY
PREREQUISITES
Arrays, Binary Search, Two Pointers
PROBLEM:
Two teams A and B have to face off in a tug of war match in which each round will be played by one of their players. The one who wins must stay for the next round and the other gets eliminated. In case of a draw both the players will get eliminated.
The team whose player is eliminated will send another person from their team.
Players with higher strength always win and players with equal strength will draw.
A team will win a match when all players get eliminated in the opponent team and at least 1 player is left in their team. If both teams are left with no player it will result in a draw.
We know that team A has N players and will send them as they appear basically if i < j, player i will go before player j and also the strength of their i_th player is A_i. We also know team B has M players with i_{th} player having B_i strength. Now we want to find if team B can win a match or not, and if they can, what is the ordering of their team players that will let them win. In case multiple orderings are possible they will decide the lexicographically smallest ordering.
QUICK EXPLANATION
We will compare the value of array A and array B, where array B has to be in decreasing order in order to get lexicographically smallest ordering.
We will sort the array B in decreasing order and then will do the following comparison until at least one of the arrays becomes empty. let u and v be the current element from A and B respectively.
i) If u is greater than v, then it is not possible for B to win.
ii) If u is smaller than v, then we will change u as the next element of A.
iii) If u is equal to v, then we will change both u and v with the next element of A and B respectively.
In the end if A does not win and array B has some non-zero element left then it can win and the lexicographically smallest queue will be the remaining players in B in increasing order and B up to next element in decreasing.
EXPLANATION:
There are few observations which are needed to get the idea of this problem. Let us build the idea of the problem step by step.
Observation 1
If we do not have to output the lexicographically smallest sequence of B, then what sequence always ensures the answer?
It will be B in decreasing order. It is because a player with the highest strength will always result in win or draw, if it is not possible to draw for him then B cannot win. Once he draws with the player of equal strength, the next strength player will play.
Observation 2
How to come up with the smallest lexicographically sequence?
Now we know that is it possible for team B to win or not and if it is possible, we have a sequence which can result in a win. To find out lexicographically smallest sequence, we have to bring players with lower strength ahead. It is because of the definition of lexicographically smallest sequence. So we will check till what players B can win with A and will keep the rest in increasing order in front of current B.
Conclusion- We have to find the players of B which are needed to win the game. After we find them, we can just print the remaining players in increasing order and the required players in decreasing order.
We can implement the above idea using following approaches:
Two pointer
We can implement this by having two pointers, one for array A and other for array B. We will sort the array B in decreasing order, and will make two pointers (say i pointing on A_1, and j pointing on B_1). Now, we will form 3 cases here,
If A_i == B_j, we will increment both i and j.
If A_i > B_j, we will return false, and print “NO”.
If A_i < B_j, we will increment i.
After running till the end, If j is equal to m, which means no player is left in Team B, we will print “NO”. Else, we will print the remaining elements of Team B in increasing order, followed by the eliminated players in decreasing order.
Time Complexity - ((m*logm)+n)
Binary Search Approach
From the observation we can say that if our B is sorted in decreasing order than our queue will look like this -
B_1, B_2, B_3…. B_i, B_m, B_{\text{m-1}}, B_{\text{m-2}} ... B_{\text{i+1}}.
Here, we can apply binary search on the position of i, then check if Team B is winning or not. If it is winning, we will Increase the value of i, else we will decrease the value of i.
Time Complexity - ((n+m)*(logm))
Constructive Approach
In case Team B wins, to make the arrangement lexicographically smallest, we will firstly print those player’s strength who haven’t been eliminated yet.
As we are fighting in decreasing order, the players left have less strength than all the players which were eliminated. So we will sort their strength in increasing order to get the lexicographically smallest arrangement.
Then we will print the strength of the eliminated players in the order of their elimination. (As explained in Observation 2).
Time Complexity - ((m*logm) + n)
Bonus: Proof why our approach gives the lexicographically smallest ordering.
Proof
Let B_win be the lexicographically largest subset of minimum size from B which will result in B to win and B_left be the remaining values of B in increasing order.
Observations
i) B_win will always be in non-increasing order, It is because if B_{\text{i+1}} > B_i then it can always defeat the player that B_i is defeating or have the same strength as B_i, and can be removed from the subset. Last player in B_win will either win or will be the only unplayed player in B_win.
ii) Last element of B_left will always be smaller than the last element of B_win because then it can also defeat the player and B_win cannot be the lexicographically largest subset.
iii) Answer of our problem will always be B_left + B_win. It is because if B_left is lexicographically smallest among all possible combinations then B_left + B_win will be lexicographically smallest. Proof that B_left is lexicographically smallest is :
Let’s say B_left = L_1,L_2,L_3…L_n and B_win = W_1,W_2,… W_m, then if there exists some other lexicographically smallest sequence B_leftmin = M_1,M_2,M_3…M_k which results in B_left to be minimum then, Say for first L_i > M_i then this is only possible if M_i is not present in L and M_i is present in B. Since all values smaller than L_i will be present in L, it will contradict.
SOLUTIONS:
Setter's Solution (Two Pointer Solution) (Python)
T=int(input())
for _ in range(T):
N,M=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
B.sort(reverse=True)
flag,i,j=0,0,0
while(i<N and j<M):
if (A[i]>B[j]):
flag=1
break
elif (A[i]<B[j]):
i=i+1
else:
i=i+1
j=j+1
if(flag==1 or j==M):
print("NO")
else:
ans=B[(j+1):][::-1]+B[:(j+1)]
print("YES")
print(*ans)
Tester's Solution - Binary Search Solution (C++) (abhi2402)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
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];
}
sort(b.begin(), b.end());
auto check = [&] (int mid) -> bool {
vector<int> c = b;
reverse(c.begin() + mid, c.end());
for (int i = 0, j = 0; i < n && j < m; ) {
if (a[i] > c[j]) j++;
else if (a[i] < c[j]) i++;
else {
i++;
j++;
}
if (j == m) return false;
}
return true;
};
int lo = -1, hi = m;
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
check(mid) ? lo = mid : hi = mid;
}
if (lo == -1) {
cout << "NO\n";
continue;
}
reverse(b.begin() + lo, b.end());
cout << "YES\n";
for (int x : b) {
cout << x << ' ';
}
cout << '\n';
}
}
Editorialist's Solution (C++) (Constructive Solution)
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
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];
}
sort(b.begin(), b.end());
vector<int> ans;
bool check = 0;
bool flag = 1;
vector<int> final;
int curr = -1;
for(int i=n-1; i>=0; i--)
{
if(a[i]>=curr)
{
curr = a[i];
final.push_back(curr);
}
}
reverse(final.begin(), final.end());
for(int i=0; i<final.size() && b.size()>0; i++)
{
if(final[i]>b.back())
{
flag = 0;
break;
}
if(final[i]==b.back())
{
ans.push_back(b.back());
b.pop_back();
}
else
{
check = 1;
ans.push_back(b.back());
b.pop_back();
break;
}
}
if(flag==0)
{
cout<<"NO"<<endl;
continue;
}
if(check==0)
{
if(b.size()==0) cout<<"NO"<<endl;
else
{
ans.push_back(b.back());
b.pop_back();
cout<<"YES"<<endl;
for(int i=0; i<b.size(); i++)
{
cout<<b[i]<<" ";
}
for(int i=0; i<ans.size(); i++)
{
cout<<ans[i]<<" ";
}
cout<<endl;
}
}
else
{
cout<<"YES"<<endl;
for(int i=0; i<b.size(); i++)
{
cout<<b[i]<<" ";
}
for(int i=0; i<ans.size(); i++)
{
cout<<ans[i]<<" ";
}
cout<<endl;
}
}
}
