TEAMFOR - Editorial

PROBLEM LINK:

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

Author: Soumyadeep Pal
Tester: Shubham Anand Jain
Editorialist: Nishank Suresh

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

There are N people, each of whom may know/not know programming and may/may not know the English language. Form the maximum number of teams of 2 people such that each person is in at most one team, and each team has at least one person who knows programming and one person who knows English.

QUICK EXPLANATION:

  • Pair people who only know English with those who only know programming.
  • Then, pair people who know both English and programming with any of the remaining people.
  • Finally, pair people who know both, if any of them remain.

EXPLANATION:

Each person can be represented by a binary string of length 2:

  • 00 for a person who knows neither programming nor English
  • 01 for someone who knows only English but not programming
  • 10 for someone who knows only programming but not English
  • 11 for someone who knows both.

Note that a 11 can be freely paired with anyone else. Other than that, the only possible pair is a 01 with a 10.

This restriction leads us to think of a greedy solution:

  1. Pair off as many 10 and 01 as possible.
  2. The remaining 10 / 01/ 00 people can only be paired with a 11 person, so do as much of that as possible.
  3. Finally, pair off any remaining 11 people.

It turns out that this simple, intuitive greedy algorithm is optimal.

Formal Proof

As is common in the proof of several greedy strategies, we use an exchange argument.

Claim: There exists a maximal pairing where as many 01 are matched with 10 as possible.

Proof

Consider any maximal (by size) set of pairs P. Suppose P contains pairs (10, 11) and (01, 11). Swapping partners to obtain the pairs (10, 01) and (11, 11) still leaves us with a set of pairs of the same size, but with more pairs of the form (10, 01). Continue this process till it can no longer be done.

Now, note that among the unpaired people, there cannot be both a 10 and a 01 - because otherwise we could pair them and improve the answer, contradicting the maximality of P.
Hence, either every 01 is in P, or every 10 is in P. The exchange argument shows us that the number of (10, 01) pairs is also maximal, as required.

Claim: In a maximal pairing where the number of (10, 01) pairs is also maximum, it is never worse to pair a 11 with 00/10/01 than to pair it with another 11.

Proof

Again, let P be the maximal pairing we are considering. Let S be the set of unpaired people.
If S were empty, then everyone is paired and we clearly can’t do better.
Suppose P contains a (11, 11) pair, and S contains a non-11 person (say of type x)
Then, we can again exchange partners to get a (11, x) pair in P and move the other 11 outside. The size of P remains the same, so our answer is not any worse, but we have reduced the number of (11, 11) pairs.

This proves that the greedy algorithm described above is optimal.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase,

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;

void solve(int tc) {
	int n; cin >> n;
	string s, t; cin >> s >> t;
	int both = 0, eng = 0, prog = 0, rem = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == '1' && t[i] == '1') {
			both++;
		} else if (s[i] == '1') {
			prog++;
		} else if (t[i] == '1') {
			eng++;
		} else {
			rem++;
		}
	}
	int ans = min(prog, eng);
	rem += (max(prog, eng) - min(prog, eng));
	if (both >= rem) {
		ans += (both + rem) / 2;
	} else {
		ans += both;
	}
	cout << ans << '\n';
}

signed main() {
	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t = 1;
	cin >> t;
	for (int i = 1; i <= t; i++) solve(i);
	return 0;
}
Tester's Solution
//By TheOneYouWant
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)

int main(){
	fastio;

	int tests;
	cin >> tests;

	while(tests--){
		int n;
		string s, t;
		cin >> n >> s >> t;

		for(int i = 0; i < n; i++){
			if(s[i]!='0' && s[i]!='1'){
				assert(1==0);
			}
			if(t[i]!='0' && t[i]!='1'){
				assert(1==0);
			}
		}

		int both = 0, eng = 0, prog = 0, oth = 0;

		for(int i = 0; i < n; i++){
			if(s[i]=='1'){
				if(t[i]=='1'){
					both++;
				}
				else{
					eng++;
				}
				continue;
			}
			if(t[i]=='1') prog++;
			else oth++;
		}

		int ans = 0, left = 0;
		ans += min(eng, prog);
		left += eng + prog - 2 * ans;
		left += oth;
		int pairs = min(left, both);
		left -= pairs;
		both -= pairs;
		ans += pairs;
		ans += both / 2;

		cout << ans << endl;
	}

	return 0;
}
Editorialist's Solution
import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    s = input()
    t = input()
    prog, eng, both, neither = 0, 0, 0, 0
    for i in range(n):
        if s[i] == '1' and t[i] == '1':
            both += 1
        elif s[i] == '1':
            prog += 1
        elif t[i] == '1':
            eng += 1
        else:
            neither += 1
    assert(both + prog + eng + neither == n)
    ans = min(prog, eng)
    eng -= ans
    prog -= ans
    x = min(both, prog + eng + neither)
    ans += x
    both -= x
    ans += both//2
    print(ans)
1 Like

why we’re finding the average value here instead of just putting the smaller value.
Ex: rem = 5, both = 15 then we should have 5 teams only instead of (5+15)/2 = 10 teams.

But when both >= rem, you can pair the both guys too with each other,
In your ex: rem = 5, both = 15, we have 5rem + 5 both guy = 5 team, now 10 both guys remain so they can be clubbed together to form 5 more teams, hence 10 teams are there.

1 Like

Great Question and Great editorial !! :smiley:

Hey Can anyone help me, I’m getting wrong answer

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 
    int t;
    cin >> t;
    while (t--) { 
        int n,p=0,e=0,b=0,ns=0;
        int ans=0;
        string s,t;
        cin>>n;
        cin>>s;
        cin>>t;
        for(int i=0;i<n;i++){
            if(s[i]=='1'&&t[i]=='1'){
                ++b;
            }
            else if(s[i]=='1' && t[i]=='0'){
                ++p;
            }
            else if(s[i]=='0'&& t[i]=='1'){
                ++e;
            }
            else{
                ++ns;
            }
        }
        int mn = min(p,e);
        int mx = max(p,e);

        int both = min(b,ns+(mx-mn));
        ans = mn+both;
        cout<<ans<<"\n";
    }
    return 0;
}
1
2
11
11

You print 0, the answer is 1.

I got it. Thanks

ohh yeah exactly. Thanks bro.

1 Like

you can also use
if (both >= rem) {
ans += rem;
both = both - rem;
if (both >= 2)
{
ans += (both / 2);
}
}

else {
	ans += both;
}