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:
- Pair off as many 10 and 01 as possible.
- The remaining 10 / 01/ 00 people can only be paired with a 11 person, so do as much of that as possible.
- 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)