CRINGEQUERY Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Practice

Setter: Dinmukhamed Tursynbay
Testers: Takuki Kurokawa and Nishank Suresh
Editorialist: Utkarsh Gupta

DIFFICULTY

2855

PREREQUISITES

XOR, Graph, Combinatorics

PROBLEM

You are given an array A of N integers, initially all zero.

There are Q types of operations that you are allowed to perform. Each operation is described by two integers l_i and r_i (1 \leq l_i \leq r_i \leq N) and is as follows:

  • Set A_j = A_j \oplus 1 for each j such that l_i \leq j \leq r_i.

Here \oplus represents the Bitwise XOR operator.

Your task is to find the number of distinct arrays which can be obtained by applying some subset of these operations (possibly none, possibly all). Since the answer may be huge, output it modulo 998244353.

EXPLANATION

Prepend A_0 = 0 and A_{N+1} = 0 to the array A.
Let us construct another array B of length N+1 such that B_i = A_i \oplus A_{i+1}.
We can see that after applying any query [L, R] exactly 2 values in the array B (B_{L-1} and B_R) will change. So for each query [L, R] we will add an edge between the nodes L-1 and R as values of both B_{L-1} and B_R will get changed after this operation.

There might be more than one components in the graph. It is easy to see that each component is different since the nodes concerned will be disjoint. So we will compute answer for all the components individually and multiply them to obtain the final answer.

Calculating Answer for one component

Consider a cycle in the component. If we apply operation on all the edges of a cycle then it will reset the values of all the nodes involved in the cycle. So we can remove the edges involved in the cycle and obtain a spanning tree. Now we can see the each edge is independent (i.e. changing the state of any edge will give us a new array). Let the number of nodes in the component be X. So there will be total X-1 edges (Since we have obtained a tree). So the answer for this component will be 2^{X-1}. We can multiply the answers for each components to get our final answer.

TIME COMPLEXITY

O(N+Q) for every test case

SOLUTIONS

Setter's Solution

# include <bits/stdc++.h>

# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
 
template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define debug(x) cerr << #x << " = " << x << endl
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());

int rnd (int l, int r) {
    return uniform_int_distribution<int> (l, r)(gen);
}
const int N = 1e6+5;
const int mod = 998244353;
int n, q;
vector <int > g[N];
int used[N];
int comp_size;

int mult(int a, int b) {
    return a * (ll) b % mod;
}

int bpow(int a, int b) {
    int res = 1;
    while(b > 0) {
        if(b & 1) res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }

    return res;
}

void dfs(int v) {
    if(used[v])
        return;
    used[v] = 1;
    ++comp_size;
    // visiting new node

    for (auto to : g[v]) {
        dfs(to);
    }
}

void solve() {
    cin >> n >> q;
    for (int i = 1; i <= q; ++i) {
        int l, r;
        cin >> l >> r;
        g[--l].pb(r);
        g[r].pb(l);
    }
    int ans = 1;
    for (int i = 0; i <= n; ++i) {
        if(used[i])
            continue;
        comp_size = 0;
        dfs(i);
        ans = mult(ans, bpow(2, comp_size - 1));
    }
    cout << ans << '\n';
}


int32_t main () {
    SpeedForce;

    int TestCases = 1;
    //cin >> TestCases;

    for (int TestCase = 1; TestCase <= TestCases; ++TestCase) {
        //cout << "Case #" << TestCase << ": ";

        solve();
    }

    return 0;
}

// B...a

Tester's Solution 1
#include <bits/stdc++.h>
using namespace std;

struct dsu {
   public:
    dsu() : _n(0) {}
    dsu(int n) : _n(n), parent_or_size(n, -1) {}

    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }

    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                           [&](const std::vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }

   private:
    int _n;
    std::vector<int> parent_or_size;
};

int main() {
    int n, q;
    cin >> n >> q;
    dsu d(n + 1);
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        d.merge(l - 1, r);
    }
    const long long mod = 998244353;
    vector<long long> fact(n + 2), inv(n + 2), inv_fact(n + 2);
    fact[0] = inv[0] = inv_fact[0] = 1;
    fact[1] = inv[1] = inv_fact[1] = 1;
    for (int i = 2; i < n + 2; i++) {
        fact[i] = fact[i - 1] * i % mod;
        inv[i] = (mod - inv[mod % i] * (mod / i) % mod) % mod;
        inv_fact[i] = inv_fact[i - 1] * inv[i] % mod;
    }
    auto C = [&](int i, int j) {
        return fact[i] * inv_fact[j] % mod * inv_fact[i - j] % mod;
    };
    long long ans = 1;
    for (int i = 0; i < n + 1; i++) {
        if (d.leader(i) == i) {
            int sz = d.size(i);
            long long ways = 0;
            for (int j = 0; j <= sz; j += 2) {
                ways += C(sz, j);
                ways %= mod;
            }
            ans *= ways;
            ans %= mod;
        }
    }
    cout << ans << endl;
    return 0;
}
Tester's Solution 2
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

/**
 * Disjoint Set
 * Source: Adapted from Aeren and Atcoder Library
 * Description: Data structure to keep a collection of disjoint sets which contain the elements {0, 1, ..., n-1}
 *              Implements both path compression and union by size
 * Methods:
 * (1) int get_root(int u): Find a representative of the set containing u
 * (2) int size(int u): Returns the size of the set containing u
 * (3) bool same_set(int u, int v): Check whether u and v are in the same set
 * (4) bool merge(int u, int v): Merge the sets containing u and v if they are different, returns success of merge
 * (5) vector group_up(): Returns the collection of disjoint sets as a vector of vectors
 * 
 * Time: Amortized O(n alpha(n)) for n operations
 * Space: O(n)
 * Tested on Codeforces EDU
 */

struct DSU {
private:
	std::vector<int> parent_or_size;
public:
	DSU(int n = 1): parent_or_size(n, -1) {}
	int get_root(int u) {
		if (parent_or_size[u] < 0) return u;
		return parent_or_size[u] = get_root(parent_or_size[u]);
	}
	int size(int u) { return -parent_or_size[get_root(u)]; }
	bool same_set(int u, int v) {return get_root(u) == get_root(v); }
	bool merge(int u, int v) {
		u = get_root(u), v = get_root(v);
		if (u == v) return false;
		if (parent_or_size[u] > parent_or_size[v]) std::swap(u, v);
		parent_or_size[u] += parent_or_size[v];
		parent_or_size[v] = u;
		return true;
	}
	std::vector<std::vector<int>> group_up() {
		int n = parent_or_size.size();
		std::vector<std::vector<int>> groups(n);
		for (int i = 0; i < n; ++i) {
			groups[get_root(i)].push_back(i);
		}
		groups.erase(std::remove_if(groups.begin(), groups.end(), [&](auto &s) { return s.empty(); }), groups.end());
		return groups;
	}
};

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	int n, q; cin >> n >> q;
	DSU D(n+1);
	int comps = n+1;
	for (int i = 0; i < q; ++i) {
		int L, R; cin >> L >> R;
		comps -= D.merge(--L, R);
	}
	int ans = 1, mod = 998244353;
	comps = n+1-comps;
	for (int i = 0; i < comps; ++i) {
		ans *= 2;
		ans %= mod;
	}
	cout << ans;
}
Editorialist's Solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 998244353
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=1000023;
bool vis[N];
vector <int> adj[N];
int cnt=0;
void dfs(int curr)
{
	vis[curr]=1;
	cnt++;
	for(auto it:adj[curr])
	{
		if(vis[it])
			continue;
		dfs(it);
	}
}
void solve()
{
    int n,q;
    cin>>n>>q;
    ll ans=1;
    while(q--)
    {
    	int l,r;
    	cin>>l>>r;
    	adj[l-1].pb(r);
    	adj[r].pb(l-1);
    }
    for(int i=0;i<=n;i++)
    {
    	if(vis[i])
    		continue;
    	cnt=0;
    	dfs(i);
    	ans*=power(2,cnt-1);
    	ans%=mod;
    }
    cout<<ans<<'\n';
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int T=1;
    //cin>>T;
    while(T--)
        solve();
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

1 Like

I have a few doubts:
Doubt1:

There are ways to choose the edges we want to include in the tree. So I think it should be 2^{X}-1. For X = 3 with a complete cycle, I am getting 7 different trees.

Doubt 2: In the editorial , you have got answer for component which is a cycle. However when it has multiple cycles, I think we should subtract the number of cycles from cnt

How does operation on array B equivalent to operation on A ? and why do we make array B ?

Let me first answer doubt 2 which will help me answering doubt 1.

Lets think that in a component initially all the nodes are black. Now if you choose any edge, you will flip the color of nodes connected through that edge. Then what is the number of colorings you can obtain.

Doubt 2: I am claiming that whenever you select any edge which forms a cycle with the previous selected edges then you can say that colors of all the nodes have reset. So you may infer that the edge which formed cycle is useless and will not increase the counting. Thus my claim is that you can remove all the back edges in the component and then deal with the spanning tree.

Doubt 1: Let us consider the example you have given.
There are 3 nodes and they form a cycle. All the nodes are initially black. What is the number of colorings you can obtain.
The colorings I can see are:
BBB
BWW
WWB
WBW
How did you obtained 7 colorings?

Hope your doubts are cleared

1 Like

If you are given array A, you can easily obtain array B.
If you are given array B, you can easily obtain array A.
So both these arrays are equivalent. So counting the number of arrays A we will instead count the number of arrays B and still our answer will be same

thanks

I want to ask is this concept somewhat standard . I have not seen this thing in any problem . I meant to say if there are any resources for this because changing the array and coming up with this idea is really difficult .

Or if you can suggest me the name of this approach , I can google it and can search for some problems u der this concept

I came to know after the contest that this technique has appeared before.

Although in these type of ques where a range is affected, I generally to transform the array such that very few elements after affected. Generally prefix xors/sums works. In these problem the transformation was a bit different. I don’t know if this technique is popular or not. It mainly comes with practice I think

I guess in order to solve this problem you don’t really need to have an exact idea of the transformation from A to B, you just need to understand that only two parts of the array will really matter for each query. Also, is there a meaning behind the name “Cringe Queries”?

Hi all,
Im new in the competitions , just started out.
Can i have a more detailed solution as Im not able to get this.