TEAMFOR - Editorial

editorial
, , ,
1

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
2

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.

3

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
4

Great Question and Great editorial !! :smiley:

5

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;
}
6 
1
2
11
11

You print 0, the answer is 1.

7

I got it. Thanks

8

ohh yeah exactly. Thanks bro.

1 Like
10

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

else {
	ans += both;
}
11

Can somebody help me out figuring out what is wrong in my code :-

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t ;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        string s,t ;
        cin>>s>>t;
        int prog = 0  , eng =0, both =0,none=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{
                none ++;
            }
        }
        int team = 0 ;
        team += min(prog,eng);
        prog -= min(prog,eng);
        eng -= min(prog,eng);
        team += min(both,none);
        both -= min(both,none);
        none -= min(both,none);
        team += min(max(prog,eng),both);
        both -= min(max(prog,eng),both);
        team += both;
        cout<<team<<endl;
    }
}
12

Hey, after the execution of the line

prog -= min(prog, eng);

The value of prog is not the same as before as it has been updated.
Then, when the line "eng -= min(prog, eng);" is executed, the value of prog is the different. You have done same mistakes further in other lines too.
Its better to first make a variable and then assign a value to it that you want to reduce from other variables. This way, you may update the value of previous variables, but the value of the newly created variable will be same.

13 
#include <bits/stdc++.h>
using namespace std;
int main(){
    int q ;
    cin>>q;
    while(q--){
        int n ;
        cin>>n;
        string s,t ;
        cin>>s>>t;
        int team = 0;
        int both =0 , prog = 0 , eng = 0, none = 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{
                none ++;
            }
        }
        team += min(prog,eng);
        prog-= min(prog,eng); eng -=  min(prog,eng) ;
        team += min(both , (prog+eng+none));
        both -=  min(both , (prog+eng+none));
        team += both/2;
        cout<<team<<endl;

    }
}

can somebody please tell me , where is error in my code!!

14

In this, first prog gets updated, lets consider a case when end was smaller than prog, but now prog has become smaller, next when you reduce min(prog,eng) from eng, the value that is reduced is smaller than what it should have been. So its better to make a new variable, store the value in it, and then subtract the value from both variables.

15

ohhh;