It is dp but you need root changing dp.

Yes. I solved it by the same solution too. I think it is more natural.

me too. was much more intuitive to build the sequence and it's also in 2N operations! Just move the already built sequence 1...i to the end by choosing the the one right after, then choose i+1.

I think people forced swaps because swaps is the basic function of all permutations so they immediately look in that directions. also many problems are solved using this mindset and building swap from given operations.

Failed system testing

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, a[300000], b[300000], ans, T;
void init(){
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	b[n + 1] = 0;
	for(int i = n; i >= 1; i--){
		b[i] = b[i + 1] + max(a[i], 0ll);
	}
	ans = 0;
	for(int i = 1; i <= n; i++){
		if(i & 1) ans = max(ans, b[i + 1] + a[i]);
		else ans = max(ans, b[i + 1]);
	}
	cout << ans << endl;
	return ;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> T;
	while(T--){
		init();
	}
	return 0;
}

// Intial DP States for the last index
dp[n][1] = max(a[n], 0LL);
dp[n][0] = 0LL;

// To avoid negative takes, we max it with 0
ll ans = max(0LL, dp[n][n & 1]);

// At every index, we will be computing optimal values for both odd and even cases
for (int i = n - 1; i >= 1; i--) {
	// Optimal Value for even index
    dp[i][0] = max(dp[i+1][0], dp[i+1][1]);
	// Optimal Value for odd index
    dp[i][1] = max(dp[i+1][0] + max(0LL, a[i]), dp[i+1][1] + a[i]);
    
    // dp [i][i&1] is the optimal value that can be taken 
    // for that index, with its current parity
    ans = max(ans, dp[i][i & 1]);
}
cout << ans << '\n';

credits: kriepiekrollie

Let us assume we have two certain cards $$$a$$$ and $$$b$$$, where WLOG $$$a$$$ comes before $$$b$$$. If we use $$$b$$$ before $$$a$$$, the parity of the indices are preserved. However, if we use $$$a$$$ before $$$b$$$, the parity of the index on $$$b$$$ changes. The key insight is that, generalizing this to more than two cards, we can choose any card's parity of index as long as we want to. (Of course, the first card chosen is an exception, but we'll get to that in a sec)

Now define $$$dp[i][\text{change parity?}]$$$ as the maximum value of the three cases —

• You choose the $$$i$$$-th card, while changing its parity of index.
• You choose the $$$i$$$-th card, without changing its parity of index.
• You do not choose the $$$i$$$-th card.

Now, if we define $$$dp[0][0]=0$$$ and $$$dp[0][1]=-\infty$$$, the case of changing the first card's parity is automagically cleared out. This is because when you try to change the first card's parity, it is evaluated as $$$-\infty + c = -\infty$$$.

Here you can see the code based on the approach. 225166689

Since 1 <= i <= 50, you can Bruteforce the solution. First, you take count of all i's in a map. Then for each i, you decrease the count of all element from every set that has i in it. Maximum of remaining map size will be your answer.

What we are doing here is, we are deleting every i from set S which is union of all set. Our target is to maximize the result that's why we try to delete only one i. But you cannot delete a single i if the original set size was greater than 1. You need to delete all the values of that set. Since other set can have the same values you just deleted, you need to decrease the count instead of deleting. I hope this makes sense.

Acc. to the problem statement, we know that ATLEAST one element will not belong to our attainable sets.

Now, as there's only 50 possible elements, We can check for each number/element (in the global set), to see what would be the maximum size of our attainable set that we can achieve by excluding it.

We can easily do this by appending every exclusive set of that number into a temp set, and compute the size of that attainable set.

The maximum upon all of these would give us the max possible attainable set.

This would be the crux:

int ans = 0;
    for (auto x : global_set)
    {
        set<int> temp;
        for (int i = 0; i < n; i++)
        {
            // Not found in the set
            if (v[i].find(x) == v[i].end())
            { // we can take this set
                temp.insert(v[i].begin(), v[i].end());
            }
        }
        ans = max(ans, (int)temp.size());
    }

    cout << ans << endl;

You can also make sense of the global map approach above, if that is more intuitive to you, but the outline is to brute-force for each element.

Bro the first number in all the sets represent 'k' which is the number of integers each set have. Here 2 represents value of k.

If they have the same parity of the number of operations just do 1 and n on the smaller sequence of operations until its length reaches the bigger one. Otherwise they have different parity. If both permutations have even length answer is -1. Otherwise WLOG permutation a has odd length, then just do operation 1 for n times. Now parities are the same and we know how to solve that.

If the difference of number of operations is even you can just type 1 and n or m the times you need depending on which one is less. If the difference is odd, you can make it even if n or m are odd, you just type 1 the size of the array times till it goes back to be sorted.

I'm also trying to understand, but essentially, you add the $$$X$$$ at the beginning of the array. Now, your array will be $$$X$$$ $$$p_1$$$ $$$p_2$$$ ... $$$p_n$$$. If you do an operation on an array $$$X$$$ $$$A$$$ $$$b$$$ $$$C$$$, where b is the pivot and A and C are the two subarrays, the array becomes $$$X$$$ $$$C$$$ $$$b$$$ $$$A$$$. At the moment, $$$X$$$ stays in place, because it's just an artificial element at the start of the array.

Now, the main trick is that you consider this array as a circular array. Here, $$$X$$$ tells you the start of the array, so if you start reading the array from the X, you will get the original array. Because the array is circular, the array $$$X$$$ $$$p_1$$$ $$$p_2$$$ ... $$$p_n$$$ is equivalent to every other rotation of the array (i.e. [ $$$p_n$$$ $$$X$$$ $$$p_1$$$ $$$p_2$$$ ... $$$p_{n-1}$$$]; [ $$$p_{n-1}$$$ $$$p_n$$$ $$$X$$$ $$$p_1$$$ $$$p_2$$$ ... $$$p_{n-2}$$$] ; ...; [ $$$p_1$$$ $$$p_2$$$ ... $$$p_n$$$ $$$X$$$ ] ).

Therefore, $$$X$$$ $$$C$$$ $$$b$$$ $$$A$$$ is equivalent to $$$b$$$ $$$A$$$ $$$X$$$ $$$C$$$. So, from $$$X$$$ $$$A$$$ $$$b$$$ $$$C$$$, the operation transforms it into $$$b$$$ $$$A$$$ $$$X$$$ $$$C$$$. Essentially, what this operation does is that it swaps $$$X$$$ with any other element.

So, we will start with the array $$$X$$$ $$$p_1$$$ $$$p_2$$$ ... $$$p_n$$$ (just the initial array) and then perform swaps with $$$X$$$ and other elements so that we reach the sorted array, which is $$$X$$$ $$$1$$$ $$$2$$$ ... $$$n$$$. Since both the starting and ending arrays are so far considered circular arrays, we will stop doing so and do it on a simple array. As a consequence, the possible "target" arrays are [ $$$X$$$ $$$1$$$ $$$2$$$ ... $$$n$$$ ] , [ $$$n$$$ $$$X$$$ $$$1$$$ $$$2$$$ ... $$$n-1$$$ ], [ $$$n-1$$$ $$$n$$$ $$$X$$$ $$$1$$$ $$$2$$$ ... $$$n-2$$$ ] , ..., [ $$$1$$$ $$$2$$$ ... $$$n$$$ $$$X$$$ ]. We will try to find a sequence of operations for every of the possible "target" arrays.

So now we must solve the following problem: we have the array $$$X$$$ $$$p_1$$$ $$$p_2$$$ ... $$$p_n$$$, with an operation, we swap element $$$X$$$ with some other element, and we want to reach some other permutation (in particular, one of the above "target" arrays). I will replace $$$X$$$ with $$$0$$$, so that we have a 0-indexed permutation of length $$$n + 1$$$. So, given $$$0$$$ $$$p_1$$$ $$$p_2$$$ ... $$$p_n$$$, we want to transform it into another target permutation. To do so, you decompose this permutation into cycles (i.e. see where $$$0$$$ has to go, the element on that position where to go, and so on). You will use $$$0$$$ as some sort of buffer. You will swap $$$0$$$ with the element that has to go in its position, and you will do that until $$$0$$$'s cycle is solved. This will take $$$len - 1$$$ moves (each move solves an element, except the last one, which will put $$$0$$$ in its correct position and the element that has to go in $$$0$$$'s position, thus solving two elements at the same time). To solve the other cycles in the permutation, you swap $$$0$$$ with some other element in the cycle that you want to solve ("break into the cycle"), and then you do the same thing as above. Swap $$$0$$$ with the element that has to go in $$$0$$$'s position. For this cycle, you use $$$1 + len$$$ swaps (first swap breaks into the cycle, the next $$$len$$$ swaps will solve each element in the cycle). Hence, you get the formula from the editorial: (sum of (size + 1) for cycles which have size ≥ 2 and don't contain X) + (X's cycle size − 1). Keep in mind, elements that are already solved which will form cycles of length 1 will be ignored.

So, you can find out the minimum number of swaps between $$$X$$$ $$$p_1$$$ $$$p_2$$$ ... $$$p_n$$$ to any other array. In particular, you want to find the minimum number of swaps from the beginning permutation to every rotation of $$$X$$$ $$$1$$$ $$$2$$$ ... $$$n$$$. So you have a new array which gives you for each target rotation the minimum number of operations. You find the minimum even number and the minimum odd number. Everything I said above was for only one permutation, but you have two permutations in the input, so you do everything for both permutations. Take the minimum from the answers with the same parity (i.e. minimum odd number of operations for the first permutation and minimum odd number of operations for the second permutation, and the same for evens) and this is your answer. If you combine two solutions, let's say that they have size $$$n$$$ and $$$m$$$, the number of operations used is $$$max(n, m)$$$. If you have a solution of size $$$n$$$, you can extend it to have size $$$n + 2$$$ (swap X with some element and do that swap again, to do nothing in two operations). You use this to pad one of the arrays with useless operations so that the two solutions have the same size.

TLDR:

• you consider the starting array as a circular array and prepend it with some extra character $$$X$$$ that represents the start of the array;
• an operations swaps $$$X$$$ with some other element;
• you can stop considering the array as a circular array from this point, but you have an extra element;
• you want to transform the starting array in another array that is a rotation of $$$X$$$ $$$1$$$ $$$2$$$ $$$3$$$ ... $$$n$$$;
• to transform a starting permutation to a target permutation, you decompose it into cycles and swap the elements around to solve the permutation;
• you find the minimum number of operations to transform the starting array to every rotation of the target array; take the minimum odd number and the minimum even number;
• to combine the two permutation in the input, combine odds with odds and evens with evens; to have two sequences of swaps of same length, pad one with pairs of operations that do nothing;

Suprisingly, we could make the parity equal with only 1 operation, which is used in the "challenge" of E2.(n=100k, query limit 150k)

The number of operations in a single permutation required is,

(sum of (size + 1) for cycles without X and size >= 2) + (X's cycle size — 1).

This value is at most 1.5n in a permutation of length n.

However, if we do this with both permutations, and the parity of them are different, we should equal the parity. Surprisingly this can be done in only 1 operation (think why :))

Input:
1
2
2 2

Your Output:
4

Correct Output:
3

If $$$a = [2, 2]$$$, we can make $$$b = [1, 3]$$$.