Codeforces Round #845 (Div. 2) and ByteRace 2023 Editorial
Difference between en3 and en4, changed 2 character(s)
We hope you enjoyed the contest!. Thank you for your participation! Do vote under the Feedback section, and feel free to give your review of the problems in the comments.↵

---↵

[problem:1777A] <br>↵

Idea: [user:ShivanshJ,2023-01-21] <br>↵
Preparation: [user:ShivanshJ,2023-01-21] <br> ↵
Editorialist: [user:ShivanshJ,2023-01-21]↵

<spoiler summary="Hints">↵

<spoiler summary="Hint 1">↵
Try to make the problem simpler.↵
</spoiler>↵

<spoiler summary="Hint 2">↵
Parity?↵
</spoiler>↵

<spoiler summary="Hint 3">↵
Try replacing even numbers with $0$ and odd numbers with $1$ in other words consider all numbers modulo $2$.↵
</spoiler>↵

<spoiler summary="Hint 4">↵
Think harder! It works!↵
</spoiler>↵

</spoiler>↵


<spoiler summary="Solution">↵

[tutorial:1777A]↵
</spoiler>↵


<spoiler summary="Implementation (C++)">↵

~~~↵
                        /* Enjoying CP as always!*/↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define int long long↵

signed main() {↵
    ios_base::sync_with_stdio(false);↵
    cin.tie(NULL);↵
    int t;↵
    cin>>t;↵
    while(t--) {↵
        //Take input↵
        int n;↵
        cin>>n;↵
        int a[n];↵
        for(int i=0;i<n;i++) {↵
            cin>>a[i];↵
        }↵
        //initialize answer..↵
        int ans=0;↵
        for(int i=0;i+1<n;i++) {↵
            ans+=(!((a[i]^a[i+1])&1));↵
            /*XOR the two numbers and check 0th bit in the resultant, if it is 1↵
            then, numbers are of different parity, otherwise both are of same parity*/↵
        }↵
        cout<<ans<<"\n";↵
    }↵
    return 0;↵
}↵
~~~↵


</spoiler>↵

<spoiler summary="Implementation (Python)">↵

~~~↵
def main():↵
    T = int(input())↵
    while T > 0:↵
        T = T - 1↵
        n = int(input())↵
        a = [int(x) for x in input().split()]↵
        ans = 0↵
 ↵
        for i in range(1, n):↵
            ans += 1 - ((a[i] + a[i - 1]) & 1)↵
 ↵
        print(ans)↵
 ↵
 ↵
if __name__ == '__main__':↵
    main()↵
~~~↵

</spoiler>↵

<spoiler summary="Feedback">↵
- Good problem: [likes:1,option1]↵
- Average problem: [likes:1,option2]↵
- Bad problem: [likes:1,option3]↵
- Did not solve: [likes:1,option4]↵
</spoiler>↵

[problem:1777B] <br>↵

Idea: [user:TimeWarp101,2023-01-21] [user:quantau,2023-01-21] <br>↵
Preparation: [user:TimeWarp101,2023-01-21] <br>↵
Editorialist: [user:TimeWarp101,2023-01-21]↵

<spoiler summary="Hints">↵

<spoiler summary="Hint 1">↵
Will the answer differ for different permutations?↵
</spoiler>↵

<spoiler summary="Hint 2">↵
If you only look at 2 elements, how much will they contribute to the answer?↵
</spoiler>↵

</spoiler>↵


<spoiler summary="Solution">↵

[tutorial:1777B]↵
</spoiler>↵


<spoiler summary="Implementation (C++)">↵

~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define int long long↵
signed main()↵
{↵
    const int N = 1e5 + 5;↵
    const int mod = 1e9 + 7;↵
    vector<int> fact(N);↵
    fact[0] = 1;↵
    for(int i = 1; i < N; i++)↵
    {↵
        fact[i] = fact[i - 1] * i;↵
        fact[i] %= mod;↵
    }↵
    int t;↵
    cin >> t;↵
    while(t--)↵
    {↵
        int n;↵
        cin >> n;↵
        int ans = n * (n - 1);↵
        ans %= mod;↵
        ans = (ans * fact[n]) % mod;↵
        cout << ans << endl;↵
    }↵
    return 0;↵
}↵
~~~↵


</spoiler>↵

<spoiler summary="Implementation (Python)">↵

~~~↵
t = int(input())↵
for _ in range(t):↵
    n = int(input())↵
    nf = 1↵
    mod = int(1e9 + 7)↵
    for i in range(n):↵
        nf = nf * (i + 1)↵
        nf %= mod↵
    ans = n * (n - 1) * nf↵
    ans %= mod↵
    print(ans)↵
~~~↵

</spoiler>↵

<spoiler summary="Feedback">↵
- Good problem: [likes:2,option1]↵
- Average problem: [likes:2,option2]↵
- Bad problem: [likes:2,option3]↵
- Did not solve: [likes:2,option4]↵
</spoiler>↵

[problem:1777C] <br>↵

Idea: [user:quantau,2023-01-21] <br>↵
Preparation: [user:TimeWarp101,2023-01-21] [user:quantau,2023-01-21] <br>↵
Editorialist: [user:TimeWarp101,2023-01-21]↵

<spoiler summary="Hints">↵

<spoiler summary="Hint 1">↵
Would sorting the array help?↵
</spoiler>↵

<spoiler summary="Hint 2">↵
Would iterating over the factors help?↵
</spoiler>↵

<spoiler summary="Hint 3">↵
If the optimal team has students with maximum smartness $M$ and minimum smartness $m$, would having students with smartness $X$ such that $m
$ \le $X$ \le $M$ the answer will not change.↵
</spoiler>↵

<spoiler summary="Hint 4">↵
Two pointers?↵
</spoiler>↵

</spoiler>↵


<spoiler summary="Solution">↵

[tutorial:1777C]↵
</spoiler>↵


<spoiler summary="Implementation (C++)">↵

~~~↵
#include <bits/stdc++.h>↵
#define sz(x) x.size()↵
#define all(v) v.begin(), v.end()↵
#define rall(v) v.rbegin(), v.rend()↵
#define nl "\n";↵
#define dbg(i) cout << "HERE " << i << endl;↵
#define var(x, y, z) cout << x << " " << y << " " << z << endl;↵
#define ll long long int↵
#define pii pair<ll, ll>↵
#define pb push_back↵
#define ff first↵
#define ss second↵
#define on_bit(x) __builtin_popcountll(x)↵
#define msb(x) (63 - __builtin_clzll(x))↵
#define lsb(x) __builtin_ctzll(x)↵
#define FASTIO                \↵
    ios ::sync_with_stdio(0); \↵
    cin.tie(0);               \↵
    cout.tie(0);↵
#define FREOPEN                       \↵
    freopen("input.txt", "r", stdin); \↵
    freopen("output.txt", "w", stdout);↵
 ↵
using namespace std;↵
 ↵
const ll inf = 1e17;↵
const ll MAXM = 1e5;↵
vector<ll> factors[MAXM + 5];↵
 ↵
void init()↵
{↵
    for (ll i = 1; i <= MAXM; i++)↵
    {↵
        for (ll j = i; j <= MAXM; j += i)↵
        {↵
            factors[j].pb(i);↵
        }↵
    }↵
}↵
 ↵
void solve()↵
{↵
    ll n, m;↵
    cin >> n >> m;↵
    vector<pii> vec;↵
    for (ll i = 0; i < n; i++)↵
    {↵
        ll value;↵
        cin >> value;↵
        vec.pb({value, i});↵
    }↵
    sort(all(vec));↵
    vector<ll> frequency(m + 5, 0);↵
    ll curr_count = 0;↵
    ll j = 0;↵
    ll global_ans = inf;↵
    for (ll i = 0; i < n; i++)↵
    {↵
        for (auto x : factors[vec[i].ff])↵
        {↵
            if (x > m)↵
                break;↵
            if (!frequency[x]++)↵
            {↵
                curr_count++;↵
            }↵
        }↵
        while (curr_count == m)↵
        {↵
            ll curr_ans = vec[i].ff - vec[j].ff;↵
            if (curr_ans < global_ans)↵
            {↵
                global_ans = curr_ans;↵
            }↵
            for (auto x : factors[vec[j].ff])↵
            {↵
                if (x > m)↵
                    break;↵
                if (--frequency[x] == 0)↵
                {↵
                    curr_count--;↵
                }↵
            }↵
            j++;↵
        }↵
    }↵
    cout << (global_ans >= inf ? -1 : global_ans) << "\n";↵
}↵
 ↵
int main()↵
{↵
    FASTIO↵
    init();↵
    ll t;↵
    cin >> t;↵
    while (t--)↵
    {↵
        solve();↵
    }↵
    return 0;↵
}↵
~~~↵


</spoiler>↵

<spoiler summary="Feedback">↵
- Good problem: [likes:3,option1]↵
- Average problem: [likes:3,option2]↵
- Bad problem: [likes:3,option3]↵
- Did not solve: [likes:3,option4]↵
</spoiler>↵

[problem:1777D] <br>↵

Idea: [user:AwakeAnay,2023-01-21] <br>↵
Preparation: [user:mayankfrost,2023-01-21] [user:ShivanshJ,2023-01-21] <br>↵
Editorialist: [user:AwakeAnay,2023-01-21]↵

<spoiler summary="Hints">↵

<spoiler summary="Hint 1">↵
What would be the value of a node at time $t$?↵
</spoiler>↵

<spoiler summary="Hint 2">↵
The value of a node $u$ after time $t$ would be the xor of the initial values of all nodes in the subtree of $u$ which are at a distance $t$ from $u$.↵
</spoiler>↵

<spoiler summary="Hint 3">↵
What is the expected value of xor of $k$ boolean values?↵
</spoiler>↵

</spoiler>↵


<spoiler summary="Solution">↵

[tutorial:1777D]↵
</spoiler>↵


<spoiler summary="Implementation (C++)">↵

~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
 ↵
#define MOD 1'000'000'007↵
 ↵
long long power(long long a, int b)↵
{↵
    long long ans = 1;↵
    while (b)↵
    {↵
        if (b & 1)↵
        {↵
            ans *= a;↵
            ans %= MOD;↵
        }↵
        a *= a;↵
        a %= MOD;↵
        b >>= 1;↵
    }↵
    return ans;↵
}↵
 ↵
int DFS(int v, vector<int> edges[], int p, int dep, int ped[])↵
{↵
    int mdep = dep;↵
    for (auto it : edges[v])↵
        if (it != p)↵
            mdep = max(DFS(it, edges, v, dep + 1, ped), mdep);↵
    ped[v] = mdep - dep + 1;↵
    return mdep;↵
}↵
 ↵
int main()↵
{↵
    ios_base::sync_with_stdio(false);↵
    cin.tie(NULL);↵
    int T, i, j, n, u, v;↵
    cin >> T;↵
    while (T--)↵
    {↵
        cin >> n;↵
        vector<int> edges[n];↵
        for (i = 0; i < n - 1; i++)↵
        {↵
            cin >> u >> v;↵
            u--, v--;↵
 ↵
            edges[u].push_back(v);↵
            edges[v].push_back(u);↵
        }↵
 ↵
        int ped[n];↵
        DFS(0, edges, 0, 0, ped);↵
 ↵
        long long p = power(2, n - 1), ans = 0;↵
        for (i = 0; i < n; i++)↵
        {↵
            ans += p * ped[i] % MOD;↵
            ans %= MOD;↵
        }↵
        cout << ans << "\n";↵
    }↵
}↵
~~~↵


</spoiler>↵

<spoiler summary="Feedback">↵
- Good problem: [likes:4,option1]↵
- Average problem: [likes:4,option2]↵
- Bad problem: [likes:4,option3]↵
- Did not solve: [likes:4,option4]↵
</spoiler>↵

[problem:1777E] <br>↵

Idea: [user:Crocuta,2023-01-21] <br>↵
Preparation: [user:mayankfrost,2023-01-21] <br>↵
Editorialist: [user:mayankfrost,2023-01-21]↵

<spoiler summary="Hints">↵

<spoiler summary="Hint 1">↵
If the cost is c, all edges with weight less than or equal to c are reversible.↵
</spoiler>↵

<spoiler summary="Hint 2">↵
If an edge can be reversed, can it be treated as bidirectional?↵
</spoiler>↵

<spoiler summary="Hint 3">↵
Let there exist a set of possible starting nodes. If this set is non empty, the highest node h in the topological ordering of nodes will always be present in the set. Think why.↵
</spoiler>↵

</spoiler>↵


<spoiler summary="Solution">↵

[tutorial:1777E]↵
</spoiler>↵


<spoiler summary="Implementation (C++)">↵

~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
 ↵
// Using Kosa Raju, we guarantee the topmost element (indicated by root) of stack is from the root SCC↵
 ↵
void DFS(int v, bool visited[], int &root, vector<int> edges[])↵
{↵
    visited[v] = true;↵
    for (auto it : edges[v])↵
        if (!visited[it])↵
            DFS(it, visited, root, edges);↵
    root = v;↵
}↵
 ↵
int cnt(int v, bool visited[], vector<int> edges[])↵
{↵
    int ans = 1;↵
    visited[v] = true;↵
    for (auto it : edges[v])↵
        if (!visited[it])↵
            ans += cnt(it, visited, edges);↵
    return ans;↵
}↵
 ↵
int main()↵
{↵
    ios_base::sync_with_stdio(false);↵
    cin.tie(NULL);↵
    int T;↵
    cin >> T;↵
    while (T--)↵
    {↵
        int i, j, n, m, u, v, w;↵
        cin >> n >> m;↵
        vector<pair<int, int>> og_edges[n];↵
        for (i = 0; i < m; i++)↵
        {↵
            cin >> u >> v >> w;↵
            u--, v--;↵
 ↵
            og_edges[u].push_back({v, w});↵
        }↵
 ↵
        int l = -1, r = 1e9 + 1, mid;↵
        while (r - l > 1)↵
        {↵
            mid = l + (r - l) / 2;↵
 ↵
            vector<int> edges[n];↵
            for (i = 0; i < n; i++)↵
            {↵
                for (auto it : og_edges[i])↵
                {↵
                    edges[i].push_back(it.first);↵
                    if (it.second <= mid)↵
                        edges[it.first].push_back(i);↵
                }↵
            }↵
 ↵
            bool visited[n] = {};↵
            int root;↵
            for (i = 0; i < n; i++)↵
            {↵
                if (!visited[i])↵
                    DFS(i, visited, root, edges);↵
            }↵
 ↵
            memset(visited, false, sizeof(visited));↵
 ↵
            if (cnt(root, visited, edges) == n)↵
                r = mid;↵
            else↵
                l = mid;↵
        }↵
 ↵
        if (r == 1e9 + 1)↵
            r = -1;↵
        cout << r << '\n';↵
    }↵
    return 0;↵
}↵

~~~↵


</spoiler>↵

<spoiler summary="Feedback">↵
- Good problem: [likes:5,option1]↵
- Average problem: [likes:5,option2]↵
- Bad problem: [likes:5,option3]↵
- Did not solve: [likes:5,option4]↵
</spoiler>↵

[problem:1777F] <br>↵

Idea: [user:Crocuta,2023-01-21] <br>↵
Preparation: [user:TimeWarp101,2023-01-21] <br>↵
Editorialist: [user:Crocuta,2023-01-21]↵



<spoiler summary="Solution">↵

[tutorial:1777F]↵
</spoiler>↵


<spoiler summary="Implementation (C++)">↵

~~~↵
#include <bits/stdc++.h>↵
 ↵
using namespace std;↵
 ↵
struct Trie{↵
struct Trie *child[2]={0};↵
};↵
typedef struct Trie trie;↵
 ↵
void insert(trie *dic, int x)↵
{↵
trie *temp = dic;↵
for(int i=30;i>=0;i--) ↵
{↵
int curr = x>>i&1;↵
if(temp->child[curr])↵
temp = temp->child[curr];↵
else↵
{↵
temp->child[curr] = new trie;↵
temp = temp->child[curr];↵
}↵
}↵
}↵
 ↵
int find_greatest(trie *dic, int x) {↵
int res = 0;↵
trie *temp = dic;↵
for(int i=30;i>=0;i--) {↵
int curr = x>>i&1;↵
if(temp->child[curr^1]) {↵
res ^= 1<<i;↵
temp = temp->child[curr^1];↵
}↵
else {↵
temp = temp->child[curr];↵
}↵
}↵
return res; ↵
}↵
 ↵
int main() {↵
int test_cases;↵
cin >> test_cases;↵
while(test_cases--)↵
{↵
int n;↵
cin>>n;↵
int a[n+1];↵
for(int i=1;i<=n;i++) {↵
cin>>a[i];↵
}↵
 ↵
trie *t[n+2];↵
int prexor[n+1];↵
prexor[0] = 0;↵
for(int i=1;i<=n;i++) {↵
t[i] = new trie;↵
insert(t[i], prexor[i-1]);↵
prexor[i] = prexor[i-1]^a[i];↵
}↵
t[n+1] = new trie;↵
insert(t[n+1], prexor[n]);↵

pair<int,int> asc[n+1];↵
for(int i=1;i<=n;i++) {↵
asc[i] = make_pair(a[i],i);↵
}↵
sort(asc+1,asc+n+1);↵

int left[n+1], right[n+1];↵
stack<int> s;↵
for(int i=1;i<=n;i++) {↵
while(!s.empty() && a[i]>=a[s.top()])↵
s.pop();↵
if(s.empty())↵
left[i] = 0;↵
else↵
left[i] = s.top();↵
s.push(i);↵
}↵
while(!s.empty()) ↵
s.pop();↵
for(int i=n;i>0;i--) {↵
while(!s.empty() && a[i]>a[s.top()])↵
s.pop();↵
if(s.empty())↵
right[i] = n+1;↵
else↵
right[i] = s.top();↵
s.push(i);↵
}↵

int ans = 0;↵
for(int i=1;i<=n;i++) {↵
int x = asc[i].second;↵
int r = right[x]-1;↵
int l = left[x]+1;↵
if(x-l < r-x) {↵
for(int j=l-1;j<x;j++) {↵
ans = max(ans, find_greatest(t[x+1], prexor[j]^a[x]));↵
}↵
t[l] = t[x+1];↵
for(int j=l-1;j<x;j++) {↵
insert(t[l], prexor[j]);↵
}↵
}↵
else {↵
for(int j=x;j<=r;j++) {↵
ans = max(ans, find_greatest(t[l], prexor[j]^a[x]));↵
}↵
for(int j=x;j<=r;j++) {↵
insert(t[l], prexor[j]);↵
}↵
}↵
}↵
cout<<ans << endl;↵
}↵
}↵

~~~↵


</spoiler>↵

<spoiler summary="Feedback">↵
- Good problem: [likes:6,option1]↵
- Average problem: [likes:6,option2]↵
- Bad problem: [likes:6,option3]↵
- Did not solve: [likes:6,option4]↵
</spoiler>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English ShivanshJ 2023-01-21 21:05:40 677
en5 English ShivanshJ 2023-01-21 20:42:17 2 Tiny change: 'at $m \le $X$ \le M$ th' -> 'at $m \le X \le M$ th'
en4 English ShivanshJ 2023-01-21 20:41:00 2 Tiny change: 'ch that $m$ \le $X$ \le $M$ the ans' -> 'ch that $m \le $X$ \le M$ the ans'
en3 English ShivanshJ 2023-01-21 20:40:08 0 (published)
en2 English ShivanshJ 2023-01-21 20:38:54 189
en1 English ShivanshJ 2023-01-21 20:37:32 15005 Initial revision (saved to drafts)