PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Rudro Debnath
Tester: Takuki Kurokawa
Editorialist: Yash Kulkarni
DIFFICULTY:
1363
PREREQUISITES:
PROBLEM:
You are given an array containing \texttt{2*N} integers.
You can do only the below operation any number of times:
- Choose any a[i] such that a[i] is even and divide it by 2.
- Choose any a[i] and multiply it by 2.
Find the minimum number of operation required to make the count of even and odd numbers equal.
EXPLANATION:
Let us first know the minimum number of operations required to change the parity of any element in the given array:
- The minimum number of operations required to convert any odd number in the array to an even number is 1 i.e. by using the second operation once.
- Any even number can be represented as C.2^B, where C is odd and B \geq 1. The minimum number of operations required to convert any even number (C.2^B) in the array to an odd number is B i.e. by applying the first operation B times so that the new number os C. There is no point in applying the second operation on an even number.
For an even number X = C.2^B, we can find out B in O(log(X)) time complexity. We will store the B's (for all even numbers in the given array) in an array say D.
Let there be O odd numbers and E ( =2N - O) even numbers in the array. There can be only three possibilities:
- O = E, the answer is zero.
- O > E, we need to change (O - E)/2 odd numbers to even numbers. This will require a minimum of (O - E)/2 operations.
- E > O, we need to change (E - O)/2 even numbers to odd numbers. We will choose the even numbers with the least B's to be changed to odd numbers for the least number of operations. So, the answer is the sum of (E - O)/2 minimum elements in array D.
TIME COMPLEXITY:
O(Nlog(max(A_i))) + O(NlogN) for each test case.
SOLUTION:
Setter's solution
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector<int> a(2 * n);
for (int i = 0; i < 2 * n; i++) {
cin >> a[i];
}
vector<int> p2(2 * n);
for (int i = 0; i < 2 * n; i++) {
while (a[i] % 2 == 0) {
a[i] /= 2;
p2[i]++;
}
}
sort(p2.begin(), p2.end());
int odds = (int) count(p2.begin(), p2.end(), 0);
int ans = 0;
if (odds <= n) {
for (int i = 0; i < n; i++) {
ans += p2[i];
}
} else {
ans = odds - n;
}
cout << ans << endl;
}
return 0;
}
Editorialist's Solution
using namespace std;
int main() {
int T;
cin >> T;
while(T--){
int n;
cin >> n;
n*=2;
vector<int>a(n);
int e=0,o=0;
vector<int>make_o;
for(int i=0;i<n;i++){
cin >> a[i];
if(a[i]%2)o++;
else{
e++;
int x=0;
while(a[i]%2==0){
x++;
a[i]/=2;
}
make_o.push_back(x);
}
}
sort(make_o.begin(),make_o.end());
if(o>=e)cout << (o-e)/2 << endl;
else{
int ans=0;
for(int i=0;i<(e-o)/2;i++)ans+=make_o[i];
cout << ans << endl;
}
}
return 0;
}
