PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author:
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
Bitmask dynamic programming
PROBLEM:
You’re given an array A of length N. You can rearrange it however you like.
Find the maximum possible number of distinct prefix ORs possible.
0 \leq A_i \leq N
EXPLANATION:
Given that we’re dealing with prefix bitwise ORs, it might seem tempting to use the fact that there are only \mathcal{O}(\log N) distinct prefix ORs, and then try to greedily maximize the number of these.
However, no correct greedy solution is known to us, and we won’t even use the fact that there are \mathcal{O}(\log N) distinct prefix ORs.
Instead, we use another constraint: the fact that 0 \leq A_i \leq N, meaning that any prefix OR created can be no more than 2N.
Suppose the sequence of bitwise ORs we want to create is x_1, x_2, \ldots, x_k.
Note that one way to achieve this is as follows:
- First, place all elements that are a submask of x_1.
- If their bitwise OR isn’t equal to x_1, it’s not possible to obtain x_1 as a bitwise OR at all.
- Next, place all remaining elements that are submasks of x_2.
- Again, only valid if the bitwise OR of everything so far is itself x_2.
- Then place every element that’s a submask of x_3, then x_4, and so on.
It’s not hard to see why this works: if for some x_i the bitwise OR of all submasks of x_i doesn’t equal x_i itself, it’s impossible to obtain x_i as a bitwise OR at all.
Otherwise, the sequence of bitwise ORs created will at least contain x_1, x_2, \ldots, x_k; so in an optimal solution it’ll be exactly these values.
We can use this idea to write dynamic programming that computes the answer.
Let \text{sub}_{mask} denote the bitwise OR of all submasks of mask.
This can be computed as follows:
- If mask exists in A, \text{sub}_{mask} = mask.
- Otherwise, \text{sub}_mask equals the bitwise OR of \text{sub}_x across all submasks of x.
- To optimize this, note that we don’t need to iterate through all submasks: it’s enough to consider only those submasks with one bit removed.
That is, we have \text{sub}_{mask} to be the bitwise OR of all \text{sub}_{mask \oplus 2^b}, where b is a bit that’s set in mask.
- To optimize this, note that we don’t need to iterate through all submasks: it’s enough to consider only those submasks with one bit removed.
Once this is known, let’s define dp_{mask} to be the maximum number of distinct prefix ORs we can obtain, using only the bits in mask.
This can be computed in similar fashion:
- First, there’s the case where mask itself doesn’t appear as a prefix OR - in which case we need to consider all subsets of mask instead.
- So, we obtain dp_{mask} to be the maximum of all dp_{mask \ \oplus\ 2^b} across all bits b set in mask.
- We also consider the case where mask itself appears as a prefix OR. Note that this is only possible if \text{sub}_{mask} = mask.
- Here, we obtain dp_{mask} to be the maximum of all (dp_{mask \ \oplus\ 2^b}) + 1, across all bits set in mask.
Once all the dp values are computed, the answer is simply \max(dp).
Recall that we observed at the start that the bitwise ORs will never exceed 2N, so it’s enough to consider only mask \lt 2N, leading to a complexity of \mathcal{O}(N\log N).
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// template<typename T>
// using oset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
void actualcode();
#define ll long long int
#define endl "\n"
int mod = 1e9 + 7;
void YES() { cout << "YES" << endl; }
void NO() { cout << "NO" << endl; }
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// #ifndef ONLINE_JUDGE
// freopen("Test_Case_10.txt","r",stdin);
// freopen("Output_Manik.txt","w",stdout);
// #endif
actualcode();
}
void actualcode()
{
int t = 1;
cin >> t;
ll zero = 0;
while (t--)
{
int n;
cin>>n;
vector<int> arr(n);
set<int> st;
for(int i=0;i<n;i++)
{
cin>>arr[i];
st.insert(arr[i]);
}
vector<pair<int,int>> dp(2*n,{0,0});
for(int i=0;i<2*n;i++)
{
int temp = 0;
for(int j=0;j<25;j++)
{
temp |= dp[i & (~(1<<j))].first;
}
if(st.count(i)) temp |= i;
dp[i].first = temp;
temp = 0;
for(int j=0;j<25;j++)
{
temp = max(temp,dp[i & (~(1<<j))].second + (dp[i & (~(1<<j))].first != dp[i].first));
}
dp[i].second = temp;
if (i==0 && st.count(i)) dp[i].second = 1;
}
int x = (1<<(int(log2(n))+1)) - 1;
cout<<dp[x].second<<"\n";
}
}
Tester's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
void solve(int test_case){
ll n; cin >> n;
vector<ll> a(n+5);
rep1(i,n) cin >> a[i];
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// ll n = rng()%5+1;
// vector<ll> a(n+5);
// rep1(i,n) a[i] = rng()%15;
ll m = 0;
while((1<<m) <= n) m++;
vector<ll> submask_or(1<<m);
rep1(i,n) submask_or[a[i]] = a[i];
rep(bit,m){
rep(mask,1<<m){
if(mask&(1<<bit)){
submask_or[mask] |= submask_or[mask^(1<<bit)];
}
}
}
vector<ll> dp(1<<m); // dp[i] = ans if or of chosen is submask of mask
rep(mask,1<<m){
rep(bit,m){
if(mask&(1<<bit)){
ll val = dp[mask^(1<<bit)];
if(submask_or[mask]&(1<<bit)) val++;\
amax(dp[mask],val);
}
}
}
ll ans = dp[(1<<m)-1];
rep1(i,n){
if(!a[i]){
ans++;
break;
}
}
cout << ans << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
sub = [0]*(2*n)
sub[0] = 2**20
for i in range(n): sub[a[i]] = a[i]
for i in range(1, 2*n):
b = 0
while 2**b <= i:
if i & (2**b): sub[i] |= sub[i - 2**b]
b += 1
sub[i] %= 2**20
dp = [0]*(2*n)
if sub[0] == 0: dp[0] = 1
for i in range(1, 2*n):
b = 0
add = 1 if sub[i] == i else 0
while 2**b <= i:
if i& (2**b): dp[i] = max(dp[i], add + dp[i - 2**b])
b += 1
print(max(dp))