Video Solution for Problem C

For minimum, for each $$$a_i$$$, we look for the smallest $$$b_j$$$ such that $$$b_j \geq a_i$$$. Note that $$$j \leq i$$$ (since it must always be valid to map $$$a_i$$$ to $$$b_j$$$). It's valid to map $$$a_i$$$ to $$$b_j$$$ because the elements between $$$a_j$$$ to $$$a_{i - 1}$$$ can be mapped to the elements $$$b_{j + 1}$$$ to $$$b_i$$$. Obviously, we can't map $$$a_i$$$ to anything smaller than $$$b_j$$$. So the minimum $$$d_i = b_j - a_i$$$, where $$$b_j$$$ is the smallest element in $$$b$$$ that's $$$\geq a_i$$$.

Maximum is trickier. Consider the first index $$$i$$$ where $$$a_{i + 1} > b_i$$$. Now for each $$$j \leq i$$$, I claim there will always exist a valid mapping from $$$a_i$$$ to $$$b_i$$$. Proof: For $$$j < i$$$, we can simply map elements $$$a_i$$$ and below to $$$b_{i - 1}$$$ and below (since $$$i + 1$$$ is the first index where we can't do this) until we reach $$$a_j$$$, which we can map to $$$b_i$$$.

Furthermore, $$$b_i$$$ is the maximum choice for $$$a_j$$$ because $$$a_{i + 1}$$$ and above cannot map to $$$b_i$$$ and below, so by pigeonhole principle, the elements from $$$b_{i + 1}$$$ and above can only be occupied by $$$a_{i + 1}$$$ and above. Therefore, $$$d_j = b_i - a_j$$$, where $$$i$$$ is the first index in which $$$a_{i + 1} > b_i$$$ and $$$j < i$$$. We can then treat $$$a_{i + 1}$$$ as the new start, and look for the next index of this property, and so on.

My submission: https://mirror.codeforces.com/contest/1721/submission/169851465

i thought it was dp and wasted alot of time then noticed test cases and then i thought for like 20 mins and ficured out greedy and then made a mistake with a bracket and waste another 30 mins and finally figured it out.

That would have taken way too much running time

You never want to go up or left. Now, any path, that can be cunstructed moving only right or down, will take you n + m — 2 steps to get to (n, m). So, i don't think, that Dijkstra or BFS is intended

It was my first idea as well but a quick glance at the bounds should immediately tell you that it's too slow. Since there's no "sum of $$$N$$$ is at most" condition and you can have up to $$$10^6$$$ cells to calculate distances too, the total runtime can get up to $$$10^{10}$$$ which is way too high.

Video Solution for Problem C

contrary test: a = {1 1 1 5}, b = {4 4 5 6}. Following your logic, mx[1] = 4, but it's actually 5

for minimum can we use lower_bound function??

same question here

Solve for bits from most significant to least significant.

For any bit b, iterate through a and store the prefix in a multiset. Set all bits to 0 except the bits you've already set, and of course, this current bit.

Iterate through b and try to find the inverse prefix in the multiset and remove it. Set all bits to 1 except the bits you've already set, and of course, the current bit.

(By inverse prefix, we mean the prefix that when xor'd with the key in the map will produce 1 on every bit. So to find an inverse prefix, take a prefix, and xor it with the 1-mask to get the actual prefix).

If the multiset has nothing left after you're done, you can set this bit. Store the info that this bit is already set and move on.

Probably my implementation will get hacked, but here it is: 169888210

You are missing

Really? The implementation is fairly straightforward (though somewhat long) if you use a set<pair<vector<int>, vector<int>>>

The issue is that while loop. Computing prefix function is amortized $$$\mathcal O(n)$$$, but when you have queries and can "rollback" some suffix of the string, you break the amortized analysis and devolve to $$$\mathcal O(nq)$$$.

I'm in the same situation as you.169890422

This is far from "clearly" $$$O(|s| + q|t|)$$$.

        else // (pat[i] != pat[len])
        {
            if (len != 0)
            {
                len = lps[len-1];
            }
            else // if (len == 0)
            {
                lps[i] = 0;
                i++;
            }
        }

Look at this code path. The len = lps[len - 1] line might happen many times as $$$i$$$ is not increased. The "vanilla" KMP will run in $$$O(|s|)$$$ because there is some amortized analysis saying it does. But now that you have all these different queries, it may happen that the parts of KMP that took a long time will happen every time.

you are too

Or there's no solution until now?

Your idea is correct. You can optimize it with 2 pointers technique.

Your algorithm is probably O(m*n). m and n can be up to 1000, and there can be up to 10^4 test cases. Worst case time complexity would be 1000 * 1000 * 10^4

https://leetcode.com/problems/minimum-cost-homecoming-of-a-robot-in-a-grid/ recalled when I made that mistake in this problem

But nethertheless, great round! Thanks for nice edu!

Make a check if the vectors are empty. In this case, don't push them into the set.

Don't add pairs of empty vectors.

Instead of copying divisions to new vectors, you can simply rearrange and operate on indices similar to quick sort partitioning.

Submission: https://mirror.codeforces.com/contest/1721/submission/169880265

I tried to solve it with the same idea. I also got TLE on test 4. I tried to make it better by using pairs of numbers that show a range on the first vectors. I am getting MLE on test 15. I have no idea why it is using so much memory. Can anyone help me understand why my code is using so much memory while it should use much less? (just a few vectors should not reach the max limit memory.)

https://mirror.codeforces.com/contest/1721/submission/169912449

edit: I got the problem. It was because I was pushing unnecessary pairs to my vector. just like pushing empty vectors.

Checking to see if you can achieve the bits before creating the new pairs would probably help. In your solution you potentially waste a lot of time pushing pairs of vectors into things and then discarding them.

One day you will not.

$$$x$$$-axis is from up to down almost always in CP.

Please no

I'd rather prefer they didn't use x for Y-axis coordinates

It probably only does checking for the each 2-query that the sum of edge indices matches the value printed on the last 1-query.

To check if the removal of a vertex results in a smaller maximum matching, it is sufficient to check that there is no alternating path from an unmatched vertex to its matched side (it doesn't matter which maximum matching we use for this check). This can be rephrased into dynamic connectivity.

Note that the checker doesn't need to be fully online, so there's lots of options for the problemsetter here. Whether the sum of edges is achievable is probably not tested, although there are some sums that are clearly not achievable, so there are at least some cases where a WA can be created this way.

It was kinda painful to implement.

The interactor doesn't check everything, but it checks a lot. First of all, the fact that deleting a subset of vertices decreases the matching is checked using the following assumptions:

• it is always possible to remove just one vertex, so if the participant removes more, then he gets WA;
• suppose the participant has removed $$$k$$$ vertices. Then the matching should be decreased by $$$1$$$ with each deletion; but since deleting a vertex can reduce the matching at most by $$$1$$$, then it's enough to check that the matching in the resulting graph is reduced exactly by $$$k$$$. If it is so, then every operation has decreased the matching; if it is not, then the answer to some query was wrong. So, the interactor doesn't need to check the matching after each query, it checks the matching only in the end.

Checking the sum of numbers in a matching is not perfect. You can, for example, print that the sum of edges is -1e18, and the interactor won't mind it. It relies on the fact that your solution doesn't know the moment when it has to process the query of type $$$2$$$ beforehand, so you can actually print some nonsense, but most probably you will get caught.

How to solve E?

Same :(

I thought about doing that, but I ultimately decided against that. I assume you mean binary searching on the answer, right? I didn't do that b/c I don't think it's guaranteed that if a value x works, then all values below x work.

Seems that if you can check whether answer $$$x$$$ is valid, you can get the optimal answer directly. So binary search is unnecessary.

Time Complexity for s.erase() is O(sizeof(set))

https://mirror.codeforces.com/blog/entry/20553

Here is a counter-example:

3
1 2 3
1 3 4

The maximum difference for $$$a_1$$$ should be 0. To see why, observe that $$$a_2 = 2$$$ cannot be mapped to $$$b_1 = 1$$$ (since $$$2 > 1$$$), which means that {$$$a_2, a_3$$$} must map to {$$$b_2, b_3$$$}. By the pigeonhole principle, this means $$$a_1$$$ can't map to {$$$b_2, b_3$$$}. Therefore, $$$a_1$$$ must be mapped to $$$b_1$$$ no matter what, so both the minimum and maximum $$$d_1$$$ are equal to $$$0$$$.

The error in your code is how you compute the maximum. Greedily picking the largest possible $$$k$$$, which only decrements if idx==k-1 or b[k-1] == b[idx] is insufficient. My approach, instead, was to find the next index $$$k$$$ for which $$$a_{k + 1} > b_k$$$, which means indices $$$\leq k$$$ cannot be mapped to $$$b_{k + 1}$$$ or above, but they can be mapped to $$$b_k$$$ instead, to yield the maximum possible difference.

Hope you can understand my submission easily ,and will find your mistake. 169935846

The third test-case provides a nice hint. If my explanation is too long, feel free to skip to the end for the algorithm steps.

Suppose the answer is $$$x$$$. Consider the leftmost 1 bit (MSB) of $$$x$$$. Let's say it's at position $$$k$$$. Elements of $$$a_i$$$ with a 0 in bit $$$k$$$ would be paired with a $$$b_i$$$ that has 1 in bit $$$k$$$, and vice versa. This means, if you were to sort $$$a$$$ according to bit $$$k$$$ only (ignoring all higher bit positions), and if you were to reverse-sort $$$b$$$ according to bit $$$k$$$ only, then the bitwise XOR of $$$a_i$$$ and $$$b_i$$$ will always yield a 1 in bit $$$k$$$.

Okay, so it's easy to find the first $$$1$$$ in $$$x$$$, but how do we find the next $$$1$$$? Let's say that the second 1 from the left in $$$x$$$ is at bit position $$$k'$$$. This time, it's not enough to look only at bit $$$k'$$$ to pair $$$0$$$s in $$$a$$$ with $$$1$$$s in $$$b$$$ and vice versa, because we also need to make sure the relationship in bit $$$k$$$ is preserved.

Essentially, bit $$$k$$$ partitions $$$a$$$ and $$$b$$$ into two (where the $$$0$$$-partition in $$$a$$$ has the same size as the $$$1$$$-partition in $$$b$$$ and vice versa) and then within each partition pair, we need to make sure bit $$$k'$$$ achieves a similar partition. It follows that if we

(a) sort $$$a$$$ according to bit $$$k$$$ and reverse-sort $$$b$$$ according to bit $$$k$$$ as mentioned before,

(b) for the partition in $$$a$$$ that has the same bit $$$k$$$, we sort these elements according to bit $$$k'$$$, while for the corresponding partition in $$$b$$$ with the opposite bit $$$k$$$, we reverse-sort these elements according to bit $$$k'$$$

Then the bitwise XOR between $$$a$$$ and $$$b$$$ should now have both bit $$$k$$$ and bit $$$k'$$$ yielding $$$1$$$s. This partition idea may sound complicated to implement, until you realize that this is basically how numbers are sorted anyway! Sort by the most significant bit first, and then for those with the same MSB, we sort by the second most significant bit, and so on. It's just plain sorting! The only difference is that we skip the bit positions in which we're not able to form such pairs (i.e., some partition formed by $$$a$$$ does not have the same size as the corresponding partition formed by $$$b$$$), where $$$x$$$ will have 0 in such bit positions. But if we ignore these bit positions, then a sorted $$$a$$$ will map perfectly to a reverse-sorted $$$b$$$.

This leads to the following algorithm:

1. Sort $$$a$$$ and reverse-sort $$$b$$$ (this automatically prioritizes the leftmost bit position)
2. For each bit position $$$k$$$, from leftmost to rightmost, check if the bits in position $$$k$$$ for ALL elements in $$$a$$$ are the opposite of the corresponding elements in $$$b$$$.

• If yes, we set the answer's bit $$$k$$$ to 1, because any arrangement of $$$a$$$ and $$$b$$$ that preserves this ordering of bit $$$k$$$ in their elements will produce a 1 in the bit $$$k$$$ of the answer.
• If no (at least one element of $$$a$$$ has the same bit $$$k$$$ as the corresponding element in $$$b$$$), then we clear bit $$$k$$$ to 0 for ALL elements of $$$a$$$ and $$$b$$$. Now we sort $$$a$$$ and reverse-sort $$$b$$$ again (does not have an impact on bit positions more significant than $$$k$$$, position $$$k$$$ itself is irrelevant, so the rearrangement considers $$$k - 1$$$ onwards)

My submission: https://mirror.codeforces.com/contest/1721/submission/169955540

Are you serious? Last edu round?

Dammn! at the border you're... Congrats for becoming unrated for upcoming Div4 LOL.

Alternatively, we can just enter each of the four characters into a set. The answer is the size of the set minus 1. 169957444

I haven't examined the code itself, but it seems you're calculating maximum incorrectly. Consider the following test-case:

3
1 2 3
1 3 4

The maximum difference for $$$a_1$$$ should be 0. To see why, observe that $$$a_2 = 2$$$ cannot be mapped to $$$b_1 = 1$$$ (since $$$2 > 1$$$), which means that {$$$a_2, a_3$$$} must map to {$$$b_2, b_3$$$}. By the pigeonhole principle, this means $$$a_1$$$ can't map to {$$$b_2, b_3$$$}. Therefore, $$$a_1$$$ must be mapped to $$$b_1$$$ no matter what, so both the minimum and maximum $$$d_1$$$ are equal to $$$0$$$.

I'm not sure what you were trying to do for maximum, but my approach was to find the next index $$$k$$$ for which $$$a_{k + 1} > b_k$$$, which means indices $$$\leq k$$$ cannot be mapped to $$$b_{k + 1}$$$ or above, but they can be mapped to $$$b_k$$$ instead, to yield the maximum possible difference. 169851465

I didn't understand your program code, but here is a counter-test:

2
1 1
1 2

The minimum values for $$$d_1$$$ and $$$d_2$$$ are both 0, since either of them can be mapped to $$$b_1 = 1$$$. You can find the minimum $$$d_i$$$ by simply looking for the smallest $$$b_j$$$ such that $$$b_j \geq a_i$$$.