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);
}
The event is a part of our annual tech symposium Exun 2021-22, powered by Athena Education.