why bother writing when you have your own code library :p

yes, it is wrong. we can't set it 0 initially.

It should be "x = ~0U" in C++

We can initialize x as a[0] and then iterate from i=1 to n-1

ya it is a mistake in writing only...the code is correct

I set it to -1

Thanks so much! This was really helpful!

For those who want to learn about the function a bit more, this might help.

My Solution is almost the same as yours, except I just maintain two pointers $$$p1,p2$$$: $$$p1$$$ is the smallest index in the same component as $$$1$$$ in first forest but not in second forest; $$$p2$$$ is the smallest index in the same component as $$$1$$$ in second forest but not in first forest. Keep adding edges $$$(p1,p2)$$$ until no edges can be added.

May I put and translate this lovely solution in my blog?

I'll certainly leave the link.

Hey humbertoyusta, I din quite get how the stack part works... Could you pls explain it in detail ? i.e. how does taking all the elements in mocha's tree which does not belong to the same component as 1 and then randomly selecting a node from diana's forest which also dont belong to the same component as 1, works ? i.e. basically i believe even if we randomly permute the elements within each stack, it will work. Could you elaborate this part ?

"First, try to add all edges (1,x) for each x, after that, all nodes are in the component of node 1 in at least one of the two trees."

In the first graph: 1 -> 3 , 3 -> 2 and 4 is alone

In the second graph: 1 -> 4 , 4 -> 2 and 3 is alone

How would you deal with cycles?

ORZZZZZZZZ TONY

If there is a valid vertex to join, then after AND operation there must be several bits left. How did you know at what positions those bits are?

Sorry for trouble caused.

In problem D2, we think that the space complexity $$$O(n\log n)$$$ isn't that large when $$$n\le 10^5$$$. My submission only uses 26700KB and among all the testers the largest memory usage is 89200KB. So we just set a standard 256MB memory limit.

As for problem E, we didn't expect that it would be a trivial problem. That's why we say 'Sorry for my mistake in estimating the difficulty of problem D2 and E.' in the previous blog.

This is the Mobius function, your solution is exactly the same as the editorial.

cause AND can't be more than the number. so just AND all

Consider taking the test case as 11 7 14 3 7 here the answer will be 2

How about this test case:

3
7 4 3

suppose you have calculated dp[i][j] for 0<=j<=m

dp[i+1][j] = dp[i][j] + dp[i][j-1] .... dp[i][j-cap[i+1]];

here cap[i+1] is upper bound on variable i+1

suppose you have following task: given array $$$a$$$, and you want to do fast multiple times following action: increase value by $$$x$$$ all $$$a_i$$$ within range $$$[l, r]$$$. And after you did all those actions, you need to output resulting array $$$a$$$. This is what you need to do for this knapsack problem. dp[i][j] will store how many arrays of length $$$i$$$ have sum $$$j$$$. And, from array of length $$$i$$$ with sum $$$j$$$ you can do arrays of length $$$i+1$$$ with sums $$$[j+l, j+r]$$$. This range is where you need to add variants. And you increase them by same amount $$$dp[i][j]$$$. So, if you can increase values within range fast, you can solve this. Idea is that instead of actual values we will store array of deltas. To be precise, we will store certain array such that if you make prefix sums array from it, you'll get actual values of dp. For example, instead of storing 1,2,3,2 — values, we will store 1,1,1,-1 — deltas. Because we can calculate prefix sums array, and get 1,1+1,1+1+1,1+1+1-1 = 1,2,3,2. Now, if you increase single element of this array, prefix sums array will change all values in suffix. For example 1 2 1 -1 will give 1 3 4 3. So you can increase all values in suffix. Now you can increase within $$$[l, r]$$$ range by increasing value at $$$l$$$ so you'll increase within range $$$[l, \infty)$$$ and decrease value at $$$r+1$$$ so you'll also decrease within range $$$[r, \infty)$$$ which results into increase only within range $$$[l, r]$$$. Once all operations done, you calculate actual values by simply calculation of prefix sums, and use it as next dp[i].

What about B???

Another brute force solution is to try to color all segments of '?' using 'BRB' or 'RBR' and pick the one with the least cost. Implementation

We want to compute the number of arrays with gcd dividing $$$g$$$. Therefore, we are only allowed to have numbers $$$i\cdot g$$$, for $$$1 \le i \le \lfloor \frac{m}{g} \rfloor$$$. The sum of numbers in the array is also a multiple of $$$g$$$. From each range $$$[L, R]$$$ we are only allowed to have numbers $$$i \cdot g$$$, where $$$\lceil \frac{L}{g} \rceil \le i \le \lfloor \frac{R}{g} \rfloor$$$. Therefore, each segment $$$[L, R]$$$ can be transformed into a segment $$$[\lceil \frac{L}{g} \rceil, \lfloor \frac{R}{g} \rfloor ]$$$. Consider $$$knapsack[k][j]$$$ — the number of ways to get sum $$$j \cdot g$$$ from the first $$$k$$$ elements. When we add a new element $$$a_{i+1}$$$ with the possible range $$$[\lceil \frac{L}{g} \rceil, \lfloor \frac{R}{g} \rfloor ]$$$, we can see that the state $$$knapsack[i][j]$$$ contributes to states starting from $$$knapsack[i+1][j + \lceil \frac{L}{g} \rceil]$$$ and ending with the $$$knapsack[i+1][j + \lfloor \frac{R}{g} \rfloor]$$$, so we need to add value $$$knapsack[i][j]$$$ to some segment of $$$knapsack[i+1]$$$. We can do this with the difference array technique (see https://codeforces.me/blog/entry/88474?locale=en ). So we compute $$$knapsack[i+1]$$$ as a difference array, and then at the next step we compute prefix sums of this array to get the actual values of $$$knapsack[i+1]$$$ and proceed to computing $$$knapsack[i+2]$$$. Note that, as always, we can only store two layers. See my code for more details: https://codeforces.me/contest/1559/submission/126027569

Another approach for the knapsack DP part is to treat it as a problem of multiplying polynomials. For the case where we want sequences of gcd >= 1 the polynomial of the interval $$$[l_{i}, r_{i}]$$$ is $$$x^{l_{i}} + x^{l_{i}+1} + \ldots + x^{r_{i}}$$$. To get the number of sequences where the gcd>=1 and the sum <= m you multiply all these polynomials and sum the coefficients of the terms for powers <= $$$x^{m}$$$. You can try doing this with NTT but it's too slow. The key observation is $$$x^{l_{i}} + x^{l_{i}+1} + \ldots + x^{r_{i}} = \frac{x^{l_{i}}-x^{r_{i}+1}}{1-x}$$$ This means if you have the current polynomial $$$p(x)$$$ and you want multiply by the polynomial for $$$[l_{i}, r_{i}]$$$ you can do it in $$$O(m)$$$ by multiplying by $$$x^{l_{i}}-x^{r_{i}+1}$$$ then dividing by $$$1-x$$$. The case where you want gcd>=g is the same but you replace the interval $$$[l_{i}, r_{i}]$$$ with $$$[\lceil l_{i}/g \rceil, \lfloor r_{i}/g \rfloor]$$$ and $$$m$$$ with $$$\lfloor m/g \rfloor$$$. 126171468

You always have the option to connect two nodes if none of the two forests is a tree. The proof is in the tutorial:

So if you can't find two nodes to merge, that means you achieved the optimal answer.

Could you explain your solution a bit more? Obviously adding edges in u1 to u2/v2 i.e. across Diana's and Mocha's forest doesn't make sense.

////////////////////////////////////////
#include<bits/stdc++.h>              ///
using namespace std;                 ///
#define ll long long int             ///
#define ull unsigned long long int   ///
#define vell vector<ll>              ///
const ll MOD = 1e9 + 7;              ///
void init_io() {                     ///
ios_base::sync_with_stdio(false);    ///
cin.tie(nullptr);                    ///
}                                    ///
////////////////////////////////////////

const int N=2e5+10;
vector<int>graph1[N];
vector<int>graph2[N];
bool vis1[N];
bool vis2[N];


void dfs1(int vertex){
    vis1[vertex]=1;
    for(int child:graph1[vertex]){
        if(!vis1[child]) dfs1(child);
    }
}

void dfs2(int vertex){
    vis2[vertex]=1;
    for(int child:graph2[vertex]){
        if(!vis2[child]) dfs2(child);
    }
}

void invictus(){

    ll n,e1,e2;
    cin>>n>>e1>>e2;
    for(int i=0;i<e1;i++){
        ll v,u;
        cin>>v>>u;
        graph1[v].push_back(u);
        graph1[u].push_back(v);
    }
    for(int i=0;i<e2;i++){
        ll v,u;
        cin>>v>>u;
        graph2[v].push_back(u);
        graph2[u].push_back(v);
    }

    dfs1(1);dfs2(1);
    vector<pair<ll,ll>> ans;
    for(int i=1;i<=n;i++){
        if(vis1[i]==0 && vis2[i]==0){
            dfs1(i),dfs2(i);
            ans.push_back({1,i});
        }
    }

    set<ll>un,co;

    for(int i=1;i<=n;i++){
        if(vis1[i]==0 && vis2[i]==1) un.insert(i);
        if(vis1[i]==1 && vis2[i]==0) co.insert(i);
    }
    auto it1=un.begin();
    auto it2=co.begin();

    while(it1!=un.end() && it2!=co.end()){
        ll x=*it1,y=*it2;
        ans.push_back({x,y});
        it1++;
        it2++;
    }

    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++) cout<<ans[i].first<<" "<<ans[i].second<<endl;
}

////////////////////////////////////////
int main(){                          ///
init_io();                           ///
// ll t;cin>>t;                      ///
// while(t--) 
invictus();                          ///
}                                    ///
////////////////////////////////////////

this is my solution for problem D

1) i'm doing dfs starting with the vertex 1 and marking the visited nodes (doing this for both the forest).

2) then i'm checking vertex which is not visited in both the forest then im doing dfs for that vertex in both forest and adding an edge between that vertex and 1.

3) last step im cheking for vertex which is visited in one of the forest and not visited in another forest for ex:- 5 is having edge in forest 1 and not in forest 2, 7 is having edge in forest 2 and not in forest 1 so i will add a edge between them

idk what's wrong in this logic please check the code

I think , in a row there can be at most n elements to merge, and each element is merged logn times max, as rows are merged by size (DSU by rank logic) and logn to insert in set each time. so for 1 element (logn)^2 , for n elements n*(logn)^2.

To detect whether connecting two vertices is possible (there will be no cycle after connection) we can use DSU (disjoint set union, tutorial). Now we assume that for each vertex A and B we know whether we can connect them or not. Just try to brutforce all pairs of vectices. If connection of two vectices in both forests wouldn`t create a cycle add new edge. Example of code: 126156817. Hope this will help you. Good luck :)

d is a divisor of $$$gcd(a_1,a_2,...,a_n)$$$, so d is also a divisor of $$$a_1$$$ and $$$a_2$$$ ...

s[i]=s[i-1]^('B'^'R') basically turns s[i] depending upon the value of s[i-1]. If s[i-1] is 'B', s[i] changes to 'R' and if s[i-1] is 'R', s[i] changes to 'B'.

'B', 'R' in C++ is number equal to ASCII code of symbol. It basically means that char is also integer in C++, it just has fewer bytes and narrow range. You should also know that (x^y)^z = x^(y^z). This is basic property of XOR. It's easy to prove by considering bits separately. Then, feed 'B' into formula you get 'B'^('B'^'R') = ('B'^'B')^'R' = 0^'R' = 'R'. Also, you should know that x^y = y^x, so if you feed 'R' into formula you get 'R'^('B'^'R') = ('B'^'R')^'R' = 'B'^('R'^'R')='B'^0='B'

DSU doesn't work like this. If you want to join two sets that have nodes $$$i$$$ and $$$j$$$, you have to find the leaders (roots) of each set and update their parents, not for $$$i$$$ and $$$j$$$.

Just use it as it is, it makes input/output operations faster, which results in faster runtime. Just use it without knowing what is it(abstraction) and believing it does ur job!!