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>↵
↵
↵
---↵
↵
[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>↵
↵
