We apologize for the technical difficulties in Task B. We hope you enjoyed the rest of the contest. We will add hints soon.
Note that if $$$min(n, x+1) < k$$$, then the answer is $$$-1$$$.
Otherwise, there are two cases:
If $$$k=x$$$, then the suitable array looks like $$$[0, 1, 2, \dots, k-1, \dots, k-1]$$$.
If $$$k \ne x$$$, then the suitable array looks like $$$[0, 1, 2, \dots, k-1, x, \dots, x]$$$.
In both cases, we can construct the array and calculate its sum in linear time. The overall complexity is $$$O(n \cdot t)$$$.
Note that after performing the operation on $$$b_j$$$, which has some bit set to 1, this bit will become 1 for all numbers in $$$a$$$ (and will remain so, as a bit cannot change from 1 to 0 in the result of an OR operation). If $$$n$$$ is even, then in the final XOR, this bit will become 0, as it will be equal to the XOR of an even number of ones. If $$$n$$$ is odd, then this bit will be 1 in the final XOR.
Therefore, if $$$n$$$ is even, by performing the operation on $$$b_j$$$, we set all the bits that are 1 in $$$b_j$$$ to 0 in the final XOR. If $$$n$$$ is odd, we do the opposite and set these bits to 1. So, if $$$n$$$ is even, the XOR does not increase when applying the operation, which means that to obtain the minimum possible XOR, we need to apply the operation to all the numbers in $$$b$$$, and the maximum XOR will be the original XOR. For odd $$$n$$$, it is the opposite: the minimum is the original XOR, and the maximum is obtained after applying the operation to all elements in $$$b$$$.
To apply the operation to all elements in $$$b$$$, it is sufficient to calculate their bitwise OR and apply the operation to the array $$$a$$$ with it.
Let's fix the color $$$x$$$ for which we will calculate the answer. If there is no $$$a_i = x$$$, then there will be no cells of color $$$x$$$, and the answer is $$$0$$$. Otherwise, there is at least one cell of color $$$x$$$.
To find the minimum rectangle containing all cells of this color, we need to find the topmost, bottommost, leftmost, and rightmost cells of this color in the array $$$b$$$. Let's find the prefix in $$$a$$$ of the maximum length, where all numbers are strictly less than $$$x$$$. Let the length of this prefix be $$$L$$$. Then in the first $$$L$$$ rows and columns of the array $$$b$$$, there will be no cells of color $$$x$$$, because for all these cells, the formula $$$b_{i, j} = min(a_i, a_j)$$$ will have a number from the prefix, and all numbers on it are less than $$$x$$$. In the $$$L+1$$$-th row and $$$L+1$$$-th column, there will be cells of color $$$x$$$, because $$$a_{L+1} \geq x$$$. Thus, we have found the topmost and leftmost cells of color $$$x$$$. To find the bottom and right cells, we need to find the longest suffix where all numbers are less than $$$x$$$.
Now we need to learn how to quickly find prefixes and suffixes for all colors. Notice that the prefix for color $$$x$$$ is not shorter than the prefix for color $$$x + 1$$$, so all prefixes can be calculated in just one pass through the array, similarly for suffixes.
Note that if there is a prefix for which there is a longer prefix that costs less, then it is useless to buy the shorter prefix. All its purchases can be replaced with purchases of the longer prefix, and the answer will only improve. Therefore, we can replace each $$$c_i$$$ with the minimum $$$c_j$$$ among $$$i \leq j \leq n$$$ (the minimum price of a prefix of length at least $$$i$$$). After this, we will have $$$c_i \leq c_{i+1}$$$.
Now let's solve the problem greedily. We want to maximize the first element of the resulting array. It will be equal to $$$k / c_1$$$, since we cannot buy more prefixes of length $$$1$$$ ($$$c_1$$$ is the smallest price). After buying $$$k / c_1$$$ prefixes of length $$$1$$$, we will have some coins left. Now we can replace some purchases of $$$c_1$$$ with purchases of longer prefixes to improve the answer.
How much will it cost to replace $$$c_1$$$ with $$$c_i$$$? It will cost $$$c_i - c_1$$$ coins. Moreover, note that to replace $$$c_1$$$ with $$$c_i$$$, we can sequentially replace $$$c_1$$$ with $$$c_2$$$, $$$c_2$$$ with $$$c_3$$$, $$$\ldots$$$, $$$c_{i-1}$$$ with $$$c_i$$$ (since $$$c_1 \leq c_2 \leq \ldots \leq c_i$$$). This means that we can make only replacements of purchases of $$$c_{i-1}$$$ with purchases of $$$c_i$$$.
Let's say we have maximized the first $$$i-1$$$ elements of the answer, and we have $$$x$$$ coins left. Now we want to replace some purchases of $$$c_{i-1}$$$ with $$$c_i$$$. How many replacements can we make? We can afford to make no more than $$$\frac{x}{c_i - c_{i-1}}$$$ replacements (if $$$c_{i-1} = c_i$$$, then we can replace all $$$c_{i-1}$$$), and we cannot replace more purchases than we have made, so no more than $$$a_{i-1}$$$ replacements (this is the number of purchases of $$$c_{i-1}$$$). Therefore, $$$a_i = \min(a_{i-1}, \frac{x}{c_i - c_{i-1}})$$$, as we want to maximize $$$a_i$$$. Finally, subtract the cost of replacements from the number of coins and move on to $$$c_{i+1}$$$.
Let's solve the problem using dynamic programming, let's store $$$dp[i][j]$$$ such that $$$dp[i][j]=1$$$ if it is possible to obtain an $$$XOR$$$ of $$$MEX$$$ values from the prefix up to $$$i$$$ (excluding $$$i$$$) equal to $$$j$$$, and $$$0$$$ otherwise. Notice that the answer cannot be greater than $$$n$$$. Therefore, the size of this two-dimensional array is $$$O(n^2)$$$.
Let's learn how to solve this in $$$O(n^3)$$$:
We iterate over $$$l$$$ from $$$1$$$ to $$$n$$$, and inside that, we iterate over $$$r$$$ from $$$l$$$ to $$$n$$$, maintaining the value $$$x=MEX([a_l, a_{l+1}, \dots, a_r])$$$. Then, for all $$$j$$$ from $$$0$$$ to $$$n$$$, we update $$$dp[r+1][j \oplus x]=1$$$ if $$$dp[l][j]=1$$$. This way, we update based on the case when the resulting set includes the set $$$[a_l, a_{l+1}, \dots, a_r]$$$.
We also need to update if $$$dp[l][x]=1$$$, we assign $$$dp[l+1][x]=1$$$. This accounts for the case when we do not include $$$a_l$$$ in the answer.
Let's define $$$MEX(l, r) = MEX([a_l, a_{l+1}, \dots, a_r])$$$, this will make the following text clearer.
Let's consider the segment $$$l, r$$$. Notice that if there exist $$$l_2$$$ and $$$r_2$$$ ($$$l \leq l_2 \leq r_2 \leq r$$$) such that $$$l_2 \ne l$$$ or $$$r_2 \ne r$$$ and $$$MEX(l, r)=MEX(l_2, r_2)$$$, then we can take the segment $$$l_2, r_2$$$ instead of the segment $$$l, r$$$ in the set of $$$MEX$$$ values, and the answer will remain the same. If, however, there is no such segment $$$l_2, r_2$$$ for the segment $$$l, r$$$, then we call this segment $$$l, r$$$ irreplaceable.
Now let's prove that there are no more than $$$n \cdot 2$$$ irreplaceable segments. For each irreplaceable segment, let's look at the larger element of the pair $$$a_l, a_r$$$, let's assume $$$a_l$$$ is larger (the other case is symmetric). Now, let's prove that there is at most one segment where $$$a_l$$$ is the left element and $$$a_l \geq a_r$$$, by contradiction:
Suppose there are at least 2 such segments, let's call their right boundaries $$$r_1, r_2$$$ ($$$r_1 < r_2$$$). Notice that $$$MEX(l, r_1) > a_l$$$, otherwise the segment $$$l, r_1$$$ would not be irreplaceable (we could remove $$$a_l$$$). Since $$$a_l \geq a_{r_2}$$$, then $$$MEX(l, r_1) > a_{r_2}$$$. It is obvious that $$$a_{r_2}$$$ appears among the elements $$$[a_l, \dots, a_{r_1}]$$$, and therefore $$$MEX(l, r_2-1) = MEX(l, r_2)$$$, which means that the segment $$$l, r_2$$$ is not irreplaceable, contradiction.
For each $$$a_i$$$, there is at most one irreplaceable segment where it is the smaller of the two extremes, and at most one where it is the larger. Therefore, the total number of irreplaceable segments is no more than $$$2 \cdot n$$$.
Let's update the DP only through the irreplaceable segments, then the solution works in $$$O(n^2+n \cdot C)$$$ time, where $$$C$$$ is the number of irreplaceable segments. However, we have already proven that $$$C\leq 2n$$$, so the overall time complexity is $$$O(n^2)$$$.
Let's store all the number entries in a trie. Consider two traversals of this trie — depth-first search (DFS) and breadth-first search (BFS). In both traversals, we go to the children of a node in ascending order of the number on the edge (in the trie). Let the index of the node representing the number $$$x$$$ in the DFS traversal be $$$dfs(x)$$$, and in the BFS traversal be $$$bfs(x)$$$. Then notice that $$$x = bfs(x)$$$, as in BFS on the trie, we simply look at all the number entries with a certain length in order (lengths are concidered in increasing order). On the other hand, $$$dfs(x)$$$ is the index of the number entry $$$x$$$ in the sorted array. Therefore, we want to calculate the number of $$$x$$$ for which $$$dfs(x) = bfs(x)$$$.
Let's fix a layer in the trie, meaning we only consider numbers with a fixed, equal length of representation. Then let's look at $$$dfs(x) - bfs(x)$$$ for the numbers in this layer. Notice that for two numbers $$$y$$$ and $$$y + 1$$$ in this layer, it holds that $$$bfs(y + 1) - bfs(y) = 1$$$, and $$$dfs(y + 1) - dfs(y) \geq 1$$$. This means that for a fixed layer, the function $$$dfs(x) - bfs(x)$$$ is non-decreasing. Therefore, we can find the $$$0$$$ of this function using binary search on each layer.
Now let's learn how to calculate $$$dfs(x) - bfs(x)$$$. $$$bfs(x) = x$$$, which we can calculate. To find $$$dfs(x)$$$, we can traverse up from the trie node corresponding to $$$x$$$, and at each step, add the sizes of the subtrees that we have traversed in DFS before the subtree with the node $$$x$$$.
The trie has a depth of $$$O(\log(n))$$$, binary search takes the same time, so the overall asymptotic complexity of the solution is $$$O(\log^3(n))$$$.
I apologize for the issues some participants faced with the time limit, if they implemented the author's idea suboptimally.
Let's start by introducing a more convenient way to store numbers — an array $$$cnt$$$, where $$$cnt[x]$$$ represents the number of occurrences of $$$x$$$ in the prefix for which we are finding the answer. All $$$x$$$ such that $$$x > n$$$ will be added to $$$cnt[0]$$$ because applying the operation to $$${x}$$$ in such cases is optimal.
Let's introduce a few array operations that will be sufficient to solve the problem.
- Create the number $$$x$$$. Apply the operation to the set of numbers $$${0, 1, 2, \dots, x-1}$$$. In terms of the array $$$cnt$$$, this is equivalent to subtracting $$$1$$$ from the range $$$0$$$ to $$$x-1$$$ and adding $$$1$$$ to $$$cnt[x]$$$.
- Turn the number $$$x$$$ into $$$0$$$. To do this, apply the operation to $$${x}$$$. In terms of the array $$$cnt$$$, this is equivalent to subtracting $$$1$$$ from $$$cnt[x]$$$ and adding $$$1$$$ to $$$cnt[0]$$$.
- Create the number $$$x$$$ and clear the multiset. This is the same as creating the number $$$x$$$, but we apply the operation to all other numbers, leaving only the single number $$$x$$$ (or a larger number) in the set.
It can be proven that by using only operations of this kind, we can always obtain the optimal answer.
Now we can forget about the original condition and solve the problem for the array.
Let's learn how to check if it is possible to create the number $$$k$$$ and clear the multiset:
First, let's try to create the number $$$k$$$. If it is possible, the answer is yes. Otherwise, we look at the rightmost number that is missing (or in other words, the rightmost $$$0$$$). We try to create it, and now we need to find the rightmost element $$$\leq 1$$$ to the left of it, and so on. To implement this, we need to maintain a number $$$p$$$ such that we subtract $$$p$$$ from all elements in the prefix (initially $$$p=1$$$), iterate through the array from right to left, and if $$$cnt[i]<p$$$, assign $$$p \mathrel{{+}{=}} (p-cnt[i])$$$. When we reach zero, $$$p$$$ may be greater than $$$cnt[0]$$$, in which case we need to use the operation to turn any number into $$$0$$$. To do this, simply check that the remaining number of elements in the array is greater than or equal to $$$p$$$.
This currently works in $$$O(k)$$$ time, which is not very efficient.
Optimization techniques:
First, let's maintain the sum of elements $$$sm$$$ and as soon as it becomes negative, terminate the process. To achieve this, when subtracting $$$p-cnt[i]$$$ from $$$p$$$, let's subtract $$$(p-cnt[i])\cdot(i-1)$$$ from $$$sm$$$. Now let's use a bottom-up segment tree to find the nearest number smaller than $$$p$$$ to the left in $$$O(\log(i))$$$ time.
Now let's notice that when we update through $$$cnt[i]$$$, we subtract at least $$$i-1$$$ from $$$sm$$$, so there can't be more than $$$O(\sqrt{n})$$$ different values of $$$i$$$ through which we will update.
Now we can answer for a specific $$$k$$$ in $$$O(\sqrt{n} \cdot \log(n))$$$ time, but in reality, the complexity is $$$O(\sqrt{n})$$$ (due to the peculiarities of the bottom-up segment tree), and the authors have a proof for this, but they are afraid that you will find an error in it, so they decided not to provide it(we will add proof later).
Now let's see how to solve the full problem:
Initially, the answer is $$$0$$$, and we notice that it does not decrease. So after each addition, we will check if it is possible to increase the answer and increase it as long as possible. The answer cannot exceed $$$n$$$, so we will perform no more than $$$2 \cdot n$$$ checks.
Overall, the solution works in $$$O(n \cdot \sqrt{n})$$$ time. That's how it is.
Let's consider that in our query, the segment tree processed $$$k$$$ nodes $$$[x_1, x_2, \dots, x_k]$$$ from the bottom.
Then, the number of operations is the sum of $$$dist(x_i, x_{i+1})$$$ for $$$i$$$ from 1 to $$$k-1$$$, and $$$dist(0, x_1)$$$, where $$$dist$$$ represents the length of the path between nodes in the segment tree. Now, let's notice that for the query $$$dist(a, b)$$$, we enter the segment tree node responsible for a block of length $$$2^t$$$ only if $$$a$$$ and $$$b$$$ are in different blocks of length $$$2^{t-1}$$$, which is logical. Also, let's notice that this doesn't happen very often, specifically, the numbers $$$[x_1, x_2, \dots, x_k]$$$ can be part of a maximum of $$$\sqrt{\frac{n}{2^t}}$$$ blocks of length $$$2^t$$$ (asymptotically). Therefore, the sum of all queries is asymptotically equal to the sum of $$$\sqrt{\frac{n}{2^t}}$$$ for $$$t$$$ from 0 to 20, which is a geometric progression with a ratio of $$$\frac{1}{\sqrt{2}}$$$. Hence, the sum is asymptotically equal to $$$\sqrt{n}$$$. Proof completed.
1870H - Standard Graph Problem
Let's unfold all the edges, now we need to ensure that all regular vertices are reachable from the selected vertices.
First, you should familiarize yourself with the algorithm for finding the ordered minimum spanning tree, also known as the Edmonds' algorithm (I will refer to his work here and without knowledge of it, the solution cannot be understood). Next, it is worth noting that the compressions in the process of this algorithm (almost) do not depend on the root, and all compressions can be performed as if there is no root (previously creating dummy edges from $$$i$$$ to $$$i+1$$$ for $$$i$$$ from $$$1$$$ to $$$n-1$$$ and from vertex $$$n$$$ to vertex $$$1$$$ with a cost of $$$n * max(a_i)+1$$$). Then, after all the compressions, only one vertex will remain. Note that the difference from Edmonds' algorithm is that if at any step of the algorithm the minimum edge from a vertex leads to the root, compression is not necessary.
So, let's maintain a tree in which each vertex corresponds to its corresponding compressed vertex or to the original vertex, and the children of vertex $$$v$$$ are all the vertices that we compressed to obtain vertex $$$v$$$. It is implied that with each compression, we create a new vertex.
Let's call the cost of vertex $$$v$$$ the minimum cost of an edge leaving vertex $$$v$$$ in the process of Edmonds' algorithm (taking into account changes in edge costs during compression in Edmonds' algorithm).
Then we need to maintain the sum of the costs of the vertices in the tree, in the subtrees of which there are no selected vertices (where the selected vertices can only be leaves). This can be easily done using a segment tree.
Please rate the problems, it will help us make the problems better next time!
You can choose one best problem, or not choose if you think there is no such task.
wow , very fast tutorial
SpeedForces!!
FastEditorialForces
Thanks for fast tutorial!
bad tests for E
Can someone explain the editorial of D in more detail?
Basically, the idea in this problem is to greedily choose which prefix to use. As the editorial explains, we first choose the minimum prefix that's the farthest from start (say it's like 3 4 3 6 5, k = 11, we choose the last 3). Now, whatever we have left over is k%3 because we are going to use as many as possible. With this remainder, we can improve our solution. in the example above, remainder is 2 and we can upgrade one of the 3s to a 5 because the difference is <= remainder. We repeat this process and each time the remainder keeps getting smaller. Also, another requirement is that the number of upgrades you can make from previous step to next step is upper bounded by the previous step. Think about why this makes sense. You cannot upgrade more things than that are currently existing. You can checkout my profile for a simple solution using maps and a special type of suffix array. Let me know if you need any clarifications.
Hello SaiAnoop, can you help explain why it is possible that the number of upgrades you can make from previous step to next step is not upper bounded by the previous step when ci>=ci-1？ I did not use this restriction and failed.
Actually, I don't know if you read it wrong or if I didn't say it correctly, but the number of upgrades you can make from a previous step to a next step is upper bounded by the previous step. In other words, say I have costs x,y,z x < y < z. First, I maximize number of x, then with the remainder k%x, we will try to replace some of the x with y. this number is remainder / (y-x). We continue this process until remainder equals 0 or we reach end of array. Now, to prove the point about why we need to upper bound, consider this example (this is what I used to figure out the logic during the contest): 99 99 99 10 99 99 15 99 99 16 99 99 99, k = 219 Now, based on our algorithm, we will first do 21 x 10 = 210 remainder = 9 Using these 9, the next best element is 15, so we do 9/5 = 1 9%5 = 4 now, if we don't upperbound we will end up doing 16 4 / (16-15) = 4 but this doesn't quite work because if you remember the original remainder was 9. now if we do 4*(16-10) that comes out as 24. So we are overcounting, so therefore, we need to upper bound by the previous step. Without using the math, to think in logical terms, we are trying to upgrade some of the previous steps into next steps, how can you possibly upgrades more next steps than there are total # of previous steps. I hope this helps.
Thank you very much for your careful reply, especially the wonderful example. I have understood the solution.
ofc. glad I could help!
can you explain why was this required
i got WA when i commmented it but i dont understand why
if you see how i initialize lastind, initially set to -1 just as default value. if it's equal to -1, then it's a dummy value and not actually last index, so we check to make sure it's a real last index and not a dummy value.
i have made the same approach as you said, but i got some wrong test cases this is my submission: https://codeforces.com/contest/1870/submission/224067985
every loop I repeat what I have done with the first minimum element but taken k % last_minimum_element then storing the answer in an vector of pair containing the value to print and the index to print up to it
why it gives my wrong answer?
https://codeforces.com/contest/1870/submission/224250810 Can u say where am I wrong Give me a test case
Bro how do u test this solution and get the wrong test case, Can u please share the software for the same
The above test case which I provided you is included in the main tests of the question itself. However by modifying this code you may generate some simple test cases. Also you may write some code to directly give you a test case where your code is failing by comparing it to an accepted code.
I have done the same approach as yours for D https://codeforces.com/contest/1870/submission/224250810 Can u say where am I wrong Give me a test case
In G, it is possible to replace segtree with DSU to find nearest position with value smaller than $$$p$$$, using the fact that these $$$p$$$ are frequencies so sum of $$$p$$$ is small, and we never decrease them.
Could you elaborate more?
MEXForces was fun, E and G were nice IMO
O sa vorbim cand ai locul 1 la bacterii2
Can anyone help why my submission for D is not working ? Submission
I used binary search to determine the number of operations which must be transferred from ci to c(i+1), is this wrong ?
You can take a look at this solution, I also used binary search for finding how much should be transferred, from current to the smallest element to right of current. https://codeforces.com/contest/1870/submission/224001124
Thanks, in your approach, you start resulting array from maximum element from the left, why don't we start resulting array from minimum element from the left ? Greedily we should start from minimum left I guess. Please correct me if i am wrong
I am doing that only, I am taking the minimum element (mn) go to that and after that I get to the smallest element to the right of mn (which is obviously greater than mn as mn was the smallest number yet) make the transfers if possible and go on, if no transfer was possible then break
Why is your code so long? :sob:
any one lost problem 3 just because of not able to understand the point( must include all positions of same colour in the rectangle) or is it only me
I've managed to submit it on the last two minutes of the contest. So basically this rectangle should contain every element of same color (number less or equal to k). That means upper bound of this rectangle is equal the minimal i for all common numbers, as well as left bound = minimal j, bottom bound = maximal i, right bound = maximal j.
So for example, if you have matrix like this:
The both sides of rectangle of color 2 will be equal to 3:
Hope that helps.
SomethingNew, In problem 1870E - Another MEX Problem ,Why we cannot think DP in this way ?
dp(i,j) -> max bitwise xor till index i inclusive and the last subarray mex is j in getting that. But after defining this like that it will get stuck afterwards. So what is the intutiton of that you used a bool DP as does not come to my thought process.
Is it just try to apply a concept and then see if it works fine or something else need to consider.
Like another DP I think of was like :
dp(i,j,k) -> maximum bitwise XOR till index i inclusive and the last subarray is of length j and its mex is k and we will precalculate mex of all the ranges from 1 to n i.e. 2D mex table.
Why is it wrong ? Is it just that optimal substructure does not suffice in defining in this DP or we can't make transitions that's why?
Any help will be so kind of you and will be very helpful.
Thanking you
.
SomethingNew, Can you please reply? I have been stuck for a long time that's why I asked you about the mistake in thought process i am thinking
Xor is not like sum, Max xor isn't necessarily obtained by another maximum xor , it can possibly be obtained by any other xor value as well. That's why your dp is wrong.
devesh_7, thanks for your time but can't we do like this as below :
let DP(i,j,k) -> max bitwise xor till index i inclusive it and last subarray taken mex is j and of length k. And also pre-calculate 2D mex table so that we can access all mex value for ranges in constant time.
Now the transitions will be like this :
DP(i,j,k) = max( DP(i-k,p,q) XOR mex(i-k+1,i) ) where p ranges from 0 to n+1 and q ranges from 1 to i-k;
What will be wrong in this because i am more interested why this will not work. SomethingNew and glebustim, can you please also look into this.
You missed the whole point of my comment. Max Xor is not necessarily obtained by another maximum Xor. That's why We are interested in all possible Xor values.
devesh_7 No,I understood your above comment and not neglecting that but why this DP is wrong then or is the above one is not DP .
It's just recursive brute-force ??
Ok I think this DP is not DP its just i have for the sake of formulating DP I have just somehow made it.
Its like exponential recursive brute force that is not DP actually then.
Am i correct here ?
SomethingNew, glebustim, devesh_7, Sorry for pinning you guys again and again but till now no one original author , editorialist not replied but only downvoted me. (I don't know why? )
Have i asked a wrong question here on the site, Why so many downvotes ?? It is a question that i have been stuck for a long time and genuinely someone to guide upon. So can anyone explain the reason behind this.
Curse of low rated questions, thats why it so downvoted:)
Okay so everyone who downvoted knows the answer for the question then why they just did not reply to it.
Why is it wrong ?
It is not wrong. You can define DP in anyway you like.
A given DP is said to have Optimal Substructure Property if the optimal solution of the given problem can be obtained by using the optimal solution to its subproblems instead of trying every possible way to solve the subproblems.
Being able to make transitions and having optimal substructure have similar meaning.
I think your problem was downvoted because your fundamentals are not clear. And also, you are tagging the author himself for such doubts. Generally, people are busy and don't have enough time to reply.
Okay , so finally someone replied to my question.Thank you so much adityagamer.
Thanks for the fast Editorial.
E tests are weak, it was necessary to add a test
0, 1, ..., n/4-1, 0, 1, ..., n/4-1, 0, 1, ..., n/4-1, 0, 1, ..., n/4-1
This breaks my solution
Can you please explain your solution and with does this case break your solution? I'm just curious.
If there are two segments [l, r1], [l, r2] (r1 < r2) with the same mex, then in DP I iterate only the first one. There can be O(n^2) such segments and my solution works in O(n^3)
Lol, I did that but with the roles of l and r reversed. Got TLE on pretest 8.
Hey Hi, @dimss I saw you solution for problem E its really nice. but I am not getting how its working in O(n^2). can you please explain time comp. once please. I just have doubt where you are updating the other state using vector_pair.
It works in O(n^3)
A similar easy version of the problem C : Max distance of a number greater than a given number in array
Do you remember when the MEX operation felt like something rare and fresh when it appeared ?
Ah, good times
(This is just my salty comment, don't take it too seriously)
My approach is failing for the 1346th test in test case 2. Any one else ?
It is based on Boolean Algebra.: (Assume bitwise OR '|' is represented by '+').
As for going through all combinations of or, I have done something similar to the editorial. As the operation of OR is transitive, I sorted b and did the above operation for all is the b-ith and the cumulative Or up-till that point.
If anyone else has experienced the same, or could provide some insight, I'd be grateful.
Thank you very much.
homie are you sure, this is gonna work?, using boolean algebra, complexifies it instead of simplification.
rather think it of as in this way,
consider the numbers are even, if we, take any number from b and take its OR, then some set bits are gonna remain set, and some unset bits will get set, now xor of two set bits is 0, hence OR is always gonna be less. Whereas it's opposite in Odd's case.
Now the maximum number that you can take for ORing is OR of array B.
Approach was right, silly mistake.. for calculating minimum and maximum, I initialized it to the xors, The fact is it can go below XOR of all the elements. That was stupid and cost me the contest :(
Thanks for the contest! I noticed some small typos in the editorial for E:
Where it says "there is at most one segment ... where $$$a_l \leq a_r$$$", it should be $$$a_l \geq a_r$$$.
Where it says $$$MEX(l, r) > a_{r_2}$$$, it should be $$$MEX(l, r_1) > a_{r_2}$$$.
thanks bro
In editorial for E it $$$a_l$$$ is sometimes called smaller than $$$a_r$$$ and sometimes larger. I think it should always be larger for the proof to work
Editorial E:
Did you mean equal to j (instead of x)?
yes
Anyway E is really bad for any kind of programming contest, since it's so much easier to come up with the correct solution and decide to submit it than it is to prove that it's correct. Your proof is really simple but it's pretty hard to come up with in my opinion
I think this is the difference between programing and math. you don't need to proof something if it is reasonable.
What is reasonable? I came up with the correct solution pretty fast and I think that the fact that I couldn't find the proof for a much longer time means that it was not reasonable to assume that it works. Usually when I don't prove something during contest it's because I understand that I can prove it in a couple of minutes and that's what I would call reasonable. Otherwise it's no different from submitting every idea you have when you don't know how to counter it, and I think that penalties for wrong submissions are meant to disincentivize that kind of behaviour, so it's not intended for a non-IOI style contests
Примерно такого ответа я и ожидал) the meme could've been in english though
You shouldn't necessarily submit every idea you can't come up with a break case for, instead if you suspect something is true (but don't have a proof), why not write some code to generate all arrays of size 9, and see that the maximum number of important subarrays is on the order of n rather than n^2 (affirming your suspicion), and then implement your solution. If you're still interested in it, you can work on/learn about the proof after the contest.
The difference between a programming and math contest is in a programming contest you have a computer, you should use it.
even that is unnecessarily 10mins wasted (assuming youre really fast in coding all that), and small numbers wont even tell you much, since the difference between O(n^2) (with small constant) and O(n) (with high constant) isnt even that large.
if a proof is harder than the rest of the problem, thats a bad problem for a programming contest, or any contest where you dont need to write a proof.
I don't think it's a waste of 10 mins if it allows you to solve the problem, but the constant could obfuscate it (agree)
I see your point about the proof, I personally feel like it's still an interesting problem, and it doesn't necessarily make it bad, but I see why you disagree
I came up with "there should be a small number of expandable intervals" pretty fast but didn't bother to prove it. Solved it in a different way using dp[xor] = the smallest prefix with xor obtainable.
I've come up with a solution that needs no proof though, just wanna share bcz it's really nice. Here is my code.
(This is my first time writing a solution so sorry if it's too long lol, recommend reading the code first before coming back here for clarification. TLDR: use a traditionally approached dp and make sure not to repeat an $$$i$$$ $$$XOR$$$ $$$j$$$ operation with the same $$$(i,j)$$$ too many times.)
Here are the steps:
Calculate every achievable $$$XOR$$$ value of $$$MEX$$$ of subarrays of prefix up to $$$i$$$-th element. (In other words, replace the initial array with its prefix (1 to $$$i$$$) then calculate all possible values). DP $$$i$$$ from 1 to $$$n$$$ then store it in a vector $$$can[][]$$$.
To compute $$$can[i]$$$, iterate backward $$$j$$$ from $$$i$$$ to 1, calculate $$$mex[j,i]$$$ (the transition from $$$j$$$ to $$$j-1$$$ can easily be done in $$$O(1)$$$), and then $$$XOR$$$ $$$mex[j,i]$$$ with every element of $$$can[j-1]$$$, then store the results in $$$can[i]$$$.
$$$can$$$ stores $$$O(n^2)$$$ elements, let's make it $$$O(n)$$$: to avoid repetition, every elements of $$$can[j]$$$ with $$$j<i$$$ won't appear in $$$can[i]$$$. To do so, just use a $$$vector<bool> check$$$ if a number was stored while iterating dp. // It will be helpful later on to reduce time complexity.
Here's the tricky part: the complexity of the above process is $$$O(n^3)$$$, so let's optimize it to $$$O(n^2)$$$.
done phew. Thanks for reading all the way here xD. Plz let me know if there are any unclear parts.
only if I had 15 minutes more to submit it during the contest T_T see you again yellowwhy my code gives wa on test 4
PROBLEM D
https://codeforces.com/contest/1870/submission/223922693
tried to solve problem D using binary search for the contribution of each element, but getting wa on test 3.
Can someone point out the mistake if you have also implemented the same idea 223895614
We made the same mistake.
This is happening because we started replacing elements from the end, which might lead to a smaller array lexicographically. This happens when you use the same number of coins, but there exists a position between two positions in your solution such that you could've taken extra coins from the larger index to increase the prefix spanned by the smaller index. For example-
Consider n = 5, c = [10 2 2 2 3] & k = 7
The answer is [3 3 2 2 0] in this case
but you find the answer to be [3 3 1 1 1]
Edit: This example is wrong. However, a correct example is in the following comments!
But the ans will be [3 3 3 3 1] and my code is working right for this test case.
Ah, okay, so my example was wrong, but the whole idea why the solution doesn't work is the same.
Try this instead-
n = 4
c = [40 41 46 47]
k = 253
Your code(I tested this time) answers [6 2 2 1]
But if I buy five c2 and one c4, I'd use a total of 243 coins and get the answer [6 6 1 1]
And that is lexicographically larger.
Thank you so much for pointing the mistake.
Excuse me, but isn't the answer for this test is
$$$ans = [6,6,1,1]$$$
You can buy $$$c_2$$$ $$$5$$$ times which equals $$$205$$$, so you have remaining coins equals $$$253 - 205 = 48$$$ which is sufficient to buy $$$c_4$$$ once
So by that we obtained larger lexicographically ans
Correct me if I misunderstand something
Yes, thank you for pointing out the mistake. I was trying to show that there exists a better answer- I wasn't looking at the final solution. My bad!
No problem my friend, thanks for that test btw, it showed me the wrong in my approach and it pointed me to the right solution!
So, I'm the one who needs to thank you ^^
I have an alternative solution to problem E.
Notice that the maximum MEX of subarray will be O(n), and the maximum XOR of MEXs of subarrays will also be O(n).
You can notice that for a fixed Y, you only care about the first position X, such that you can make the XOR of chosen subarrays equal to Y, while the last subarray ends at position X. This is easy to prove, and I will leave that as an exercise for the reader.
You can also precalculate nxt[l][M] for each pair of (subarray starts at least at position l, MEX of subarray is M). This will store the least position R, such that there exists a subarray [L;R], where MEX is equal to M, and L >= l, if it exists, and -1(something to show that it's not possible) otherwise.
Now what you can do, is write a Dijkstra in O(n^2) where in dist[Y] you store the least position, such that you can chose some subarrays where the last of them ends at position dist[Y], and XOR of their MEXs is equal to Y. To make a transition, you iterate over value of the MEX of the next subarray, and using the precalculated nxt[l][M], you know whether you can make such a transition or not, and what the least next position could be.
Oh, this is so much more intuitive than the intended solution. Honestly, I even feel bad now for not thinking about that during the contest...
Could you share the intuition why this approach works?
I implemented it but got tle at test 10
Hey, so, first of all, you don't have to use set to get MEX of all subarrays, you can do it in $$$O(n^2)$$$ total time complexity, by fixing one border of subarray, iterating over the other, and MEX can only increase, so it's possible to use two pointers(store in some bool array values that you have already, or smth like that).
Secondly, you don't need to use Dijkstra with priority_queue, the given graph is not sparse(in fact it's complete), so it would be better to use Dijkstra in $$$O(n^2 + m)$$$, without priority_queue.
Thanks
I'm confused about the explanation for E and would appreciate it if anyone could explain where I am going wrong.
From my understanding, the tutorial is saying that for each position, it will only show up as the smallest extreme in only one irreplaceable segment. However, take [0, 1, 2]. Isn't 0 the smaller extreme in both [0, 1] and [0, 1, 2] which are both irreplaceable?
It should actually be, "$$$a_i$$$ can be the larger element and the left extreme atmost once, and it can be the larger element and the right extreme atmost once." SomethingNew
Yes, thanks
Can anyone tell me what is wrong in this soln? It is giving WA in test case 4 and idk how to debug it.
223949565
Try this:
output is 4 1 0 , isnt it correct?
nope, ans will be 4 1 1
okay, thanks found my mistake..
224037810 mine give the right output on your case but still WA on the same test as his.
I came up with the solution to the problem $$$E$$$ with the complexity $$$O(NP)$$$ where $$$P$$$ stands for the number of segments $$$[l, r]$$$ so that $$$mex[l, r]$$$ is equal neither to $$$mex[l+1, r]$$$ nor $$$mex[l, r-1]$$$. Can anyone bound the number of such segments better than $$$O(N^2)$$$?
Your segments coincide with the segments in the editorial.
Yup, my bad
I think calculating $$$\text{dfs}(x)$$$ in $$$O(\log n)$$$ is the hardest part of 1870F - Lazy Numbers. However, some people managed to compute it in $$$< 10$$$ lines using some magic (for example,
getidin 223885585). Could anyone elaborate?Suppose that $$$x$$$ has $$$d$$$ digits, we count all $$$y$$$ such that $$$y$$$ comes before $$$x$$$ in dfs order. We iterate over the number of digits of $$$y$$$, let's denote it by $$$e$$$. We have inequality $$$k^{e-1} \leqslant y \leqslant min(x', n)$$$, where:
Case $$$e \leqslant d$$$: $$$x'=floor(x/k^{d-e})$$$, i.e. the prefix of $$$x$$$ of length $$$e$$$.
Case $$$e > d$$$: $$$x'=x\cdot k^{e-d} + k^{e-d} - 1$$$, i.e. $$$(k-1)$$$'s appended to the back of $$$x$$$.
Maybe you can read jiangly's code, I think it's clear enough.
Can someone explain how we can find the irreplaceable segments in Problem E? I understand how it' s upper bounded by 2n but how can we find those segments so we can iterate over them.
You just need to check $$$[l, r-1]$$$ and $$$[l+1, r]$$$.
Proof: if $$$\text{mex}(l, r) = \text{mex}(l', r')$$$, and $$$l \leq l' \leq r' \leq r$$$, then $$$\text{mex}(l'', r'') = \text{mex}(l, r)$$$ for every $$$l \leq l'' \leq l'$$$ and $$$r' \leq r'' \leq r$$$.
Hi SaiAnoop , can you please explain how its upper bounded by 2n, Thanks!!
I had a different approach for problem E. In my approach dp[x] means minimum length of prefix from which it is possible to obtain x as XOR of MEX values from the prefix. I've also precalculated nxt where nxt[a][b] means minimum value of r for which there is an l such that $$$(a <= l <= r)$$$ and mex of subarray(l, r) is $$$b$$$.
Here's my submission
I think it's not true. Think about $$$a=[0,1,2,3,4,5]$$$. For $$$a_1$$$，there are $$$6$$$ segments where it is the smaller of the two extremes because $$$0$$$ is always smaller, they are $$$[1,1],[1,2],\dots,[1,6]$$$.
I think it can be explained by a way like:
For each segment, we use a pair $$$(i,0/1)$$$ to describe that its greater extreme is $$$i$$$, and the other extreme is at its left side/right side. For a specific pair, there is at most one segment corresponds to it.
Mysterious E
Kindly help with code for problem C. I got the tutorial but need to know how to code prefixes and suffixes.
so fast tutorial! thx! good round.XD
Nowadays difficulty rating of the recent contest problems is not getting updated.
MEXForces
another solution for E. is to for each value v track the first position i where it is possible to create v.
we loop from 1 ~ n keeping track of the the minimum position to create a mex value 0 ~ n with n + 1 sliding windows. Then, if the current index is the first possible position to create a value v we xor the value v with every possible mex and update the min index array.
each value v will only have 1 possible first position so updates are bounded by O(n^2) and maintaining the sliding windows are also bounded by O(n^2) as it costs O(n) each so the final complexity is O(n^2).
https://codeforces.com/contest/1870/submission/223975557
whoops, did not notice someone else alr posted about this
alternative proof for number of irreplaceable sub-arrays:
let mex[l][r] be the mex of a[l], a[l + 1], ... a[r],
the array mex[l][1 ... n] can have at most n distinct values
each first distinct value of mex[l] that differs from what it becomes in mex[l + 1] will be counted as an irreplaceable subarray
notice that each value that changes between mex[l] and mex[l + 1] will become the same value namely a[l] in mex[l + 1] because we're removing a[l] from being considered in the mex calculations.
let dec[i] be the number of distinct numbers that change between mex[l] and mex[l + 1], the number of distinct numbers of mex[l + 1] will be less than the number of distinct numbers in mex[l] — dec[i] + 1.
the number of distinct numbers in mex[n] will be less than the number of distinct numbers in mex[1] — dec[1] + 1 — dec[2] + 1 ... — dec[n] + 1. This implies the sum of dec[1 ... n] is less than n (initial distinct number count) + n (possible increase in distinct numbers).
Noob solution for B
223974675
In order for:
Maximising final XOR: we try maximising every bit. Keeping every bit on in the best case scenario.
Minimising final XOR: we try minimising every bit. Keeping every bit off in the best case scenario.
Imagine each of $$$a_i$$$ and $$$b_j$$$ in terms of their bitsets/binary representation.
What is needed for the $$$i^{th}$$$ bit of final XOR to be high/on ?:
At the end of the optimal set of operations (whatever that might be), if we look at the $$$i^{th}$$$ bit of all $$$a_i$$$'s and say $$$count$$$ is the number of high bits, then this $$$count$$$ must be odd.
Similarly, for minimising the $$$i^{th}$$$ bit of final xor: this $$$count$$$ must be even.
Suppose it is possible to get the best-case maximum final XOR (where all bits are high) with just a single operation if we choose an optimal or best number. Lets call the binary-representation of this best number as the $$$optimal$$$ string.
Defining $$$optimal$$$ binary-string/bitest to maximise final XOR:
if $$$n$$$ is odd: if $$$i^{th}$$$ bit has on-count = odd, then optimal string's $$$i^{th}$$$ bit is unimportant (because no matter what you do, this on-count will stay odd only). Else it must be $$$1$$$ necessarily for optimality.
if $$$n$$$ is even, then: if $$$i^{th}$$$ bit has on-count = odd, then optimal string's $$$i^{th}$$$ bit must $$$0$$$ necessarily. Else its unimportant(same reason as before).
Defining $$$optimal$$$ binary-string to minimise final XOR:
if $$$n$$$ is odd, then: if $$$i^{th}$$$ bit has on-count = even, then optimal string's $$$i^{th}$$$ bit must be $$$0$$$ necessarily. Else its unimportant.
if $$$n$$$ is even, then: if $$$i^{th}$$$ bit has on-count = even, then optimal string's $$$i^{th}$$$ bit must is unimportant. Else it must be $$$1$$$ necessarily.
At this point, I should have pivoted to notice/reinterpret the situation in terms of the fact used by editorial. But anyways since I couldn't see it, here is an alternate approach, although dumb, unnecessary and laborious.
The $$$optimal$$$ strings just defined may or may not actually exist in the array $$$b$$$. So, we have to find that set of elements of $$$b$$$ whose cumulative $$$OR$$$ satisfies these $$$optimal$$$ strings as best as possible.
Strategy for finding the best fit set of elements of $$$b$$$ for the optimal strings:
Thus, we have the two different best-fit set of $$$b$$$-elements for maximising and minising the final XOR. Now, the solution is straightforward, just calculate the final XOR by applying the operation in problem statement for all elements of the best-fit sets.
223974675
IN D question :-i have taken best possible answers from min1 to min2 , min1 to min3 , min1 to min4 ....... then why it is giving error.?
void solve(){ int n; cin>>n;
int k; cin>>k; int p=*min_element(v.begin(),v.end()); if(p<=k){
Please give the code for F, as "To find dfs(x) , we can traverse up from the trie node corresponding to x , and at each step, add the sizes of the subtrees that we have traversed in DFS before the subtree with the node x ." is too ambigious for me to make sense of.
Thanks for the good contest!
Can someone explain the editorial of E in more detail?
Problem C: how to find the longest prefix and suffix with elements < x for each color x?. I cant do this in O(n). I can do this in O(n^2). Please explain
Problem-D : Why is my code wrong ?? 223975030
my logic is same like you . and got the same error on the same testcase. after last 2 hrs debugging i dont find the exact reason but it may be the code is giving runtime error on some testcases (it is 52 after dbeugging in my code). which results in to automatically jumping of testcases to 93(it sounds wierd).
try case
1
4
10 12 13 14
99
answer should be 9 3 2 1
i think the answer should be 9 4 1 0 ,and this is my code 224008681,i can't find my fault,can anyone tell me what is wrong in my code?
You need to perform
ans[0]=1e9+5inside thewhile(t--)loop, sinceans[las] -= tmp;may change the value ofans[0]. Also, inside thewhile(1)loop, you needif(cnt>=n) break;instead ofif(cnt>n) break;.Can we also have the code part in editorial ?
Can Anyone point out the error in my solution? It is failing at 113th position in test 2. We should be allowed to see all test cases after the contest is over. I have used a set to find the minimum price. Any help is appreciated.
i m failing at 114.lol
Can someone please tell what is wrong in my code for problem D? my submission
I think i have implemented the exact same solution as given in editorial, but still it is failing in test 2. Any help is appreciated.
Try to declare
int cnt = 1e9;at the beginning of thesolve()function, and instead to performint cnt = k/(curr - prev);, usecnt = min(cnt, k/(curr - prev));since the variablecntmeans that you "replace"cntprevious purchases into the current ones, so the currentcntmustn't exceed the previouscnt.Thanks prairie2022, it worked!
You're welcome.
Can you see mine https://codeforces.com/contest/1870/submission/224114880
I have tried solving problem E by pre calculating mex's of all the subarrays and then use dp to pick some ranges and xor the mex of all the picked ranges.
Getting WA on TC 11.
Link to submission: E
What is wrong with this approach ? Can anyone please explain ?
understood why this wont work as max xor of the segment (i, j) can come from any of the possible segments from (j + 1, n — 1) but in my logic I'm just taking max xor from segment (j + 1, n — 1) and trying to calculate the max xor for segment (i, j).
Any counter Test, or place at what i done mistake for D
https://codeforces.com/contest/1870/submission/224114880
.
why is this solution wrong for D ? https://codeforces.com/contest/1870/submission/224184528
ignore solved.
What's 114th input in testcase2 of D?wtf man
can any one explain why this brute force got accepted. https://codeforces.com/contest/1870/submission/224151942
wrong answer 807th numbers differ — expected: '1', found: '0' , in D ????help! here's my pycode
can someone tell error in my submission for problem c https://codeforces.com/contest/1870/submission/224161992
In
1870B - Friendly Arrays, why are we so sure that we will be using allb[j], maybe there is a case where using only one element fromb[]gives us a min and max XOR respectively. Or am I reading the question wrong, because the question only says "You can choose any elementbjfrom array b (1≤j≤m), and for all 1≤i≤n performai=ai|bjfor allbiYou can perform any number of such operations."Performing more OR with a number turns more bit ON(1), which will increase the number. And we have to perform OR to all a[i], so after performing the operations all a[i] will become same(lets say it is x). Now, we know that if there are even no. of x's, the xor will be 0. Thus if the array length of a is odd, the xor will be x(which will give maximum possible value) otherwise it will be 0(which will give minimum possible value).
Lets consider a testcase
4 1 1 1 2 6 1
If we xor all the element of b with all the elements of a we get final array as 1 1 3 7. But in this case all a[i] are not the same.
Am i doing it missing something or have i interpreted the problem incorrectly?
hi, I am unable to understand the tutorial of problem C. I'll be really glad if someone could explain in more depth than the tutorial. Thanks.
Another (more complicated but still pretty cool) solution to G:
One of the initial ideas that I had was to define the value of a number which will be 2^v. Then if the sum of the values of all the numbers is = 2^m where m is the mex, then potentially we can create m.
This does not work though, because lets say we try to create m, and we have two (m — 1)'s. This, though has the same value sum as 0, 1, 2,.... m — 1, does not create m. This leads us to another definition: space. Let space be equal to the maximum number of is that we can have. This then gives us that after processing number i, x = 2 * x — min(x, cnt[i]). Then, if we compute the space of all i (in reverse) up to 0, the space must be equal to or less than the number of zeros we can create. Now, you can create a bunch of functions f(x), which essentially represents this: 2 * x — min(x, cnt[i]) for each i. Now, an issue is that we also need to count the number of zeros we can create. The number of zeros we can create is the number of this not in the range [1, m — 1] PLUS when calculating f(x), which x < cnt[i], we wont use cnt[i] — x numbers, and we can turn those into zeros aswell. This means we need to a datastructure to support the following: maintain f0(f1(f2(f3(...fn(x)...))) (where fi(x) is the space function for number i), but also the zeros, which will be g0(f1(x)) + g1(x) for the n = 2 case. We can simply do this with a segment tree. This leads to a solution (with a couple constant optimizations) that passes. The issue is, theoretically, if each of these functions that we maintain have size O(n) (which I do not this is true but not sure how to prove) re-merging all of the functions every time an update happens should theoretically be O(n). This can be fixed with sqrt decomp, splitting it up into sqrt(n) functions, where to compute the final answer we use binary search on each of those functions. Every update is O(sqrt(n)) but every query is O(sqrt(n) log n) because of binary search, but this, with optimal blocking will result in O(sqrt(n log n)) (the logn factor is quite optimal because its simple binary search on an array). This leads to a slightly faster solution, saving around 150ms.
Without sqrt decomp: 224529457
With sqrt decomp: 224527332
where is the code
I have implemented Problem D using stack.
Can someone help me in finding a test case for which my solution fails.
Approach: Go from right and take the element that can give maximum buys. After that if there is a remainder, take 1 less buy and try to recursively again find an element from the right that gives maximum buy. Do this till we have k >= 0 or we don't repeat a number.
One can solve D recursively:
Now, upgrading to an index $$$j$$$ further to the right costs $$$c_j-c_i$$$.