# MAKEODD - Editorial

Author: Vishesh Saraswat
Tester: Istvan Nagy
Editorialist: Vishesh Saraswat

Easy-Medium

# PREREQUISITES:

Bitmask Dynamic Programming, Bitwise operations, Maths

# PROBLEM:

Given an array A of N positive integers. In one operation you choose a non-negative integer Y and for all elements in the array divide them by 2^Y if they are divisible. f(B) for an array B is defined as the minimum operations required to make it have only odd numbers. Find the sum of f(a) over all subarrays a of A.

# SOLUTION AND EXPLANATION

Letβs simplify the problem a bit before proceeding. We can see that every positive integer can be represented as 2^p \cdot q where p is a non-negative integer and q is an odd positive integer. For odd numbers, p will be 0. Now, we can redefine f(B) as the minimum number of operations required to make p = 0 for all elements if the element is represented as 2^p \cdot q.

Another thing we can observe is that for an array B, f(B) will only depend on unique values of p in B. This is because whenever we apply an operation, duplicate values of p reduce equally.

Under the constraints of the problem, p can have at max 20 unique values. This points us to our solution β the use of bitmasks to represent arrays. We will create a bitmask from the array as the OR of all 2^p in the array. For example, if the input array is 24 15 18 40 we will create the bitmask as OR of 8 1 2 8, which will be 11 (binary representation is 1011).

Now that we have a way to represent any array as a bitmask with at most 20 bits, we can precompute the answer for all possible bitmasks, and determine f(B) for any array B efficiently. The precomputation is done in the following manner.

Precomputation Code Snippet
const int mx = (1<<20);
vector<int> dp(mx, -1);

if (mask == 1) // Base case: 00..1 is the intended mask we are trying to reach
return dp[mask] = 0; // Therefore, the answer for this is 0
int ans = (1<<30); // Assigning ans a very big value
for (int i = 0; i < 20; ++i) { // We go over all possible Y and try to divide the array by 2^Y
for (int j = i; j < 20; ++j) {
}
}
// The new bitmask created after dividing by 2^i is stored in nmask
if (mask != nmask) ans = min(ans, calc(nmask) + 1); // We find the best value for ans
}
}

void pre() {
for (int i = 1; i < mx; ++i)
if (dp[i] == -1) // If dp[i] hasn't been calculated already, we calculate dp[i]
calc(i);
}


After we have computed the value DP(mask) for all possible bitmasks, we need to find a way to efficiently find sum of f(a) over all subarrays a of A. One thing we can observe here is that after making the array have only numbers of the form 2^p, from any starting position s the OR of subarray s to e for all s \leq e \leq N will increase at max \log max(A_i) times. Therefore we only need to calculate the answer for at max N \cdot \log max(A_i) arrays.

A nice way to find at which positions the OR increases is to maintain vector of maps such that subor[i][x] stores the maximum length len for for which the subarray with indexes i-len-1, i-len-2, \ldots i has OR equal to x. This is calculated in the following manner.

subor Code Snippet
//v is the input array here
vector<map<int, int>> subor(n);
subor[0][v[0]] = 1; // For index 0, len will be 1 for OR = v[0];
for (int i = 1; i < n; ++i) {
subor[i][v[i]] = 1; // we initialise the length as 1, because it remains the same for at least 1 index
for (auto [mask, len] : subor[i-1]) {
subor[i][nmask] = max(subor[i][nmask], len+1); // And then set subor[i][nmask] as the max of it's already existing value or the length from subor[i-1] + 1
}
}


Then we can calculate the sum of f(a) for all subarrays a of A by just going over all the values stored in the map of each index.

Precomputation takes O(max(A_i)) time and finding answer for an array takes O(N \cdot \log max(A_i)) time. Therefore, total time complexity is O(max(A_i) + N \cdot \log max(A_i)).

# SOLUTIONS

Setter's / Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
*/

#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) (int)(x).size()

using ll = long long;
const int mod = 1e9+7;

const int mx = (1<<20);
vector<int> dp(mx, -1);

if (mask == 1) // Base case: 00..1 is the intended mask we are trying to reach
return dp[mask] = 0; // Therefore, the answer for this is 0
int ans = (1<<30); // Assigning ans a very big value
for (int i = 0; i < 20; ++i) { // We go over all possible Y and try to divide the array by 2^Y
for (int j = i; j < 20; ++j) {
}
}
// The new bitmask created after dividing by 2^i is stored in nmask
if (mask != nmask) ans = min(ans, calc(nmask) + 1); // We find the best value for ans
}
}

void pre() {
for (int i = 1; i < mx; ++i)
if (dp[i] == -1) // If dp[i] hasn't been calculated already, we calculate dp[i]
calc(i);
}

void solve(int tc) {
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; ++i) {
cin >> v[i];
int temp = 1;
while (v[i] % 2 == 0) {
v[i] /= 2;
temp *= 2;
}
v[i] = temp;
}

//v is the input array here
vector<map<int, int>> subor(n);
subor[0][v[0]] = 1; // For index 0, len will be 1 for OR = v[0];
for (int i = 1; i < n; ++i) {
subor[i][v[i]] = 1; // we initialise the length as 1, because it remains the same for at least 1 index
for (auto [mask, len] : subor[i-1]) {
subor[i][nmask] = max(subor[i][nmask], len+1); // And then set subor[i][nmask] as the max of it's already existing value or the length from subor[i-1] + 1
}
}

ll ans = 0;
for (int i = 0; i < n; ++i) {
int prev = 0;
for (auto [mask, len] : subor[i]) {
ans += dp[mask] * (len - prev);
prev = len;
}
}

cout << ans << '\n';
}

signed main() {
cin.tie(0)->sync_with_stdio(0);
int tc = 1;
cin >> tc;
pre();
for (int i = 1; i <= tc; ++i) solve(i);
return 0;
}

Tester's Solution
#include <iostream>
#include <algorithm>
#include <string>
#include <cassert>
#include <vector>
#include <set>
#include <numeric>
using namespace std;

#ifdef HOME
#define NOMINMAX
#include <windows.h>
#endif

long long readInt(long long l, long long r, char endd) {
long long x = 0;
int cnt = 0;
int fi = -1;
bool is_neg = false;
while (true) {
char g = getchar();
if (g == '-') {
assert(fi == -1);
is_neg = true;
continue;
}
if ('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if (cnt == 0) {
fi = g - '0';
}
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);

assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if (g == endd) {
assert(cnt > 0);
if (is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
}
else {
//assert(false);
}
}
}

string readString(int l, int r, char endd) {
string ret = "";
int cnt = 0;
while (true) {
char g = getchar();
assert(g != -1);
if (g == endd) {
break;
}
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l, long long r) {
}
long long readIntLn(long long l, long long r) {
}
string readStringLn(int l, int r) {
}
string readStringSp(int l, int r) {
}

int main() {
#ifdef HOME
if (IsDebuggerPresent())
{
freopen("../in.txt", "rb", stdin);
freopen("../out.txt", "wb", stdout);
}
#endif

{
for (uint32_t shiftVal = 1; shiftVal < maskWidth; ++shiftVal)
{
uint32_t tmp = actMask >> shiftVal;
uint32_t tmp2 = (actMask) & ((1<< (shiftVal - 1))-1);
}
}

uint32_t sumN = 0;
for (int tc = 0; tc < T; ++tc)
{
sumN += N;
int32_t actr = 0;
vector<uint32_t> A(N);
vector<int32_t> B(N);
for (auto&& ai : A)
{
if (actr + 1 != N)
else
int32_t tmp = 0;
while (((1 << tmp) & ai) == 0)
++tmp;
if (tmp > 0)
AS[tmp - 1].insert(actr);
B[actr] = tmp - 1;
++actr;
}
for (auto& ASI : AS)
ASI.insert(N);
uint64_t res = 0;
for (uint32_t pos = 0; pos < N; ++pos)
{
int32_t currV = B[pos];
uint32_t currMask = currV >= 0 ? 1 << currV : 0;
uint32_t actPos = pos;
while (true)
{
uint32_t newPos = N;
uint32_t bestSHV = 0;
for (uint32_t shV = 0; shV < maskWidth; ++shV)
{
if ((currMask >> shV) & 1)
continue;
uint32_t candPos = *AS[shV].lower_bound(actPos);
if (candPos < newPos)
{
bestSHV = shV;
newPos = candPos;
}
}
if (newPos == N)
break;
actPos = newPos;
}
}
printf("%llu\n", res);
}
assert(sumN <= 500'000);
assert(getchar() == -1);
}


The event is a part of our annual tech symposium Exun 2021-22, powered by Athena Education.

4 Likes

Thanks for this editorial.

I have spent many hours on this problem. I am writing this reply so that if someone is stuck like I was, this might be helpful to him.

First I thought that the minimum number of operations to make array odd is same as the number of unique powers of 2 other than (2^0).

Example: [2,4] β 2,
[1,2,4] β 2.

But it was wrong.
Example: [64,16,4].

The number of unique powers: 3.
But it can be made odd in just 2 operations.

Choose X=16.
[64,16,4] β [4,1,4].

Choose X=4.
[4,1,4] β [1,1,1].

3 Likes

Thanks, man for that speical case, I was thinking the same way.

1 Like