MAKEODD - Editorial

PROBLEM LINK:

Practice
Div-3 Contest
Div-2 Contest
Div-1 Contest

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

DIFFICULTY:

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);

int calc(int mask) {
    if (dp[mask] != -1) // If we have already calculated dp[mask], we return the computed value
        return dp[mask];
    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
        int nmask = mask;
        for (int j = i; j < 20; ++j) {
            if (nmask&(1<<j)) {
                nmask ^= (1<<j);
                nmask |= (1<<(j-i));
            }
        }
        // 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
    }
    return dp[mask] = 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]) {
        int nmask = mask | v[i]; // Now for all previous masks, we calculate what the new mask will be 
        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);

int calc(int mask) {
    if (dp[mask] != -1) // If we have already calculated dp[mask], we return the computed value
        return dp[mask];
    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
        int nmask = mask;
        for (int j = i; j < 20; ++j) {
            if (nmask&(1<<j)) {
                nmask ^= (1<<j);
                nmask |= (1<<(j-i));
            }
        }
        // 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
    }
    return dp[mask] = 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]) {
            int nmask = mask | v[i]; // Now for all previous masks, we calculate what the new mask will be
            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) {
	return readInt(l, r, ' ');
}
long long readIntLn(long long l, long long r) {
	return readInt(l, r, '\n');
}
string readStringLn(int l, int r) {
	return readString(l, r, '\n');
}
string readStringSp(int l, int r) {
	return readString(l, r, ' ');
}

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

	const uint32_t maskWidth = 20;
	vector<uint32_t> vFMask(1 << maskWidth, maskWidth);
	vFMask[0] = 0;

	for (uint32_t actMask = 1; actMask < vFMask.size(); ++actMask)
	{
		for (uint32_t shiftVal = 1; shiftVal < maskWidth; ++shiftVal)
		{
			uint32_t tmp = actMask >> shiftVal;
			uint32_t tmp2 = (actMask) & ((1<< (shiftVal - 1))-1);
			vFMask[actMask] = std::min(vFMask[tmp | tmp2] + 1, vFMask[actMask]);
		}
	}

	int T = readIntLn(1, 1000);
	uint32_t sumN = 0;
	for (int tc = 0; tc < T; ++tc)
	{
		uint32_t N = readIntLn(1, 100'000);
		sumN += N;
		int32_t actr = 0;
		vector<uint32_t> A(N);
		vector<int32_t> B(N);
		vector<set<uint32_t>> AS(maskWidth);
		for (auto&& ai : A)
		{
			if (actr + 1 != N)
				ai = readIntSp(1, 1'000'000);
			else
				ai = readIntLn(1, 1'000'000);
			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;
					}
				}
				res += (newPos - actPos) * vFMask[currMask];
				if (newPos == N)
					break;
				actPos = newPos;
				currMask |= 1 << bestSHV;
			}
		}
		printf("%llu\n", res);
	}
	assert(sumN <= 500'000);
	assert(getchar() == -1);
}
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].