LCKDSAFE - Editorial

PROBLEM LINK:

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

Author: Evgeny Karpovich
Tester: Felipe Mota
Editorialist: Evgeny Karpovich

DIFFICULTY:

Medium-Hard

PREREQUISITES:

Divide-and-conquer algorithm.

PROBLEM:

It is necessary to calculate the number of array subsegments that the following condition is met:
(A_l \lor A_{l+1} \lor \ldots \lor A_r) \oplus (A_l \land A_{l+1} \land \ldots \land A_r) \geq \max(A_l, A_{l+1}, \ldots, A_r) \,.

QUICK EXPLANATION:

Let’s do divide and conquer algorithm and notice that you can do 2 pointers.

EXPLANATION:

Let’s use Divide-and-conquer algorithm.

Let’s suppose we want to find the answer for the segment of array l \ldots r. Then let’s find the answers for its left half, right half and answers when the bounds of the segment are located in different halves.

We now need to learn how to find the answer when the bounds are in different halves. Let’s fix one of the bounds (at this if the left bound is fixed, then the maximum will be located in the left half; similarly with the right bound).

The solutions for the halves are similar, so let’s consider the left half (i.e. the left bound is fixed). Let’s iterate over all left bounds in descending order and maintain a pointer ptr\_r in the right half so that all right bounds that are less than ptr\_r would satisfy the condition of maximum.

Notice that if we add numbers to the array, the value or \oplus and won’t decrease. Let’s maintain one more pointer ptr\_l such that if we consider all right bounds greater or equal to ptr\_l, they will satisfy the following condition: with the fixed maximum or \oplus and \geq max. The answer for the left bound is equal to ptr\_r - ptr\_l.

Let’s find the complexity of the algorithm. Divide-and-conquer works in O(n \cdot \log n), but the pointer ptr\_l can be moved in two directions. It will not be spent more than O(n \cdot \log MAX(A_i)) operations for its movement, because if or \oplus and in the left half does not change, then the pointer moves to the right only, and if it does change (it will not happen more than O(\log MAX(A_i)) times), then we will move it to the begin in the worst case scenario.

SOLUTIONS:

Setter's Solution
    #include<bits/stdc++.h>

    using namespace std;

    typedef long long ll;
    int const maxn = 1e6 + 5;
    ll a[maxn];
    ll ans = 0;
    ll pref_or[maxn], suff_or[maxn];
    ll pref_and[maxn], suff_and[maxn];
    ll pref_max[maxn], suff_max[maxn];

    void calc(int l, int m, int r) {
        ll val_or = a[m], val_and = a[m], mx = a[m];

        for (int i = m; i >= l; --i) {
            val_or = (val_or|a[i]);
            val_and = (val_and&a[i]);
            mx = max(mx, a[i]);

            suff_or[i] = val_or;
            suff_and[i] = val_and;
            suff_max[i] = mx;
        }

        val_or = a[m + 1], val_and = a[m + 1], mx = a[m + 1];
        for (int i = m + 1; i <= r; ++i) {
            val_or = (val_or|a[i]);
            val_and = (val_and&a[i]);
            mx = max(mx, a[i]);

            pref_or[i] = val_or;
            pref_and[i] = val_and;
            pref_max[i] = mx;
        }
    }

    void solve(int l, int r) {
        if (l == r) {
            if (a[l] == 0) {
                ans++;
            }
            return;
        }

        int m = (r + l) / 2;
        calc(l, m, r);

        int ptr_l = m + 1, ptr_r = m + 1;
        for (int L = m; L >= l; --L) {
            while (ptr_r <= r && pref_max[ptr_r] <= suff_max[L]) ptr_r++;
            while (ptr_l < ptr_r && ((suff_or[L]|pref_or[ptr_l])^(suff_and[L]&pref_and[ptr_l])) < suff_max[L]) ptr_l++;
            while (ptr_l >= m + 2 && ((suff_or[L]|pref_or[ptr_l - 1])^(suff_and[L]&pref_and[ptr_l - 1])) >= suff_max[L]) ptr_l--;
            ans += (ll)max(0, ptr_r - ptr_l);
        }

        ptr_r = m, ptr_l = m;
        for (int R = m + 1; R <= r; ++R) {
            while (ptr_r >= l && suff_max[ptr_r] < pref_max[R]) ptr_r--;
            while (ptr_l > ptr_r && ((pref_or[R]|suff_or[ptr_l])^(pref_and[R]&suff_and[ptr_l])) < pref_max[R]) ptr_l--;
            while (ptr_l < m && ((pref_or[R]|suff_or[ptr_l + 1])^(pref_and[R]&suff_and[ptr_l + 1])) >= pref_max[R]) ptr_l++;
            ans += (ll)max(0, ptr_l - ptr_r);
        }

        solve(l, m);
        solve(m + 1, r);
    }

   int main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        int n, t;
        cin >> t;
        while (t--) {
            cin >> n;
            for (int i = 1; i <= n; ++i) cin >> a[i];
            ans = 0;
            solve(1, n);
            cout << ans << '\n';
        }
        return 0;
    }

8 Likes

I liked this problem so much… wooah… :star_struck:

2 Likes

Can you syntax-highlight the setters code: Instead of indenting the code by 4 spaces, surround it by

```cpp
<code>
```

Quite a different solution than what I was thinking.
I tried to decompose it into bit by bit.

For a bitstream of (1101101111) all the eq* starting with consecutive ones will make the eq invalid.
Meaning, 11111 is invalid, 0111 is valid.
In above example, if right bound is fixed at last element, number of invalid subsequences are 4 and rest are valid.

Invalid ones are: (11), (111), (1111), (1)
All sequences starting before left=last-4 (01111), (101111), etc are valid.

Then I devised a way to merge the bits from MSB to LSB. Code works fine.

Eq*: Equation of AND XOR OR >= max

Very poor explanation. The editorial has explained what D&C is, not how it’s to be used in this problem.

This doesn’t make any sense tbh. I think you meant: “after fixing the left bound, we consider all right bounds (that lie in the right half) such that the maximum element lies in the left half contained by the sub array.”

Sure, this is the crux of the solution. What’s the point of the editorial if the reasoning behind this is not shown?

Also, consider elaborating on how ptr_l and ptr_r are updated, rather than making readers view the code for details.

1 Like

I did everything according to the instructions.

2 Likes

I will repeat the idea of ​​the solution with a few details.

Suppose we now want to know the number of good segments on the segment l, r. The middle of this segment is m. Let’s fix the left border, which is in the l..m segment, and say that this is the maximum. Then we know that some prefix of the right boundaries from m + 1 to r satisfies the condition of reaching a maximum in the left half.

Note that if we add numbers to the current non-empty set, then the value of or \oplus and will not decrease, since if there was one in the bit, it will never become 0. If the bit had one, then it was in or and and this bit was 0 - and this will always be when adding new numbers.

Everything else is the subtleties of the implementation of the divide and conquer algorithm.

1 Like

I agree that the editorial is hard to read, mostly because essential steps are skipped over. I figured out what was meant by the setters solution.
I will explain the idea of the setters solution (As I myself was on a too complicated approach that I couldn’t get to work fast enough). As I have not implemented it my explanation may have off-by-one errors.

The idea is to apply divide and conquer. D&C splits ranges in half each time. In a iteration we have the range [l,r) , and m is the split point. Then we will count the number of valid ranges crossing the split point. We count those in two parts:
suppose we consider a valid range [a,b) with l\leq a<m\leq b<r. The maximum of this range can be in [a,m) or in [m,b). If it is in [a,m) or in both we will count it in the first part; otherwise we will count it in the second.

I will expand below on how to count part 1, the valid ranges crossing m with the maximum on the left side. Counting part 2 is similar, but flipped around m

To start we precompute or[i], and[i], max[i] for indices i\in[l,r). These are defined as follows:
\mathtt{or[i]=A_i\lor A_{i+1}\lor\ldots\lor A_{m-1}} if i< m
\mathtt{or[i]=A_m\lor A_{m+1}\lor\ldots\lor A_{i}} if i\geq m
\mathtt{and[i]=A_i\land A_{i+1}\land\ldots\land A_{m-1}} if i< m
\mathtt{and[i]=A_m\land A_{m+1}\land\ldots\land A_{i}} if i\geq m
\mathtt{max[i]=\max(A_i, A_{i+1},\ldots, A_{m-1}}) if i< m
\mathtt{max[i]=\max(A_m, A_{m+1},\ldots, A_{i}}) if i\geq m
Or in short; the max/or/and of the range from m to i.

Why are these helpful. It’s because the halves are sorted:
if \mathtt{i\leq j<m} or \mathtt{m\leq j\leq i} then \mathtt{max[i]\geq max[j]} and \mathtt{(or[i]\oplus and[i])\geq(or[j]\oplus and[j])}

We will now iterate a (the left index of the ranges we are counting) from m-1 down to l. We are going to count the number of b (corresponding right index) in [m,r) that will give a valid range where the maximum is in [a,m) (as we are doing part one).

That last part gives us a restriction on the b's we can choose: \mathtt{max[b]\leq max[a]}, and because max is sorted this gives a maximum for b: ptr_r, so that \mathtt{max[ptr_r]>max[a]} and \mathtt{ max[ptr_r-1]\leq max[a]}. So now we know that \mathtt{b<ptr_r} must hold. When we decrement a by one we need to find a new \mathtt{ptr_r} which is at least as big as the previous. This allows to find all of them in \mathcal{O}(r-m) time.

The valid range requirement gives us a lower bound on b. It can be stated as \mathtt{(or[a]\lor or[b])\oplus(and[a]\land and[b])\geq max[a]}. The left hand side increases as we increase b, and we set \mathtt{ptr_l} to be the first b that satisfies this equation. When we decrement a we need to find the new \mathtt{ptr_l}, which can be on both sides of the old one. The editorial has a good explanation why this pointer is moved at most 2\cdot\lg(2^{60})(r-l) times.

For each a we have now calculated the lower bound \mathtt{ptr_l} and upper bound \mathtt{ptr_r} of b. These encode the only requirements we had. So there are \mathtt{ptr_r-ptr_l} valid ranges starting at a and crossing m.

To wrap up an overview:
With a D&C approach we recursively split the entire array into ranges [l,r) with midpoint m. We count the number of valid ranges [a,b)\subseteq [l,r) crossing m in two parts, those where the largest element is on the left of m and those where it is on the right. In each part we iterate over one of the endpoints of [a,b) while we maintain two pointers ptr_l and ptr_r. The purpose of ptr_r is to ensure that the largest element is indeed on the left of m, the purpose of ptr_l is to ensure it is a valid range. So for each iteration we add ptr_r-ptr_l

What I learned while writing this
  • $\mathtt{}$ is awesome! being able to have monospaced math is very handy.
10 Likes

i simply do binary search and got 40 points
maybe because of limited test cases.
and then i waste lots on time on it to improve time complexity.
but lol its divide and conquer

1 Like

Is total time O(nlogn60)?

2 Likes

Нет, общее время O (n log n + n * 60)

Thank you for the detailed analysis.

I can explain to you the reason why this analysis is without details.

I believe that the analysis should reflect the ideas and tell a little about them, and think out the details of the participants’ implementation themselves or look at the author’s solution, since only such solutions of problems will be useful

Видимо я что-то не понимаю: на каждом уровне максимум logAi раз ptr_l будет двигаться влево n итераций. Итого: n * logAi + 2 * (n / 2) * logAi + 4 * (n / 4) * logAi + …

@spaanse, thank you very much for this detailed explanation.

This is more like an editorial. Tho the subtleties of the implementation could be shortened, I think this is much more readable and easier to understand. More in line with CodeChef editorials (which are usually considered of a higher standard than CodeForces ones).

Also, there are certain grammatical errors, that make it hard to understand the editorial. Consider using grammerly to help write clear statements.

ptrl двигается влево только тогда, когда изменяется величина or \oplus and. Суммарно по всем уровням она продвигается не более O(n * 60) итераций.

I can agree that my explanation is a bit more on the implementation detail side, that a good editorial should be somewhere between our two.

I think what is missing in your editorial is a flow of ideas. Like you can’t use a variable before it is defined, you can’t use an idea that hasn’t been explained. In an explanation that means explaining the what and why before the how.

what: we are going to count these ranges crossing b in two parts
why(optional but nice): because then we find the maximum value easier
how: by splitting the ranges into those having the largest on the left or on the right

In the how part you can have new what/why/how sequences until the level of detail your comfortable with. Compare it to code: an idea is a variable, the what is it’s declaration, the why a comment explaining what it is for and the how an assignment to that variable.

PS: I’m dutch, were used to giving quite direct feedback. Don’t take anything I say as an insult, my intention is to help improve your future editorials. I know writing is hard.

4 Likes

Could you explain more detailed? As I understood, at each interval [l, r] the value or ^ and can change 60 times, and after each change we may start at the beginning again and have to increase to r. So each interval it seems to cost O(60 * (r - l)), so with all the intervals, isn’t it O(nlogn*60)

Please help me :< Thanks