windva's blog

By windva, history, 14 months ago, In English

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
  • Vote: I like it
  • +213
  • Vote: I do not like it

| Write comment?
»
14 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Just opened codeforces and found this tutorial. Lucky xD.

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried to solve D by DP,but actually it's dfs :( Are there any useful tips to distinguish them?

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    It is dp but you need root changing dp.

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      Oh,yeah,I didn't totally understand the code I saw.thx.

»
14 months ago, # |
Rev. 3   Vote: I like it +44 Vote: I do not like it

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.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

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

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is first solve data?

»
14 months ago, # |
  Vote: I like it +37 Vote: I do not like it

E2 is brilliant.

»
14 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What is FSTs?

»
14 months ago, # |
  Vote: I like it +78 Vote: I do not like it

E2 is amazing!

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody explain me the DP solution for C in an easy way?!

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    // 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

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why dp[n][1] and dp[n][0] 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

      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        $$$\textrm{dp}[i][0]$$$ 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][1]$$$ 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$$$.

      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This problem isn't actually dp, but I only realized that after the contest ended and I'd already submitted this code...

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
14 months ago, # |
Rev. 4   Vote: I like it +1 Vote: I do not like it

Recursive DP solution for Problem C


int recur(int i, int parity, vector<int> &a, vector<vector<int>> &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; }
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you! I was not understanding that either...

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

»
14 months ago, # |
Rev. 4   Vote: I like it +11 Vote: I do not like it

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[0], 0LL)
if(n > 1) S = max(S, a[0] + a[1]);
for(int i=2;i<n;i++) if(a[i] > 0) S += a[i];
cout << S << "\n";
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, thnx for such a clean solution. Can you also explain why choosing only among a_1 and a_2 will give the optimal solution?

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in E2 , I couldnt understand what editorial was trying to say , would greatly appreaciate it if you could explain it in a simpler manner

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    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;
    • »
      »
      »
      13 months ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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.

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      that is some great simple yet intuitive explanation , thanks !

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For E1, I randomly did some operations on both arrays if the parity of the answer was different, and it got accepted.

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve the challenge with E? Can anyone give some tips? Thanks

  • »
    »
    13 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 :))

»
13 months ago, # |
Rev. 8   Vote: I like it 0 Vote: I do not like it

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:

  1. n = int(input())
  2. tests = []
  3.  
  4.  
  5. def no_one_repeat(array1, array2):
  6.     for a, b in zip(array1, array2):
  7.         if a == b:
  8.             return False
  9.     return True
  10.  
  11.  
  12. for x in range(n):
  13.     _ = input()
  14.     tests.append(list(map(int, input().split())))
  15.  
  16. for test in tests:
  17.     suppose_min = len(test)
  18.     done = False
  19.     while not done:
  20.         array = [suppose_min — i for i in reversed(range(len(test)))]
  21.         if no_one_repeat(test, array):
  22.             print(suppose_min)
  23.             done = True
  24.         suppose_min += 1
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Input:
    1
    2
    2 2
    
    Your Output:
    4
    
    Correct Output:
    3
    

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

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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!

      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        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.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please tell me what's wrong with my submission https://codeforces.me/contest/1882/submission/225463927

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn't get why am I getting tle in D although it is O(n) time and space complexity https://codeforces.me/contest/1882/submission/228653180

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

amazing D problem

»
12 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

i'm too stupid

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For 1882B - Sets and Union my idea is: Remove one set at a time , restore it before removing the next set & check how many elements are removed from the main set. From that finding the minimum elements that can be removed. If removing any set don't contribute in decreasing elements from main set then don't restore that set. Can anyone tell me what's wrong with my approach?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Yeah

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

for B, if anyone is wondering why only removing one element yields the best answer, think it like this.

we are not trying to find a set which does not have say i and rest all numbers,

what we are doing is trying to find a set which does not have i, but it is possible that we may miss out on few more numbers in doing so.

think of it like this, say our resulting set(answer set) does not have i,j. that means we have to remove all sets which have i and j.

if i remove all set which has i, then it is also possible that I also remove some set which has some unique element say k (by unique i mean it is not present in any other set). if this is the case then trying to remove j also is of no use because I am already down by two elements i and k.

now, consider the case where we don't end up remove some unique element like k, then also there is no point of removing j, because Iby am already down one element i, removing j will only decrease our answer set size.

hence we only aim to get rid of one element.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think I found a very neat solution to C — 275229304