SEGCOMPR - Editorial

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 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';
}

2 Likes

Tried but was unable to solve :sweat_smile:.
Great problem though.

nice problem of observation and prefix cnt

Can someone please tell me what is wrong with this logic. Not able to find WA testcase.
Steps:
Let denote g(a,b) by G.

  1. for N <=4, return answer by brute force.

  2. for N>4,
    Let K be the maximum set bit in largest number in array. Lets group all elements into two parts y_i and x_i. Therefore, y1,y2,y3…y_m , x1,x2…x_n be the elements of array, where x_i are the elements with maximum set bit equal to K. and y_i are the remaining numbers.
    e.g
    In 2, 3, 5, 6, 7, here K = 2 ( max bit in 7),
    So, y1 = 2 , y2=3, x1=5, x2=6, x3=7
    Here in each x_i, K is the max set bit. and remaining numbers are in y_i.

  3. Now, if count of number in x_i (i.e max bit set is K) is ODD then return 1<<K. Because to neutralize every Kth bit we need atleast even count. Otherwise we cannot get rid of Kth bit.

  4. If count of numbers in x_i is not Even. then return 0. we can always make zero. (How?)

    let array be y1, y2, y3 , x1 x2 x3 x4
    steps:

    1. Find G for x3 and x4 let be y4 (Kth bit is removed)
      new array ---> y1 y2 y3 y4 x1 x2
    2. Find G for x2 to each of y2, y3, y4, i.e G(y2, G(y3, G(y4,x2))) each of them will give same value let be x5 (Kth bit is still set)
      new array ---> y1 x1 x5
    3. now xor x1 and y1 , this will be equal to x5. hence answer is zero.

    similarly, when x_i will contain even count, we perform G by picking any two which will give some number without Kth set bit (hence must be part of y_i). Finally when we remain with 2 elements in x_i, we remove all y_i and make both x_i equal. So answer should be zero in each of these cases.

    let take another example with zero count of y_i ,
    let array be x1 x2 x3 x4 x5, x6 , all having max set bit K.
    steps:

    1. Find y1 = G(x5,x6), y2 = G(x3,x4) both of these values should now be part of y_i.
      new array ---> y1 y2 x1 x2
    2. Now again make x1 and x2 equal by G(x1,y1) and G(x2,y2)
    3. Finally, answer will be zero.

    I am not able to find what is wrong with it and what test case it is missing.

    Link to attempt: https://www.codechef.com/viewsolution/38850077

    Edit: replied without reading editorial. Now found logic is similar.

why does my code failed for the final subtask. I implemented the exact similar logic but still it gave WA for the final subtask.

my code - https://www.codechef.com/viewsolution/38885307