Auto comment: topic has been updated by randomx_123 (previous revision, new revision, compare).

A few hints for problem 2 in your post:

Problem 1: a[i] & x == 0 iff a[i] is a submask of ~x. Rephrasing the problem, you're given a mask and you want to know whether there's its submask in the array. Use sum over submasks dp to pre-compute the answer for all ~x values at once and then answer each query in $$$\mathcal{O}(1)$$$ by accessing this pre-computed array.

Both the problems are well known :) .

Problem-1 can be solved using Trie.

Off topic,

I have seen another set in which the first question was some significantly easier stack question and the second question was same. So while selection is some kind of normalization done? Or is it the case that people of same college get same set?(which is kind of pointless)

Problem 1 is same as this one https://mirror.codeforces.com/contest/165/problem/E The only difference being the array itself forms the queries

the first one is a basic question of tries , you need to find the prefix of your choice if the number has a 1 find a 0 else if its 0 then look for 1 or 0.

the second one is also a standard question called inversion count , we can make a prefix. sum array of the string by converting the 0's to -1 and keeping 1 as 1, then it can be solved using merge sort, bit tree, avl tree, ordered set and idk if there are more ways

I have a very easy approach for problem A which no-one has mentioned.

We'll create a vector of sets in which v[i] will contain set of possible elements if we consider rightmost i bits for every element

Now for X let j be the index of most significant bit of X (from right) So we will query in v[j] for complement of X and if it exists answer is yes otherwise no.

Proof :- if X&Y==0 then after removing those bits which are not present in X, Y will become compliment of X. If Y<X then we'll pad Y with zeros.

I think this approach will work, feel free to point out any mistakes you find.

I thought on a funny solution to problem 2 and it ended up being O(N) after some optimization (which is what i think is the complexity you were aiming for).

I'll define 0 to be -1 instead so it will make calculations easier. Make an array V of size 2*n+1, where we will be storing all the the number of sequences that end on the index we're iterating and have a certain sum. Initially we will assume the point in that array that represents sum 0 to be n. Let's say we filled this array from the start of the string to i-1. Consider these two cases:

If S[i] = 1: it's like the "zero point" of the sequences from j to i-1 "went down", because we will be adding 1 to all other sufixes that come before it. In addition, we do on V[newzeropoint+1].

If S[i] = 0: like the previous case, it's like the "zero point" went up, and in addition to that V[newzeropoint+1]++.

At any given index we're iterating over the initial string the number of subsequences that end on that point is the sum of all V[i] such that i > zeropoint. We can do that in O(logn) with a fenwick tree (aka BIT) but we just need to mantain a variable storing this sum and update it as we're moving the zero point up and down for a O(n) solution

Approach for the 2nd question:

1.replace each 0 with -1

2.calculate prefix sum of newly formed array after replacement ( call this array pref)

3.now we have to find the number of sub-arrays who's sum is > 0.

4.let's say we have to find the sub-arrays ending at index j.

5.then sub-array [i,j] has +ve sum iff, pref[j] — pref[i-1] > 0 =>pref[j] > pref[i-1]

6.it means we have to find number of elements pref[i] which are smaller than pref[j] such that i < j.

8.for this (in python ) we use SortedList a special type of container which keeps the list sorted and upon binary searching elements we can get the number of elements < pref[j] .

9.as SortedList is a special type of container it won't be allowed in the online rounds, hence here is the link for the source code for it, https://ideone.com/RyMNKu

10.we will traverse from left to right and keep pushing elements into the SortedList and add answer for each index to our final answer.

link for the code I have solved using SortedList: https://mirror.codeforces.com/contest/1536/submission/122169458

I have no idea how to solve this in c++ ,as set/multiset returns pointer, how to convert it to index ?

problem 2

void solve(ll &tc)
{
    string s;
    cin >> s;

    ll n = s.length();
    ll ans = 0;
    for(ll i = 0; i < n; i++) {
        ll diff = 0;
        for(ll j = i; j < n; j++) {
            diff += (s[i] == '1' ? 1 : -1);
            ans += (diff > 0);
        }
    }
    cout << ans << endl;
}

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template <class key, class Comp = less<key>>
using pbds = tree<key, null_type, Comp, rb_tree_tag, tree_order_statistics_node_update>;

// order_of_key(k)    : number of elements strictly smaller than k
// find_by_order(ind) : iterator to set[ind]

void solve(ll &tc)
{
    string s;
    cin >> s;

    ll n = s.length();
    pbds<pair<ll, ll>> p;
    p.insert({0, 0});

    ll ans = 0, diff = 0, id = 0;
    for(ll i = 0; i < n; i++) {
        diff += (s[i] == '1' ? 1 : -1);
        p.insert({diff, id++});
        ans += p.order_of_key({diff, -1});
    }
    cout << ans << endl;
}

inline ll lsb(ll x) { // Least Significant Bit
    return (x & -x);
}

struct Fenwick
{
    ll n;
    vector<ll> bit;
    Fenwick(ll _n = 1e5) {
        n = _n;
        bit.assign(n + 5, 0);
    }
    void add(ll ind, ll val) // arr[ind] += val;
    {
        for(ll i = ind; i <= n; i += lsb(i)) {
            bit[i] += val;
        }
    }
    ll sum(ll ind) // prefix sum
    {
        ll ans = 0;
        for(ll i = ind; i > 0; i -= lsb(i)) {
            ans += bit[i];
        }
        return ans;
    }
};

void solve(ll &tc)
{
    string s;
    cin >> s;

    ll n = s.size();
    Fenwick f(2 * n + 5);

    ll offset = n + 1;
    ll ans = 0, diff = 0;
    f.add(offset, 1);

    for(ll i = 0; i < n; i++)
    {
        diff += (s[i] == '1' ? 1 : -1);
        f.add(diff + offset, 1);
        ans += f.sum(diff + offset - 1);
    }
    cout << ans << endl;
}

Does anybody have an idea how to solve Problem-1? (Considering the Trie solution is not very optimal in the worst case)

Best I could think is maintaining a set for each i from 1 to 32. If a number is having set bit at position 'i', then we add it to that set. Now to answer for query X, we check the set bit positions and take intersection of all those sets. But again, taking intersection might give TLE. Can this be improved or any other way to solve this?

I too got the same set.

I couldnt do 2nd one but I did 1st one For the first one I created an array of powers of 2 of length 20 and then for every element of this array I made sure whether it is in the keys array or not. Then for each query I traversed through the power of two's array and checked if that element exists in keys array and its and with the X = 0 then yes otherwise no.

PS: I had done 1st one partially...sorry for the mistake.

I think there exists an o(n) solution for the 2nd question, we convert all 0 to -1 and want to find all l < r such that pref[r] > pref[l],

so the optimization basically boils down to : given an array arr, can you find all l < r such that arr[l] < arr[r] in O(n), if abs(arr[i + 1] — arr[i]) == 1; and this seems possible if we store just two arrays what is the current prefix and what have we not updated yet.

For the first, read about SOS DP

Here and here is the soln for first one:

We can do second problem by using lazy propagation on array. In second problem we have to form an array which will intially have a[i] = (count of prefix having cnt(1)-cnt(0) >= i). At each index we have to find the value of a[(count(1)-count(0) + 1 upto i)] . After finding this value, we have to decrement a[min(count(1)-count(0))] upto a[(count(1)-count(0) upto i)] and since the difference between counts is changing by 1 we can apply lazy propagation. Note: count(1)-count(0) can be negative and we can handle it by sufficient positive offset. Time and space:O(n)

First problem can be done by graphs. We have to take values of a[i] as nodes and we have to add directed edge between two nodes such that the number of zeroes in binary representation of parent is 1 more than number of zeroes in binary representation of child node and all the indices having 0 in child nodeis subset of those in parent node. Then we have to create a flag array for occurence of each node value and then using bfs we will assign flag of child to be true if it is true or if any one of its parents is true. Complexity O(logn).

Let me know if there us any doubt

Since I found some coincidence with this blog so thought of sharing it. So recently, I have qualified for the Round2 of Google Girl Hackathon 2023 and to qualify for the further rounds, I had to appear for a Google Online Challenge on 25th June'23. Therein, I got two questions and the first question of my goc is exactly the second problem of this blog. I solved it using merge sort (NlogN) approach and it did pass all the testcases. Waiting for the results now :)