PROBLEM LINK:
Division 1
Division 2
Video Editorial
Author: Ildar Gainullin
Tester: Radoslav Dimitrov
Editorialist: Srikkanth
DIFFICULTY:
Medium
PREREQUISITES:
Bit-Manipulation and Basics
PROBLEM:
Given an array A, of size n, compute the \sum_{i=1}^{n}\sum_{j=1}^{i} f({A_i, A_{i+1}... A_j})
where,
f(B) is the minimum value that remains after repeatedly applying the following procedure
until a size of B is 1.
- Take any two different indices i and j, remove A_i and A_j and insert g(A_i, A_j)
where g(a, b) = highest power of two \leq a xor b
EXPLANATION:
Firstly the operation is a bit complicated, however let’s see if we can simplify it.
After playing around with the possibilities for some time, we make the following observation
Let the highest set bit, in all values be p.
The parity of the number of values that have p^{th} bit set is invariant.
We can easily verify this by taking cases,
- If both A_i and A_j have p^{th} bit set, then count decreases by 2
- If exactly one has p^{th} bit set, then count doesn’t change (one is removed and one is added)
- If neither has p^{th} bit set, then count doesn’t change
So if we have odd number of values in B with p^{th} bit set, then we cannot hope to make f(B) smaller than 2^p
Next step is identifying if there’s a construction that can get the minimum value in these cases.
- If count is even, and there are atleast 5 numbers, we can make the answer 0.
Take any two numbers with p^{th} bit set, say a and b.- If there are two numbers c and d without p^{th} bit set, combining a, c and combining b, d
Now we have two 2^p's in the the array.
Other than the two 2^p's, group other numbers which have p^{th} bit set and combine them, result does not contain p^{th} bit.
Now exactly two numbers contain p^{th} bit, and they are 2^p. Remove all other numbers by combining with 2^p.
Finally combine the two 2^p's to get 0. - If there aren’t two numbers c and d, we can combine two numbers that contain p^{th} bit and produce required c, d
and repeat the above process to get 0.
- If there are two numbers c and d without p^{th} bit set, combining a, c and combining b, d
- If count is odd, and there are atleast 5 numbers, we can make the answer 2^p.
Take any number that has p^{th} bit set and combine with every value that doesn’t contain it.
Subsequently pairing the other numbers in any order results in 2^p and finally combining with 2^p gives the answer.
So for all subarrays with size greater than 5, we can obtain f easily, simply count the parity of numbers containing highest set bit in the array and if it is even, answer is 0 otherwise answer is 2^p.
For subarrays with size less than 5, we can brute force the answer.
There are \mathcal{O}(n) subarrays of size less than 5, evaluate each separately.
For others we can use the above criterion, and maintain frequencies of highest set bit’s as we traverse all subarrays,
and easily get an \mathcal{O}(n^2) solution.
To optimise this, let’s suppose the answer is 2^p, and count the number of subarrays that have odd number of elements with p^{th} bit set.
Iterate from maximum p (i.e 30) to 0.
Say the indices that contain p^{th} bit are i_1, i_2, ... i_k
Let’s iterate over the prefixes from 1, 2, ... n and maintain odd\_count and eve\_count, the number of prefixes that have odd and even number of elements with p^{th} bit set respectively.
Fix the end point (at say j), at this point, if we have odd (or even) elements in the prefix then the possible starting points correspond to the even (or odd) prefixes.
So we can obtain the answer in \mathcal{O}(n) for single p.
For smaller p's, we can recursively obtain the answers for the subarrays [1, i_1), (i_1,i_2), ... (i_k, n) and add them.
For each p, the total work done is \mathcal{O}(n) and the total complexity is \mathcal{O}(n \log A_{max}), which easily passes for 100 pts.
TIME COMPLEXITY:
TIME: \mathcal{O}(n \log A_{max})
SPACE: \mathcal{O}(n)
SOLUTIONS:
Setter's Solution
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
using namespace std;
typedef long long ll;
#ifdef iq
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
const int M = 998244353;
void add(int &a, int b) {
a += b;
if (a >= M) a -= M;
}
int f(int x) {
for (int i = 29; i >= 0; i--) {
if ((x >> i) & 1) {
return (1 << i);
}
}
return 0;
}
int cost(vector <int> a) {
if (a.size() == 1) return a[0];
else {
int ans = (1 << 30);
for (int i = 0; i < (int) a.size(); i++) {
for (int j = i + 1; j < (int) a.size(); j++) {
auto b = a;
b[i] = f(a[i] ^ a[j]);
b.erase(b.begin() + j);
ans = min(ans, cost(b));
}
}
return ans;
}
}
int ret(vector <int> ok, int x) {
vector <int> ret(2);
int pref = 0;
ret[0]++;
int s = 0;
for (int &y : ok) {
if ((y >> x) & 1) {
pref ^= 1;
}
add(s, ret[pref ^ 1]);
ret[pref]++;
}
for (int i = 0; i < (int) ok.size(); i++) {
int cur = 0;
for (int j = i; j < i + 4 && j < (int) ok.size(); j++) {
cur ^= ok[j];
if ((cur >> x) & 1) {
add(s, M - 1);
}
}
}
return (s * (ll) (1 << x)) % M;
}
int main() {
#ifdef iq
freopen("a.in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector <int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int sum = 0;
for (int i = 0; i < n; i++) {
vector <int> b;
for (int j = i; j < n && j < i + 4; j++) {
b.push_back(a[j]);
add(sum, cost(b));
}
}
for (int x = 29; x >= 0; x--) {
vector <int> ok;
for (int i = 0; i < n; i++) {
if (a[i] >= (1 << (x + 1))) {
add(sum, ret(ok, x));
ok.clear();
} else {
ok.push_back(a[i]);
}
}
add(sum, ret(ok, x));
}
cout << sum << '\n';
}
.