Greedy solution. Continue constructing $$$b$$$ as small as possible.
If $$$a_{1} = 1$$$, $$$b_{1} = 2$$$. Else, $$$b_{1} = 1$$$.
For $$$i \ge 2$$$, if $$$a_{i} = b_{i-1} + 1$$$, $$$b_{i} = b_{i-1} + 2$$$. Else, $$$b_{i} = b_{i-1} + 1$$$.
$$$b_{n}$$$ calculated by this process is the answer.
Time complexity is $$$\mathcal{O}(n)$$$ per test case.
Sorry for everyone who got FSTs :( We tried our best to make pretest strong especially for this problem, but it wasn't enough.
Denote $$$T = S_{1} \cup S_{2} \cup \cdots \cup S_{n}$$$, then $$$S \subset T$$$. Since $$$S \neq T$$$, $$$i \in T$$$ and $$$i \notin S$$$ for some $$$i$$$.
Given an integer $$$i$$$, can you calculate the maximum size of $$$S$$$, such that $$$i \notin S$$$?
$$$i \in T$$$ and $$$i \notin S$$$ for some $$$i$$$. Here $$$1 \le i \le 50$$$.
For fixed $$$i$$$, select of all the sets among $$$S_{1}, S_{2}, \cdots, S_{n}$$$ which don't contain $$$i$$$. Size of their union will be the maximum size of $$$S$$$ such that $$$i \notin S$$$.
If we do this for all $$$i$$$ in $$$T$$$, maximum of them is the answer.
Time complexity is $$$\mathcal{O} \left( N \cdot \max \left( s_{i, j} \right) ^{2}\right)$$$.
Fix the topmost card you'll pick in the initial deck.
Let's denote $$$i$$$-th card in the initial deck as card $$$i$$$.
Let the topmost card you'll pick in the initial deck as card $$$i$$$.
For all cards under card $$$i$$$ in initial deck, you can choose all and only cards with the positive value at odd index.
Proof: Here is the strategy. Before you pick card $$$i$$$, if positive card(under card $$$i$$$ in initial deck) in odd index exists, choose it. Repeat this until all positive cards(under card $$$i$$$ in initial deck) are in even index. Then if you choose card $$$i$$$, all index of positive cards(under card $$$i$$$ in initial deck) will be decreased by $$$1$$$, and will become odd. Now, choose them from the bottom to top, so that the choosing won't change the other positive cards' index.
Denote $$$prf_{j}$$$ as the sum of positive numbers among $$$a_{j}, a_{j+1}, \cdots, a_{n}$$$, and $$$prf_{n+1} = 0$$$. Since $$$prf_{j} = prf_{j+1} + \max \left( 0, a_{j}\right)$$$, $$$prf$$$ can be calculated in $$$\mathcal{O}(n)$$$.
You should necessarily pick card $$$i$$$ in index of $$$i$$$, and can pick all positive cards under card $$$i$$$ in initial deck, so your maximum final score will be $$$(i \% 2 == 1 ? a_{i} : 0) + prf_{i+1}$$$.
The answer is $$$\max \left( (i \% 2 == 1 ? a_{i} : 0) + prf_{i+1} \, | \, 1 \le i \le n \right)$$$.
There are lots of other solutions too.
Try to solve the problem for single root.
For any vertex $$$v$$$ which isn't the root, denote $$$par_{v}$$$ as the parent of $$$v$$$. Then value of $$$a_{v} \oplus a_{par_{v}}$$$ only changes if we perform the operation on $$$v$$$.
Since $$$x_{1} \oplus x_{2} \oplus \cdots \oplus x_{m} \le x_{1} + x_{2} + \cdots + x_{m}$$$ for any numbers $$$x_{1}, x_{2}, \cdots, x_{m}$$$, we can assume that there is at most operation performed in same vertex.
Let's solve the problem for single root first.
Denote the operation in the statement as $$$op(v, c)$$$, and size of $$$v$$$'s subtree as $$$s_{v}$$$.
The goal is to make $$$a_{v} \oplus a_{par_{v}} = 0$$$ for every non-root vertex $$$v$$$. This value is changed only when we select $$$v$$$. To make $$$a_{v} \oplus a_{par_{v}}$$$ to $$$0$$$, we should perform $$$op \left( v, a_{v} \oplus a_{par_{v}} \right)$$$ (Look Hint 3).
Therefore, the answer sill be $$$\sum_{i != root} s_{i} \times (a_{i} \oplus a_{par_{i}})$$$. Now our task is to calculate this for all roots. This can be done by lots of ways, and the following algorithm is one way.
Calculate the answer for $$$1$$$ as root first in $$$\mathcal{O}(n)$$$. Now, we will traverse the tree starting at vertex $$$1$$$ and keep updating the answer. If root changes from $$$q$$$ to $$$r$$$ ($$$q$$$ and $$$r$$$ are adjacent), every vertex except $$$q$$$ and $$$r$$$ will have same parents and subtree size, so will contribute same to the answer, so we only need to consider $$$q$$$ and $$$r$$$ to calculate the change. Edge connecting $$$q$$$ and $$$r$$$ will divide the tree into parts: each of size $$$X$$$ and $$$Y$$$. If root changes $$$q$$$ to $$$r$$$, $$$Y \times (a_{q} \oplus a_{r})$$$ will be subtracted, and $$$X \times (a_{q} \oplus a_{r})$$$ will be added to the answer. $$$X$$$ and $$$Y$$$ can be pre-calculated in $$$\mathcal{O}(n)$$$, so this update costs $$$\mathcal{O}(1)$$$.
Since changing root into the adjacent vertex costs $$$\mathcal{O}(1)$$$, answer for all roots can be calculated in $$$\mathcal{O}(n)$$$.
1882E1 - Two Permutations (Easy Version)
Let's think two permutations independently. The goal is to make sequence of operations for each permutation which have same parity of number of operations.
Try to sort single permutation of length $$$N$$$, using at most $$$3N$$$ operations. It is always possible.
If the permutation's length is odd, you can perform operation at index $$$1$$$ for $$$N$$$ times and return to the same permutation.
If the permutation's length is even, the parity of inversion number changes in each operations.
Hints above were the summary of the tutorial. Please check them.
First, let's do Hint 2. There are lots of ways to do this, and I'd like to introduce one which I thought first. It is possible to swap two elements using $$$3$$$ operations. Let's denote the two elements as $$$x$$$ and $$$y$$$, and permutation as $$$[[ A ] x [ B ] y [ C ]]$$$ ($$$[ A ], [ B ], [ C ]$$$ are subarrays). Then:
- Perform the operation at $$$x$$$. Permutation becomes $$$[[ B ] y [ C ] x [ A ]]$$$.
- Perform the operation at $$$y$$$. Permutation becomes $$$[[ C ] x [ A ] y [ B ]]$$$.
- Perform the operation at $$$x$$$. Permutation becomes $$$[[ A ] y [ B ] x [ C ]]$$$.
Using this, we can sort the single permutation of length $$$N$$$ using at most $$$3N$$$ operations, since we can sort the permutation by $$$N$$$ swaps.
If this requires same parity of number of operations for $$$p$$$ and $$$q$$$, the problem is solved. At most $$$3 \max(m, n)$$$ operations are used.
Else, if $$$n$$$ or $$$m$$$ is odd, we can make the parity equal by method provided in Hint 3. At most $$$4 \max(m, n)$$$ operations are used.
Else, then $$$n$$$ and $$$m$$$ is both even. In this case, it's impossible because of Hint 4.
The overall time complexity is $$$\mathcal{O}(n + m)$$$ in this solution.
Lastly, here is the proof of Hint 4.
Proof: Let's consider the permutation of length $$$N$$$($$$N$$$ is even). Denote the permutation as $$$[[ A ] x [ B ]]$$$, and the length of $$$[ A ]$$$ and $$$[ B ]$$$ as $$$n_{A}$$$ and $$$n_{B}$$$. Here $$$n_{A} + n_{B} = N-1$$$ so one of $$$n_{A}$$$ and $$$n_{B}$$$ is even and one of them is odd. Permutation becomes $$$[[ B ] x [ A ]]$$$ after the operation.
First, the parity of inversion number from two elements of $$$[ A ]$$$ or two elements of $$$[ B ]$$$ doesn't change, because their order inside doesn't change.
Second, the parity of inversion number from one element of $$$[ A ]$$$ and one element of $$$[ B ]$$$ doesn't change, because sum of them are $$$n_{A} \times n_{B}$$$, which is even.
Third, the parity of inversion number from $$$x$$$ and one element of $$$[ A ]$$$ or $$$[ B ]$$$ changes, because sum of them are $$$n_{A} + n_{B}$$$, which is odd.
If we add these three, we can lead to the conclusion that the parity of inversion number must change. The text may look a bit complicated, but it will not be that hard if you write them in your own :)
1882E2 - Two Permutations (Hard Version)
Special thanks to kizen providing an key idea which motivated me to make this problem!
The solution is completely different from E1. A brilliant idea is required. Maybe the fact that checker is implemented in linear time might be the hint.
Find a way changing the operation to 'swap'.
Add an extra character.
Add an extra character '$$$X$$$' in front of the permutation. Here position of $$$X$$$ won't be changed by the operation, and will always locate at left of $$$p_{1}$$$. Then in each operation, the permutation will change as: $$$[X [ A ] c [ B ]] \rightarrow [X [ B ] c [ A ]]$$$.
Now, let's consider the array made by $$$X$$$ and permutation as circular. This is possible because $$$X$$$ is always in left of $$$1$$$st element, so it marks the start of the permutation. Then $$$[X [ B ] c [ A ]]$$$ is equivalent with $$$[c [ A ] X [ B ]]$$$.
Then the operation is: $$$[X [ A ] c [ B ]] \rightarrow [c [ A ] X [ B ]]$$$, which is same with swapping $$$X$$$ and $$$c$$$.
Now we need to calculate the minimum odd number of swaps and even number of swaps(of $$$X$$$ and any element) each, turning $$$[X\,p_{1}\,p_{2}\,\cdots\,p_{n}]$$$ to one of $$$[X\,1\,2\,\cdots\,n]$$$, $$$[n\,X\,1\,2\,\cdots\,(n-1)]$$$, $$$[(n-1)\,n\,X\,1\,\cdots\,(n-2)]$$$, $$$\cdots$$$, $$$[1\,2\,\cdots\,n\,X]$$$.
To calculate the minimum number of swaps required to turn $$$[X\,p_{1}\,p_{2}\,\cdots\,p_{n}]$$$ to the given array, first renumber the initial array to $$$[X\,1\,2\,\cdots\,n]$$$, then change the given array in the same correspondence. Do permutation cycle decomposition. Then the answer is (sum of (size + 1) for cycles which have size $$$\ge$$$ 2 and don't contain $$$X$$$) + ($$$X$$$'s cycle size $$$-$$$ 1). This can be proven easily by counting the number of elements which go into the proper place in each operations.
Calculate this for all $$$[X\,1\,2\,\cdots\,n]$$$, $$$[n\,X\,1\,2\,\cdots\,(n-1)]$$$, $$$[(n-1)\,n\,X\,1\,\cdots\,(n-2)]$$$, $$$\cdots$$$, $$$[1\,2\,\cdots\,n\,X]$$$. Since we can't make the same array using different parity of number of swaps, we can achieve the goal by calculating the minimum odd number and minimum even number each.
The overall time complexity is $$$O(n^{2}+m^{2})$$$.
Try solving E1 in $$$n,\,m \le 10^{5}$$$, using at most $$$1.5 \times 10^{5}$$$ operations. It is solvable :)
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.
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.
What is FSTs?
Failed system testing
E2 is amazing!
Can anybody explain me the DP solution for C in an easy way?!
credits: kriepiekrollie
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
$$$\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$$$.
This problem isn't actually dp, but I only realized that after the contest ended and I'd already submitted this code...
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 —
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
Recursive DP solution for Problem C
ayush002024 —
Can you explain more about transitions?
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.
Thank you! I was not understanding that either...
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.
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:
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?
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:
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
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 :))
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:
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.me/contest/1882/submission/225463927
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
amazing D problem
i'm too stupid
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?
Yeah
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.
I think I found a very neat solution to C — 275229304