Codeforces Round #845 (Div. 2) and ByteRace 2023 Editorial
Difference between en5 and en6, changed 677 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);↵
 
FASTIO                \↵
    ios ::sync_with_stdio(0); \↵
    cin.tie(0);               \↵
    cout.tie(0);↵

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="Hints">↵

<spoiler summary="Hint 1">↵
Can we somehow fix the maximum element ?↵
</spoiler>↵


<spoiler summary="Hint 2">↵
To calculate the answer over all subarrays with the same maximum element, can we use the trie trick for calculating the maximum xor.↵
</spoiler>↵

</spoiler>↵

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