Very interesting competition!

Thanks to Vladosiya and your team!

I have an idea to solve G in another way (a bit complicated). Height of vertex = value of vertex The best way from point $$$a$$$ to $$$b$$$ by traversing vertexex with minimum values. So, we can make a tree/forest (if graph is not connected) on our graph and use only simple paths to move between vertexes. We sort our vertexes by value. Maintain DSU. Iterate every edge of every vertex and add edge if vertex are in diffrerent unions.
Our query is reformulated: check if maximum of value of every vertex on simple path between $$$a$$$ and $$$b$$$ is smaller or equal to $$$value[a]$$$ + $$$energy$$$. If $$$a$$$ and $$$b$$$ are in different unions then path does not exists. It could be done by finding $$$c = lca(a,b)$$$. We divided our task to find maximum on path between $$$a$$$ and $$$c$$$, and on path between $$$b$$$ and $$$c$$$. And resulting maximum will be maximum from these. To find LCA and maximum on path between $$$a,b$$$ and $$$lca(a,b)$$$ we can use binary lifting.

I nearly got F. I know there is something to do with sorting but don't have enough time to implement it

Why problem E doesn't have cycles? I read E description for very long time but still don't know why :(

In problem F can also be understood using equation

$$$a+b = a ⊕ b+ 2*(a$$$&$$$b)$$$

$$$a = a_{i} ⊕x$$$

$$$b = a_{j} ⊕x$$$

$$$ \large \frac{(a_{i} ⊕x) + (a_{j} ⊕x) - (a_{i} ⊕x ⊕a_{j} ⊕x)}{2} = \frac{(a_{i} ⊕x) + (a_{j} ⊕x) - (a_{i} ⊕a_{j} )}{2} $$$

So we need to get min pair xor and $$$x$$$ which increases positive term.

G can be solved online using persistent DSU, which also allows us to solve the problem of finding the minimum energy needed to go from $$$a$$$ to $$$b$$$ in $$$O(\log n)$$$.

Submission

In my solution of D I have used slightly different checks to determine if the original array was a permutation.

Let's assume we already know that the deleted element isn't the last one — it's either the first one or some element in the middle (same as in the editorial).

• For the original array to be a permutation there can't be two differences of 1 in the prefix array (we can't reduce a 1 to any other difference by inserting an element back to the prefix array).
• Given array of prefix sums can either have at most one difference bigger than n, or at most 2 equal differences (we need to insert back at least one element to fix either one of those, so if we have to insert more than one element, the original array isn't a permutation).

I don't know how to prove that these 2 conditions are sufficient for the original array be a permutation, but apparently this is enough, my submission: 215583206

Someone please explain the secret solution of div2F mentioned in editorial.. what are AVX instructions ? :)

unordered_map gives TLE while map works

Can someone help me understand why using unordered_map fails(TLE on case 13) but using map works in problem D. The logic in my code is to find answer based upon the occurance of a difference between adjacent elements > n and any repeated differences. I know that average time complexity for unordered_map is O(1) while in worst case it is O(n) and average for map is O(log n), however I always thought that using unordered_map is faster due to better average. What am I missing? My submission using unordered_map — 215744161 My submission using map — 215746951 Both the codes are same except the usage of map instead of unordered_map

I thought editorial of D would have a better solution.

Is the solution 2 for F correct? Consider the case: 1 (0b000001), 31 (0b011111), and 32 (0b100000), with k = 6: Here the answer is ai=1, aj=32. If we look at a(i+1), it has a very high (non-minimal) xor with both aj and ai and the answer is not the adjacent numbers after sorting.

good div 3!!

but...i think problem A need to be easier to understand TvT

For problem F, I don't think solution 3 passes, as you typed O(n^2/16), or is it just a typo of the time complexity? Thanks.

How can we use AVX instructions to solve 1851F?

For problem E, since there can't be any cycles, the problem can also be solved by first doing a topological sort. And then a DP in that order, because for all $$$i$$$ we have already computed the answer for the potions it can be mixed by (namely some $$$j$$$ where $$$j < i$$$).

(And great competition, thank you Vladosiya and team!)

Solution of problem E using Trie.
algorithm -> Before inserting a element into the TRIE we check the minimum xor we can form using the current element and the previous element inserted int the TRIE.
We can also construct the other element and the number X(the element which satisfies the inqquality (ai⊕x)&(aj⊕x) ) while traversing the TRIE.

submission Link : link

I think F was Google-able, but I didn't have the insight to try it in the contest. Great contest! (if not a little frustrating)

I tried coding this $$$O(n^2/16)$$$ solution to problem F using AVX instructions. However its taking 2.14s for 1.5e5 elements, but barely blowing the 3s TL for 2e5. Can anyone think of any optimizations?

https://codeforces.net/contest/1851/submission/215775069

Update: After only saving the block indices that gave the minimum (not the element indicies) and then reiterating separately though these two blocks, I managed to save just enough operations.

$$$O(n^2/16)$$$ AC: https://codeforces.net/contest/1851/submission/215791929

Has anyone solved F with a binary search(n log(n))?

Someone please help me. This 215826166 really drives me crazy. I got tens of Runtime Error with GUN C++ 20 because of exit code: -1073741819 (STATUS_ACCESS_VIOLATION) but the same code could be Accepted with MS C++ 2017. I can't figure out why.

I have an approach similar to solution-$$$2$$$ for Problem F but we don't need to sort.

Here is my solution.

Greedy solution for F:

We need to find value = (a[i] ^ x) & (a[j] ^ x). Note that a[i] & value removes bits that do not affect the answer. Let's find value greedily starting from the highest bits. All we need to do is make sure that after adding next 1 bit, there is still at least two different i that produce a[i] & (value | (1 << u)).

int value = 0;
for (int u = k - 1; u >= 0; --u) {
    map<int, int> q;
    for (int i = 0; i < n; ++i) {
        if (++q[a[i] & (value | (1 << u))] > 1) {
            value |= (1 << u);
        }
    }
}
map<int, int> q;
for (int i = 0; i < n; ++i) {
    int y = a[i] & value;
    if (q.count(y)) {
        cout << i + 1 << " " << q[y] + 1 << " " << (value ^ y) << "\n";
        return;
    }
    q[y] = i;
}

Anyone whose E shows runtime error on test case 12[python]

I have another solution for problem F. It relies on the fact that for any bit, if it is on or off in both the numbers we choose, than that bit will be on in the number we try to maximise. With this in mind we can define a recursive function that for some maximal suffix of bits of the number we try to maximse, keeps track of all the numbers with that suffix and which of those numbers have the next bit set to 0 and which bit set to 1 tries to turn on the next bit in the solution or just skip it if it is not possible (this happens when there are 0 or 1 numbers with the next bit being 0 and 0 or 1 numbers with the next bit being 1). This results in a solution of complexity O(nk). Here is my code: https://codeforces.net/contest/1851/submission/216012524

For task E, you can simply write a recursion

Very good contest! I learned a lot of new knowledge.

can anyone plz tell in problem g why cant we just simply perform dfs starting from a and check whether we are able to ever reach b or not with the necessary checks of energy .

Is there some tutorial for bitwise trie data structure from problem F? It's hard for me to understand the official solution.

Problem E,It is guaranteed that no potion can be obtained from itself through one or more mixing processes. but in 1st example case 3,potion 1 can be obtained from 2,4,5 , and potion 4 can be obtained from 1,5, doesn't that make 1 and 4 a circle???

I am Chinese.This competition is very interesting.I like it very much.It is gooder than luogu.

For F, the Python trie-based solution is very hard to make pass under the constraints (I searched a bit in AC solutions, did not find one). I did not manage to make mine pass, and ended up submitting the same algorithm in C++ to get AC.