Your first upvote!!

Thank you for the interesting problem :)

Excuse Me, where are problems? Would You send link? before thanks)

Can I get a hints about how to calculate the Wael-uty of two unordered integers (X, Y) fast? Thank you for the interesting problem?

The problem is GREAT but it's really hard to understand

upvote!!

Let's Reverse the permutation we note that the first $$$j$$$ such that all elements between $$$[1;j]$$$ exists in this prefix form a connected component this is easy to prove and you can find it out from doing some trials as well.

So you just need to count the number of such $$$j$$$. This can be translated to the following problem: Count the number of prefixes such that $$$\sum_{i=1}^{j} i-p_i == 0$$$, Note that this sum will always be non-negative which translate it to this

Thnx.

Can you post your solutions on pastebin for all problems please? I am curios about some of them.

for the first test case the possible permutations are: all permutations

for the second test case the possible permutations are: all permutations

for the third test case the possible permutations are: [1,3,2],[2,3,1], [1,2,3]

You build a union find data structure with time , where you save the update time for every node and the corrosponding id and answer for that time. you have for example for node 2 has been updated at times 3, 6 , 7 you will have the following update_time[2]={0,3,6,7}, id[2]={2,2,2,5}, now to get the id for u and time t , you search for the biggest update time for u <= t and see , if it's equal to u then it's the id of the component otherwise recursively search on it's id like a simple DSU. , for the merge operation you keep set for every component , and save current ans for every component, you merge the small one into the big one, lets consider big is the big set and small is the small set, now we iterate over the items of the small set , let's say u is the current value we want to insert, if u is already in big continue, if u+1 and u-1 are in big the we decrease the ans by 1 (we merged them together) , if u+1 and u-1 not in big we increase the answer by 1 (a new component) and then we insert u into big and we continue iterating. Here is my code : link

First you need to notice that every value should exist at most 2 times . If a value exist only 1 time it doesn't matter where it should be A or B, If a value exists 2 times then you there are 3 cases : if the 2 poisitions of that values are the same it means there is i such that a[i]=b[i]=value then it doesn't matter we swap those or not so we skip. if we have now 2 positions i,j such that ai=V, bi=x and aj=V,bj=y then we need one of them to be swapped and the other no , se we will construct a graph with nodes are indices and edge weight =1 between i and j in this case.

if we have now 2 positions i,j such that ai=V, bi=x and aj=y ,bj=V then we need if one is swapped then the other one should be swapped too. then we add to the graph an edges between i and j with weight 0.

So we will build a graph with edges with weights 1 or 0 and see if we can color the graph with 2 colors such that edge with weight 0 means both end should have same solor and edge with weight 1 means both ends should have different colors. => bipartite graph

And for the answer just get the minimum size of color_0, color_1 for each connected compoenent and sum them .