PROBLEM LINK:
- Practice
- Contest: Division 1
- Contest: Division 2
- Contest: Division 3
- Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: theminacious
PREREQUISITES: None
PROBLEM STATEMENT: You are given an array AAA that you can rearrange in any way. Your goal is to maximize the number of odd prefix sums derived from this array.
EXPLANATION: Let Pi=A1+A2+…+AiP_i = A_1 + A_2 + \ldots + A_iPi=A1+A2+…+Ai represent the iii-th prefix sum of the array AAA. The concept of parity determines whether a number is even or odd. Here are the key points to consider:
- If the last element AiA_iAi is even, then the parity of PiP_iPi will remain the same as that of Pi−1P_{i-1}Pi−1.
- If AiA_iAi is odd, then PiP_iPi will have the opposite parity of Pi−1P_{i-1}Pi−1.
Starting with P0=0P_0 = 0P0=0 (which is even), each odd number in the array switches the current parity from even to odd or vice versa.
If there are kkk odd numbers in AAA, the parity will switch kkk times. Out of these switches, approximately ceil(k2)\text{ceil}\left(\frac{k}{2}\right)ceil(2k) will yield odd prefix sums, as the very first switch will result in an odd number.
For the even numbers, which total N−kN - kN−k, they can be placed after the first odd number. Each of these even numbers contributes to additional odd prefix sums, resulting in N−kN - kN−k more odd prefix sums.
Therefore, the maximum possible number of odd prefix sums can be expressed as:
N−k+ceil(k2)N - k + \text{ceil}\left(\frac{k}{2}\right)N−k+ceil(2k)
Special Case: If k=0k = 0k=0 (meaning there are no odd numbers), the output should be 000, as it’s impossible to generate odd prefix sums with only even numbers.
TIME COMPLEXITY:
The solution runs in O(N)\mathcal{O}(N)O(N) for each test case.
C++ Implementation:
include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int oc = 0, ec = 0;
for (int i = 0; i < n; i++) {
if (arr[i] % 2 == 0) {
ec++;
} else {
oc++;
}
}
cout << (oc ? ec + (oc + 1) / 2 : 0) << endl;
}
return 0;
}