Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### windva's blog

By windva, history, 2 months ago, 1882A - Increasing Sequence

Tutorial

1882B - Sets and Union

Something to say
Hint 1
Hint 2
Tutorial

1882C - Card Game

Hint 1
Tutorial

1882D - Tree XOR

Hint 1
Hint 2
Hint 3
Tutorial

1882E1 - Two Permutations (Easy Version)

Hint 1
Hint 2
Hint 3
Hint 4
Tutorial

1882E2 - Two Permutations (Hard Version)

Special thanks to kizen providing an key idea which motivated me to make this problem!

Hint 1
Hint 2
Hint 3
Tutorial
Challenge Tutorial of Codeforces Round 899 (Div. 2) Comments (61)
 » Just opened codeforces and found this tutorial. Lucky xD.
 » I tried to solve D by DP,but actually it's dfs :( Are there any useful tips to distinguish them?
•  » » It is dp but you need root changing dp.
•  » » » Oh,yeah,I didn't totally understand the code I saw.thx.
 » 2 months ago, # | ← Rev. 3 →   Regarding E1, could anyone share a little about how to come up with the observation "any 2 positions can be swapped in 3 operations"? It seems unnatural to me, orz.Alternatively, I solve E1 by gradually forming the contiguous segments i,i+1,...,n for i from n to 1.
•  » » 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.
 » Where is first solve data?
 » E2 is brilliant.
 » 2 months ago, # | ← Rev. 2 →   What is FSTs?
•  » » Failed system testing
 » E2 is amazing!
 » Can anybody explain me the DP solution for C in an easy way?!
•  » » 2 months ago, # ^ | ← Rev. 3 →   #include #define int long long using namespace std; int n, a, b, 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] = max(a[n], 0LL); dp[n] = 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] = max(dp[i+1], dp[i+1]); // Optimal Value for odd index dp[i] = max(dp[i+1] + max(0LL, a[i]), dp[i+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
•  » » » why dp[n] and dp[n] are like that ? what dp[i][j] in general means and how do you got the intuition behind considering 2D dp ? can it be reduced to 1D dp also ?kriepiekrollie
•  » » » » $\textrm{dp}[i]$ is the answer if we only consider the suffix $a_i, a_{i+1}, \dots a_n$, and we consider $i$ to be an "even index".$\textrm{dp}[i]$ is the answer if we only consider the suffix $a_i, a_{i+1}, \dots a_n$, and we consider $i$ to be an "odd index".Thus we print the maximal value of $\textrm{dp}[i][i\%2]$ over all $i$.
•  » » » » This problem isn't actually dp, but I only realized that after the contest ended and I'd already submitted this code...
•  » » » » » got it now thanks for the help.
•  » » » » 1D DP Lol...
•  » » » » » what that dp[i] represents and transition state?
•  » » » » » » its the answer for a[i.....n] subarray.
•  » » 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$ and $dp=-\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
 » Can someone explain problem B solution I still don't know why that work
•  » » 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 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.
•  » » » thank you guys that really help
 » 2 months ago, # | ← Rev. 4 →   Recursive DP solution for Problem C int recur(int i, int parity, vector &a, vector> &dp) { if (i >= a.size()) return 0; int &ans = dp[i][parity]; if (ans != -1) return ans; ans = recur(i + 1, parity, a, dp); if ((i % 2) == parity) { ans = max(ans, a[i] + recur(i + 1, parity ^ 1, a, dp)); ans = max(ans, a[i] + recur(i + 2, parity, a, dp)); } else ans = max(ans, recur(i + 1, parity ^ 1, a, dp)); return ans; } 
 » Could someone please help me understand problem B? Specifically, in example test case 3, if I take the union of all sets besides S4 = {2, 1, 3}, I get S = {1, 3, 5, 6, 8, 9, 10}, which is not equal to the union of all sets as 2 is not included. But the answer to the problem is 6, and not 7.What am I missing?
•  » » 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.
•  » » » Haha damn, I had a feeling it was something simple like that. Thanks!
•  » » » Thank you! I was not understanding that either...
 » Why there is no code in editorial nowadays ?
 » Can anyone tell me how E1?I know how to sort the $2$ arrays, but not understanding how to make the number of operations the same.
•  » » 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.
 » 2 months ago, # | ← Rev. 4 →   In Problem C, if ever you can only choose it from a_1 or a_2 the first value which is picked, there are optimal solutions. It is a funny property and here is a simple solution using this fact: ll S = max(a, 0LL) if(n > 1) S = max(S, a + a); for(int i=2;i 0) S += a[i]; cout << S << "\n"; 
 » Alternative Solution for C 1.First of all you only need to care about first two index.lets see how....there are only four possibility for these two index..either both pos ,both neg, first is pos second is neg, and first is neg second is pos...lets deal with all of them one by one but before that i am assuming that we have picked all the pos numbers which are at odd pos after 2nd index and there are only pos elements left at even index(after 2nd index)...now for the first case when both are neg we can always remove 2nd index neg and now all the even index pos after that comes at odd index so we can add the rest of pos....same goes for the second case when both are pos,you can pick first index and now all the rest pos....in the case of first pos and second neg...remove second index element(neg number) and now all the pos are at odd index....for the last case first is neg and second is pos,one thing is to notice that if you have to remove atleast one pos number to get the pos after it(because then they come at odd pos) now which pos to choose...obviously removing the 2nd index pos number is always favourable as now we can always add all the pos numbers after it...so what we observe that we will always take all the pos numbers after 2nd index and for these two elements we can check locally...see my submission 225272412.Thanks for reading upto here.
 » in E2 , I couldnt understand what editorial was trying to say , would greatly appreaciate it if you could explain it in a simpler manner
•  » » 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;
•  » » » 2 months ago, # ^ | ← Rev. 4 →   Could you tell me how to demonstrate that we can certainly get both even and odd answers.What if we can only get an minimum even answer but there're minimum ansers with both parities?
•  » » » » In general, there can't be both even sequence of swaps and odd sequence of swaps that turns the permutation to same other permutation, since each swap changes the parity of inversion number (this is well-known).Therefore, if the minimum number of swaps required to turn $[X p_{1} \cdots p_{n}]$ into the array required is even, then there can't be the odd number of swaps that turns $[X p_{1} \cdots p_{n}]$ into the array.So if there is no minimum odd number, then there is no any odd answer.Furthermore, for reference, if $n$ is odd, then the parity of number of operations required changes everytime when we shift the goal array once. Specifically, parity of number of number of operations required to turn $[X\,p_{1}\,p_{2}\, p_{3}\,p_{4}\,p_{5}]$ into $[X\,1\,2\, 3 \,4 \,5]$, $[2 \,3\, 4 \,5\, X\, 1]$, $[4 \,5\, X \,1 \,2 \,3]$ are equal, and $[1\,2\,3\,4\,5\,X]$, $[3\,4\,5\,X\,1\,2]$, $[5\,X\,1\,2\,3\,4]$ are equal(and these are different). This is because one shift can be obtained by $n$ swaps, $n$ is odd, and each swap changes the parity of number of cycles, and the number of operations is equal with $n$ + (number of cycles) in mod 2.Similarly, if $n$ is even, all parity are same.
•  » » » that is some great simple yet intuitive explanation , thanks !
 » For E1, I randomly did some operations on both arrays if the parity of the answer was different, and it got accepted.
•  » » Suprisingly, we could make the parity equal with only 1 operation, which is used in the "challenge" of E2.(n=100k, query limit 150k)
 » How to solve the challenge with E? Can anyone give some tips? Thanks
•  » » 2 months ago, # ^ | ← Rev. 2 →   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 :))
 » 2 months ago, # | ← Rev. 8 →   I'm curious to know if anyone did this approach solving the problem A ??, because it keeps failing for me for some case, even though I tested it in with a lot of cases: n = int(input()) tests = []     def no_one_repeat(array1, array2):     for a, b in zip(array1, array2):         if a == b:             return False     return True     for x in range(n):     _ = input()     tests.append(list(map(int, input().split())))   for test in tests:     suppose_min = len(test)     done = False     while not done:         array = [suppose_min — i for i in reversed(range(len(test)))]         if no_one_repeat(test, array):             print(suppose_min)             done = True         suppose_min += 1 
•  » » Input: 1 2 2 2 Your Output: 4 Correct Output: 3 If $a = [2, 2]$, we can make $b = [1, 3]$.
•  » » » Got you, thanks a lot.Can you tell me how you noticed the problem in code and came up with a test to prove it?I want to improve my CP skills, thanks!
•  » » » » You're only trying arrays of type $x, x + 1, x + 2, ..., x + n - 1$, so only a particular class of arrays. For $n = 5$, let's say the largest number is $8$, so the sequence you're trying is $[4, 5, 6, 7, 8]$. Let's also say that $8$ is the correct answer to the problem. if $a_1 = 4$, then you will say that $8$ is not actually the answer, so you must go higher. Basically, you're filtering this answer out because you're trying only one particular class of arrays.
 » In D , I used an O(nlogn) algorithm by calculating all the O(logn) places,each with a root-changing DP.Max n is 1e5 but surprisingly,my algorithm is very slow(up to 2.5 sec)。So can anyone tell me why?
 » can someone please tell me what's wrong with my submission https://codeforces.com/contest/1882/submission/225463927
 » 2 months ago, # | ← Rev. 2 →   My idea for pbC was that when i found a positive number at an odd position p , i add to the ans all positive numbers after this element.so the rest positive elements are at even index from 1 to p-1. if there is one element just i check if there is neg number before him where their sum psoitive else i sum those elements and i do the same check. but i dont know why it didnt work out 226503504
 » Simplest solution for C: sum all positive numbers in range [3..n]. Then handle first two values manually (add first or first + second or 0)
 » 228386888 #include using namespace std; #define ll long long void dfs(int u, int par, vector adj[], vector &a, vector &val, vector &cnt) { for (auto it : adj[u]) { if (it != par) { dfs(it, u, adj, a, val, cnt); cnt[u] += cnt[it]; val[u] += (a[it] ^ a[u]) * cnt[it] + val[it]; } } } void dfs2(int u, int par, vector adj[], vector &val, vector &ans, vector &cnt, vector &a) { for (auto it : adj[u]) { if (it != par) { val[u] -= (val[it] + (a[it] ^ a[u]) * cnt[it]); cnt[u] -= cnt[it]; cnt[it] += cnt[u]; val[it] += (val[u] + (a[u] ^ a[it]) * cnt[u]); ans[it] = val[it]; dfs2(it, u, adj, val, ans, cnt, a); } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while (t--) { int n; cin >> n; vector a(n); for (int i = 0; i < n; i++) cin >> a[i]; vector adj[n]; for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; u--; v--; adj[u].push_back(v); adj[v].push_back(u); } vector val(n, 0), cnt(n, 1); dfs(0, -1, adj, a, val, cnt); // for(int i=0; i ans(n, 0); ans = val; dfs2(0, -1, adj, val, ans, cnt, a); for (int i = 0; i < n; i++) cout << ans[i] << " "; cout << endl; } return 0; } Could you please tell me where is mistake in re rooting used in above code Thanks!!
 » I didn't get why am I getting tle in D although it is O(n) time and space complexity https://codeforces.com/contest/1882/submission/228653180
 » my solution of D has time and space complexity O(n) but its very slow. Why is that?
 » amazing D problem
 » 2 weeks ago, # | ← Rev. 2 →   i'm too stupid
 » Nice round