PROBLEM LINK:
Setter: Rashed Mehdi
Tester: Manik Goenka
Editorialist: Saranya Naha Roy
DIFFICULTY:
EASY
PREREQUISITES:
none
PROBLEM:
There are N different colors of socks and gloves. A left sock and a right sock make a pair of socks. A left glove and a right glove make a pair of gloves. i_{th} element of array A denotes there are A_i number of pair of socks of color i. i_{th} element of array B denotes there are B_i number of pair of gloves of color i. Now we have to choose K socks and L gloves such that we have a left sock, a right sock, a left glove and a right glove all of the same color and (K+L) is minimum.
Also A_1 = A_2 = ... = A_n and B_1 = B_2 = ... = B_n
QUICK EXPLANATION:
minimum\ value\ of\ K+L = (A+B)*(N-1)+2+min(A,B)*N+max(A,B)
EXPLANATION:
Let’s assume A_1=A_2=...=A_n=A and B_1=B_2=...=B_n=B
At first we need to find the minimum number of socks we need to choose such that there are at least P pairs of socks of different colors. Suppose we choose K socks. Now, if K<=N*A, it is possible all the socks are left socks. If K=N*A+1, there is at least 1 right sock. In this case we can say there is at least one pair of socks. If k=N*A+1+1, there are at least two pairs of socks. But these two pairs of socks can be of same color. If K=N*A + A, there are at least A pair socks and these A pairs of socks can be of same color. But if K=N*A + A + 1, there are at least (A+1) pairs of socks and these (A+1) pairs of socks can not be of same color as we know there are A pairs of socks of a particular color. So if K=N*A+A+1, we can say there are at least two pairs of socks of different colors. Similarly, if K=N*A+2*A+1 there are at least 2*A+1 pairs of socks. Now if A pairs of socks are of color x and A pairs of socks are of color y then 2*A pairs of socks are of colors x and y. So 2*A+1 pairs of socks must have socks of at least 3 different colors. There are at least 3 pairs of socks of different colors. Hence if K=N*A+(P-1)*A+1, there are at least P pairs of socks of different colors.
Similarly, we need to find the minimum number of gloves we need to choose such that there are at least Q pairs of socks of different colors.
L=N*B+(Q-1)*B+1
K+L=(N*A+(P-1)*A+1) + (N*B+(Q-1)*B+1)
=>K+L=N*A+P*A-A+1+N*B+Q*B-B+1
=>K+L=(A+B)*(N-1)+2+P*A+Q*B
In this case there are pairs of socks of at least P different colors and pairs of gloves of
at least Q different colors. If P+Q<=N then it is possible there is no common color between pairs of socks and pairs of gloves. But if P+Q=N+1 there is at least one common color between pairs of socks and pairs of gloves. so minimum value of P+Q is N+1.
Now we need to minimize P*A+Q*B
P*A + Q*B
if\ B>A
=P*A + Q*A + Q*B - Q*A
=A*(P+Q) +Q*B - Q*A
=A*(P+Q) + Q*(B-A)
=A*N+A+B-A\ [minimum\ Q=1\ and\ minimum\ P+Q=N+1 ]
=A*N+B
if\ A>B
=P*B + Q*B + P*A - P*B
=B*(P+Q) +P*A - P*B
=B*(P+Q) + P*(A-B)
=B*N+B+A-B\ [minimum\ Q=1\ and\ minimum\ P+Q=N+1 ]
=B*N+A
Hence\ minimum\ value\ of\ K+L = (A+B)*(N-1)+2+min(A,B)*N+max(A,B)
Time Complexity: O(n)
SOLUTIONS:
Setter's Solution
Language: C++17 (gcc 9.1)
//Setter's solution
//author: rash007
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
int tt;
cin>>tt;
while(tt--){
ll n, i, a=0, b=0;
cin>>n;
ll arr[n], brr[n];
for(i=0;i<n;i++){
cin>>arr[i];
a+=arr[i];
}
for(i=0;i<n;i++){
cin>>brr[i];
b+=brr[i];
}
ll mna = arr[0];
ll mnb = brr[0];
cout<<min((2*a) - mna+b+2, (2*b) - mnb+a+2)<<'\n';
}
}
Tester's Solution
Language: C++17 (gcc 9.1)
#include <bits/stdc++.h>
#define int long long int
#define mod 1000000007
#define f(i,a,b) for(int i=a;i<b;i++)
#define rf(i,a,b) for(int i=a;i>=b;i--)
#define rep(i,n) f(i,0,n)
#define rrep(i,n) rf(i,n-1,0)
#define w(t) int t; cin>>t; while(t--)
#define vi vector<int>
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define mii map<int,int>
#define mci map<char,int>
#define inf (int)(1e18)
using namespace std;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int bin_expo(int x, int n, int m)
{
x %= m;
int res = 1;
while (n)
{
if (n & 1)
res = res * x % m;
x = x * x % m;
n >>= 1;
}
return res;
}
void coder99()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
int32_t main()
{
coder99();
w(t)
{
int n;
cin >> n;
int a[n], b[n], suma = 0, sumb = 0;
rep(i, n)
{
cin >> a[i];
suma += a[i];
}
rep(i, n)
{
cin >> b[i];
sumb += b[i];
}
int ans = min((2 * suma) - a[0] + sumb + 2, (2 * sumb) - b[0] + suma + 2);
cout << ans << "\n";
}
return 0;
}
Editorialist's Solution
Language: C++17 (gcc 9.1)
#include <bits/stdc++.h>
using namespace std;
typedef long long int big;
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
int a;
for (int i = 0; i < n; i++)
{
cin >> a;
}
int b;
for (int i = 0; i < n; i++)
{
cin >> b;
}
cout << (a + b) * (n - 1) + 2 + min(a, b) * n + max(a, b) << "\n";
}
return 0;
}