#	User	Rating
1	ecnerwala	3649
2	Benq	3581
3	jiangly	3578
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	tourist	3565
8	maroonrk	3531
9	Radewoosh	3521
10	Um_nik	3482

#	User	Contrib.
1	maomao90	174
2	awoo	164
3	adamant	161
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	SecondThread	147
9	orz	146
10	pajenegod	145

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define eb emplace_back



void solve() {
    int n,m,k,H; cin >> n >> m >> k >> H;
    int ans = 0;
    forn(i, n) {
        int x; cin >> x;
        ans += (H != x) && abs(H - x) % k == 0 && abs(H-x) <= (m-1) * k;
    }
    cout << ans << endl;
}

int main() {
    int t;
    cin >> t;

    forn(tt, t) {
        solve();
    }
}

1851B - Parity Sort

Idea: Vladosiya, prepared: myav

Tutorial

Solution

#include<bits/stdc++.h>
using namespace std;

bool solve(){
    int n;
    cin >> n;
    vector<int>a(n), b(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b.begin(), b.end());
    for(int i = 0; i < n; i++){
        if((a[i] % 2) != (b[i] % 2)) return false;
    }
    return true;

}

int main(){
    int t;
    cin >> t;
    while(t--){
        cout << (solve() ? "YES" : "NO") << "\n";
    }
    return 0;
}

1851C - Tiles Comeback

Idea: Vladosiya, prepared: myav

Tutorial

Solution

#include "bits/stdc++.h"
using namespace std;

bool solve(){
    int n, k;
    cin >> n >> k;
    vector<int>c(n);
    for(int i = 0; i < n; i++) cin >> c[i];
    int left = 0, right = 0, i = 0, j = n - 1;
    int k_left = k, k_right = k;

    if (c[0] == c[n - 1]){
        k_left = k / 2;
        k_right = k - k_left;
    }
    for(; i < n && left < k_left; i++){
        if(c[i] == c[0]) left++;
    }
    for(; j >= 0 && right < k_right; j--){
        if(c[j] == c[n - 1]) right++;
    }
    return (i - 1) < (j + 1);
}

int main(){
    int t;
    cin >> t;
    while(t--){
        cout << (solve() ? "YES" : "NO") << "\n";
    }

}

1851D - Prefix Permutation Sums

Idea: Gornak40, prepared: senjougaharin

Tutorial

Solution

#include <iostream>
#include <vector>
#include <set>
#include <map>

using namespace std;

typedef long long ll;

ll n;

bool isPermutation(vector<ll> a) {
    for (int i = 0; i < n; ++i) {
        if (a[i] <= 0 || a[i] > n) {
            return false;
        }
    }
    set<ll> s(a.begin(), a.end());
    return s.size() == n;
}

vector<ll> prefSumToArray(vector<ll> p) {
    vector<ll> res(n);
    res[0] = p[0];
    for (int i = 1; i < n; ++i) {
        res[i] = p[i] - p[i - 1];
    }
    return res;
}

void solve() {
    cin >> n;
    vector<ll> a(n - 1);
    for (int i = 0; i + 1 < n; ++i) {
        cin >> a[i];
    }
    ll x = n * (n + 1) / 2;
    if (a.back() != x) {
        a.push_back(x);
        vector<ll> b = prefSumToArray(a);
        if (isPermutation(b)) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
        return;
    }
    map<ll, int> cnt;
    cnt[a[0]]++;
    for (int i = 1; i < n - 1; ++i) {
        cnt[a[i] - a[i - 1]]++;
    }
    vector<int> cntGt1;
    for (auto p: cnt) {
        if (p.second > 1) {
            cntGt1.push_back(p.first);
        }
    }
    if (cntGt1.size() > 1) {
        cout << "NO\n";
        return;
    }
    if (cntGt1.size() == 1) {
        int x1 = cntGt1[0];
        if (cnt[x1] > 2) {
            cout << "NO\n";
            return;
        }
    }
    vector<int> cnt0;
    for (int i = 1; i <= n; ++i) {
        if (cnt[i] == 0) {
            cnt0.push_back(i);
        }
    }
    if (cnt0.size() != 2) {
        cout << "NO\n";
        return;
    }
    cout << "YES\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        solve();
    }
    return 0;
}

1851E - Nastya and Potions

Idea: Vladosiya, prepared: Vladosiya

Tutorial

Solution

#include <bits/stdc++.h>

#define int long long

using namespace std;

vector<int> dp;
vector<bool> used;
vector<vector<int>> sl;

int get(int v){
    if(used[v]){
        return dp[v];
    }
    used[v] = true;
    int s = 0;
    for(int u: sl[v]){
        s += get(u);
    }
    if(!sl[v].empty()) dp[v] = min(dp[v], s);
    return dp[v];
}

void solve(int tc) {
    int n, k;
    cin >> n >> k;
    dp.resize(n);
    used.assign(n, false);
    sl.assign(n, vector<int>(0));
    for(int &e: dp) cin >> e;
    for(int i = 0; i < k; ++i){
        int e;
        cin >> e;
        dp[--e] = 0;
    }
    for(int i = 0; i < n; ++i){
        int m;
        cin >> m;
        sl[i].resize(m);
        for(int &e: sl[i]){
            cin >> e;
            --e;
        }
    }
    for(int i = 0; i < n; ++i){
        get(i);
    }
    for(int e: dp) cout << e << " ";
}

bool multi = true;

signed main() {
    int t = 1;
    if(multi) cin >> t;
    for (int i = 1; i <= t; ++i) {
        solve(i);
        cout << "\n";
    }
    return 0;
}

1851F - Lisa and the Martians

Idea: Gornak40, prepared: Gornak40

Tutorial

Solution

#include <bits/stdc++.h>
#define all(arr) arr.begin(), arr.end()

using namespace std;

const int MAXN = 200200;
const int MAXK = 30;
const int MAXMEM = MAXN * MAXK;

mt19937 rng(07062006);

struct node {
	node *chi[2] {nullptr};
	int sz = 0, id = -1;
};

int n, k;
int arr[MAXN];
node *mem = new node[MAXMEM];
node *root, *mpos;

void add_num(node* &v, int val, int i, int id) {
	if (v == nullptr) *(v = mpos++) = node();
	v->sz++;
	if (i == -1) {
		v->id = id;
		return;
	}
	add_num(v->chi[val >> i & 1], val, i - 1, id);
}

int down(node *v, int val, int i, int &x, int &jans) {
	if (i == -1) {
		jans = v->id;
		return 0;
	}
	int b = val >> i & 1;
	if (v->chi[b])
		return down(v->chi[b], val, i - 1, x ^= ((1 ^ b) << i), jans) | (1 << i);
	return down(v->chi[b ^ 1], val, i - 1, x ^= ((rng() & 1) << i), jans);
}

void build() {
	root = nullptr;
	mpos = mem;
	add_num(root, *arr, k - 1, 0);
}

tuple<int, int, int> solve() {
	int ians = 0, jans = 1, xans = 0;
	for (int i = 1; i < n; ++i) {
		int x = 0, j = -1;
		int cur = down(root, arr[i], k - 1, x, j);
		if (cur > ((arr[ians] ^ xans) & (arr[jans] ^ xans)))
			ians = j, jans = i, xans = x;
		add_num(root, arr[i], k - 1, i);
	}
	return {ians, jans, xans};
}

int main() {
	int t; cin >> t;
	while (t--) {
		cin >> n >> k;
		for (int i = 0; i < n; ++i)
			cin >> arr[i];
		build();
		auto [ians, jans, xans] = solve();
		cout << ++ians << ' ' << ++jans << ' ' << xans << endl;
	}
}

1851G - Vlad and the Mountains

Idea: Vladosiya, prepared: Vladosiya

Tutorial

Solution

#include <bits/stdc++.h>

#define x first
#define y second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

typedef long double ld;
typedef long long ll;

using namespace std;

struct dsu{
    vector<int> p, lvl;

    dsu(int n){
        p.resize(n);
        lvl.assign(n, 0);
        iota(all(p), 0);
    }

    int get(int i){
        if(i == p[i]) return i;
        return p[i] = get(p[i]);
    }

    bool unite(int a, int b){
        a = get(a);
        b = get(b);
        if(a == b){
            return false;
        }
        if(lvl[a] < lvl[b])swap(a, b);
        p[b] = a;
        if(lvl[a] == lvl[b]){
            ++lvl[a];
        }
        return true;
    }

    bool reachable(int a, int b){
        return get(a) == get(b);
    }
};

void solve(int tc) {
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> h(n);
    for(auto &e: h) cin >> e.x;
    for(int i = 0; i < n; ++i){
        h[i].y = i;
    }
    dsu graph(n);
    vector<vector<int>> sl(n);
    for(int i = 0; i < m; ++i){
        int u, v;
        cin >> u >> v;
        --u, --v;
        if(h[u].x > h[v].x) sl[u].emplace_back(v);
        else sl[v].emplace_back(u);
    }
    int q;
    cin >> q;
    vector<pair<pair<int, int>, pair<int, int>>> req(q);
    for(auto &e: req){
        cin >> e.y.x >> e.y.y >> e.x.x;
        --e.y.x, --e.y.y;
        e.x.x += h[e.y.x].x;
    }
    for(int i = 0; i < q; ++i){
        req[i].x.y = i;
    }

    sort(all(h));
    sort(all(req));
    vector<bool> ans(q);
    int j = 0;
    for(auto e: req){
        while (j < n && h[j].x <= e.x.x) {
            for(int u: sl[h[j].y]){
                graph.unite(h[j].y, u);
            }
            ++j;
        }
        ans[e.x.y] = graph.reachable(e.y.x, e.y.y);
    }
    for(bool e: ans) cout << (e? "YES": "NO") << "\n";
}

bool multi = true;

signed main() {
    int t = 1;
    if(multi) cin >> t;
    for (int i = 1; i <= t; ++i) {
        solve(i);
        if(i < t) cout << "\n";
    }
    return 0;
}

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; }

vector<int> cntGt1; for (auto p: cnt) { if (p.second > 1) { cntGt1.push_back(p.first); } } if (cntGt1.size() > 1) { cout << "NO\n"; return; } if (cntGt1.size() == 1) { int x1 = cntGt1[0]; if (cnt[x1] > 2) { cout << "NO\n"; return; }

include

using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pl; typedef vector vi; typedef vector vll; typedef vector vpii; typedef vector vpl; typedef vector vvi; typedef vector vvll; typedef vector vs; typedef vector<vector> vvll; typedef map<ll,bool> mllb; typedef unordered_set ucst; typedef unordered_map<ll,bool> umllb;

define mp make_pair

const ll mod=10e9+7;

bool solve() { ll n; cin>>n; int m=n-1; vll arr(n-1); ll permSum=n*(n+1)/2; for(ll& x: arr) { cin>>x; }

for(auto x: arr) { if(x>permSum) { return false; } } if(arr[m-1]>permSum) { //Not a permutation return false; } else if(arr[m-1]<permSum) { //Last element missing in prefix sum arr.push_back(permSum); unordered_map<ll,ll> mp; for(int i=n-1;i>0;i--) { mp[arr[i]-arr[i-1]]++; } mp[arr[0]]++; for(ll i=1;i<=n;i++) { if(mp[i]==0) { return false; } else if(mp[i]>1) { return false; } } return true; } else { //First or middle element deleted arr.insert(arr.begin(),0); unordered_map<ll,ll> mp; for(ll i=n-1;i>0;i--) { mp[arr[i]-arr[i-1]]++; } vector<ll> missing; for(ll i=1;i<=n;i++) { if(mp.find(i)==mp.end()) { missing.push_back(i); } } if(missing.size()>2) { return false; } if(missing[0]+missing[1]>n && mp[missing[0]+missing[1]]==1) { return true; } else if(missing[0]+missing[1]<=n && mp[missing[0]+missing[1]]==2) { return true; } else { return false; } }

}

int main() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); ll t; cin>>t; //t=1; while(t--) { if(solve()) cout<<"YES"<<endl; else cout<<"NO"<<endl; //solve(); //cout<<solve()<<endl; }

return 0;

}

Comments (92)

Write comment?

The_Boys_Word

9 months ago, # |

Very interesting competition!

Thanks to Vladosiya and your team!

→ Reply

Narendramaddigunta

I am stuck at the first question itself for a while

MiyawakiSakura

9 months ago, # ^ |

It was quite hard to read, but the idea at least was simple

Danzev

← Rev. 2 →

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.

jaredsu0719

I just got TLE in test 9 (5 sec) time complexity should be O(nlogn+qlogn) Not sure what's going wrong

IHOPEIDIEYOUNG

Me too. Any idea?

Hey, Try adding #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

I got it accepted thru this.

vuhuydiet

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

Sean6

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

ready_take-off

+20

It is guaranteed that no potion can be obtained from itself through one or more mixing processes.

comingsoon.cpp

-17

How you take know? The reason wey I dey ask be sey most of Una dey like to talk things wey be sey no dey correct at times

pratikshaw

For problem E, Is it possible to have the following criteria

1 needs 4 and 5 for mixing & 2 needs 1 and 5 for mixing.

For 1, we already have 5 included, so how will that affect the answer for 2 which has both 1 and 5. Is such a case even possible , if yes , how will the answer be calculated (adding both 1 and 5 or only 1)?

BeanBurrito

That is valid.

Find cost of 4 and 5, now you have the cost for 1. Use the cost of 1 and 5 to get the cost for 2.

+10

"Moreover, no potion can be obtained from itself through one or more mixing processes." here it is

"It is guaranteed that no potion can be obtained from itself through one or more mixing processes." This statement means that agent i cannot be mixed directly or indirectly by Agent i(that is, itself)

thank you, seems like I need to improve my English reading skill...

KushagrJaiswal

Oh man... This "one or more mixing processes" got me.

I definitely need to get used to problem statements on Codeforces.

jpalayoor

bruh my solution for C would have worked if i didnt put nums2 instead of nums1 at https://codeforces.com/contest/1851/submission/215591370

working solution: https://codeforces.com/contest/1851/submission/215744363

wasted :(

is alright tho learnt that i always have to double check my code

udta_kouwa

← Rev. 5 →

+11

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.

NeoYL

this is cool, but I dont really know how to find x. Then I saw a lot of people do like ((1 << k) — 1) ^ (a[i] | a[i-1]); after sorting. can anyone explain this a bit?

electric_boogaloo

We know that all given numbers are strictly less than $$$2^k$$$, so the biggest possible number with the most bits (exactly k bits) set to 1 is equal to $$$2^k - 1$$$, to maximize our expression (a[i] ^ x)&(a[i-1] ^ x) we intuitively want to set to 1 only those bits in x that do not occur either in a[i] or a[i — 1] (and bits that do occur both in a[i] and a[i-1] are the result of the logical or of a[i] and a[i-1]).

ok got it, thx

t1400

i figured this out but it is giving tle. what are avx instructions that tutorial mentions??

logicAn

7 months ago, # ^ |

have you got the answer bro?

Arnur2937

bro, you are the best, thanks!!

ahsoltan

+16

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

canvas_melody

Can you explain the algorithm you used in short please? I read about persistent DSU but I didn't see standard unite and find_set functions in your dsu and also what does the upper_bound at the end signify?

Here is my implementation of persistent DSU:

For each set, store its elements. Instead of storing the parent of each element store a vector of pairs $$$(time, parent)$$$. Since we want the length of the path from each element to its root to always be 1, when merging two sets update the parent of each element in the smaller set. This results in an amortized space and time complexity of $$$O(n \log n)$$$.

Proof of complexity

To get the root of an element at time $$$t$$$ we can simply binary search to find the last $$$(time, parent)$$$ entry with $$$time \le t$$$.

Thanks a lot!

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

Xarma

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

-ved-ansh-

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

Please refer to the classic blowing up an unordered_map

Thank you!

Hard_2_FaceReality

I thought editorial of D would have a better solution.

Krzychuo

You can check my submission for easier to understand and implement solution. Main idea is very similiar to the one in editorial. If last element was removed from prefix array, then we end up with permutation without 1 element, and if remove other element, then we will end up with permutation without 2 elements and a special element which should be the sum of missing elements of mentioned permutation.

kgb_70

can we simply solve e with simple array based approach. just trying to update values to 0 for potions which r unlimited and then calculate cost, and simply give the output by comparing.

I think here, when we get some potion is unlimited by mixing other unlimited potions, then this will affect other similar potions so this would be a tree. Also, when we buy a potion, we get unlimited quantities of that potion too (I had misunderstood this during contest)

2am

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.

Spoiler (my understanding)

You're right about minimizing $$$a_i$$$ ^ $$$a_j$$$ part, but your example is wrong: 1^31 < 1^32

Thanks, I made a very silly mistake there, blinded by maximizing the matching bits and ignoring their values

Yumesekai

good div 3!!

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

tosivanmak

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.

Flvx

How can we use AVX instructions to solve 1851F?

liusususu

-8

I feel that I have considered the d question comprehensively, but it's just not right. I'm so sad :（

__yannick__

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

Meanwhile you can perform a topological sort on a DAG, in case of a problem like this you don't need to. You can just traverse all the unvisited nodes with a simple dfs in a "topological sort"-like manner, compute the answer for each unvisited node based on prices of its children, memorize the answer (one of the main points of dp) and move onto the rest of the nodes.

Because that's exactly what I did during the contest — wrote a topological sort on autopilot and didn't even use it afterwards (how silly of me).

If by an array based approach you mean this solution: 215678317, then I don't think your approach is correct, namely, there are a couple of inaccuracies that stick out to me right away:

You have multiple nested loops in your solution, which leads to at least $$$O(n^3 + k \cdot n^2)$$$ time complexity
You seem to process all queries "online", i.e. you try to reduce prices for all potions after reading each new recipe
I don't think you are reading the recipes in the right format

Try to draw a couple of test examples on paper, look at what kind of graphs do you get and try to proceed from there.

expertaq

← Rev. 4 →

In F, we can actually prove that we need minimum XOR pair, let Ai = A and Aj =B and x = X (A ^ X).(B^X) = (AX' + A'X)(BX' + B'X) = ABX' + A'B'X From this, we can deduce that for whatever A and B, there exists X that can give a maximum value so, we only need to calculate the maximum value of AB + A'B' which is basically XNOR. Hence we need to calculate the minimum of XOR of all pair.

puspendra_09

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

register2601

I need to code all 3 solutions for problem F

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)

Djangoo

can anyone help me in problem D?

https://codeforces.com/contest/1851/submission/215772754

wa in test case 3

MatheusAB

← Rev. 3 →

+25

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.com/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.com/contest/1851/submission/215791929

BF_OF_Priety

curious to know how did you learn this AVX instructions thing and why?

I dont really know AVX instructions (discovered it today).

When I saw the editorial, I searched and found this blog https://codeforces.com/blog/entry/98594. After reading it, I implemented a solution using __m128 (which is $$$O(n^2/8)$$$ here). Later, googling a bit about 256 bit AVX, found more instructions and finally managed to optimize enough to pass.

Why? No specific reason, guess I like playing around with these things on my spare time. It probably doesn't help me in CP though.

Bucketsmith

Thank you for the link! You saved my day, I googled "AVL Instructions" only to find some pragma stuffs.

Noluck_167

How unlucky you are-> My honest reaction: my solution= 215621385 and my submission just after the contest after just adding two brackets in if(i!=H) condition 215624902

_MASTER__

My thoughts and solution for F:

We can check by the truth table that we will get a plus in our final value if the $$$i$$$'th bit in $$$a$$$ and $$$b$$$ are equal (0 and 0) or (1 and 1). So, the final value is for each two values inside the array our value is: $$$\sum_{i=0}^{k-1} ((\text{ith bit of } a \text{ and } b \text{ equals to each other}) \ll i)$$$.

So, the final output will be the indices of $$$a$$$ and $$$b$$$ that will give us the maximum value. We can notice that our sum is equivalent to: $$$2^{k} - 1 - \sum_{i=0}^{k-1} ((\text{ith bit of } a \neq \text{ith bit of } b) \ll i)$$$.

Additionally, we can observe that $$$\sum_{i=0}^{k-1} ((\text{ith bit of } a \neq \text{ith bit of } b) \ll i)$$$ is the definition of $$$a \oplus b$$$ (the bitwise XOR operation between $$$a$$$ and $$$b$$$).

So, how do we maximize our sum? We need to minimize the XOR, right? To do so, I know (from previous problems) that the minimum XOR occurs from a pair of values in the given array (but sorted).

so we just do that :).

sort the given array, get the minimum xor and build the X accordingly. my submission: 215782665

TsupaRoman

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

Forestmy17

what?maybe you didn't find me in dm Because I added restriction that atleast LGMs can text me , now changed that to 'allow all'

shanks333

can someone please explain me question D.

xy_yx

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 got it. It's actually a common problem in C++ when sorting if two elements are equal the result should be false!

byte0010

Can someone explain why my soln to E 215608832 throws a runtime error on test 12

humblebose

mine too.[python]

ishwarendra

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

Here is my solution.

bad_imagination

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

ayush002024

Another opportunity to feel ashamed

Md_Abu_Taleb

Thanks for memorable contest first time touch pupil

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

dino_merlin

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.com/contest/1851/submission/216012524

star25light

For task E, you can simply write a recursion

youthPaul

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

PoLaRbEaR_

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 .

vitosevskich

Because that would be too slow. In that case we will maybe visit all mountains in every query.

thank you got it

olegmak

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

yyash8000

in ques A why do we need to check if the vlag height(H) and escsalator person's height[i] is equal or not

vizzy205

8 months ago, # |

in question A, I didn't understand the statement: "the difference between the extreme steps should not exceed the difference in height." why is this condition considered?

Lint_Whoppers

THese condition in question D is useless

SPcoder2000

Way too many edge cases for D.

My solution:-

define PI 3.1415926535897932384626

define pb push_back

TheDarkKnight03

If anyone was curious, yes 1851E can be solved using modified dijkstra https://codeforces.com/contest/1851/submission/220974558

aks013

7 months ago, # |

Hi, for problem E, why does the below code gives TLE but the tutorial solution works?

223600037

leducphuclong

You just need to do like this for prob B. Thank you for the contest but I hope you will do better editorial next time.

https://pastie.io/hccsrs.cpp

man-ray

5 months ago, # |

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???

vgtcross

5 months ago, # ^ |

+12

Are you talking about this test case?

Read the statement again:

"This is followed by $$$n$$$ lines describing ways to obtain potions by mixing.

Each line starts with the integer $$$m_i$$$ ($$$0\le m_i < n$$$) — the number of potions required to mix a potion of the type $$$i$$$ ($$$1\le i\le n$$$).

Then line contains $$$m_i$$$ distinct integers $$$e_1,e_2,\dots,e_{m_i}$$$ ($$$1\le e_j\le n, e_j\ne i)$$$ — the indices of potions needed to mix a potion of the type $$$i$$$. If this list is empty, then a potion of the type $$$i$$$ can only be bought."

The first integer on those lines is is the number of remaining integers on that line, it's not one of the potions. Potion $$$1$$$ can be made from potions $$$\{2, 5\}$$$, potion $$$4$$$ can be made from potion $$$\{5\}$$$.

oh I thought the first digit of each line is a potion,thanks for replying!!!

hmlegend

2 months ago, # |

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

Vladosiya's blog

include

include

include

include

include

include

include

include

define PI 3.1415926535897932384626

define pb push_back

define mp make_pair