codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1777.md (13564B)


      1 Source: https://codeforces.com/blog/entry/111729
      2 
      3 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.
      4 
      5 ---
      6 
      7 [1777A - Everybody Likes Good Arrays!](/contest/1777/problem/A "Codeforces Round 845 (Div. 2) and ByteRace 2023")
      8 
      9 Idea: [ShivanshJ](/profile/ShivanshJ "Candidate Master ShivanshJ")   
     10  Preparation: [ShivanshJ](/profile/ShivanshJ "Candidate Master ShivanshJ")   
     11  Editorialist: [ShivanshJ](/profile/ShivanshJ "Candidate Master ShivanshJ")
     12 
     13 **Hints**
     14 
     15 **Hint 1**
     16 
     17 Try to make the problem simpler.
     18 
     19 **Hint 2**
     20 
     21 Parity?
     22 
     23 **Hint 3**
     24 
     25 Try replacing even numbers with $0$ and odd numbers with $1$ in other words consider all numbers modulo $2$.
     26 
     27 **Hint 4**
     28 
     29 Think harder! It works!
     30 
     31 **Solution**
     32 
     33 Tutorial is loading...
     34 
     35 **Implementation (C++)**
     36 
     37 ```
     38                         /* Enjoying CP as always!*/
     39 #include <bits/stdc++.h>
     40 using namespace std;
     41 #define int long long
     42 
     43 signed main() {
     44     ios_base::sync_with_stdio(false);
     45     cin.tie(NULL);
     46     int t;
     47     cin>>t;
     48     while(t--) {
     49         //Take input
     50         int n;
     51         cin>>n;
     52         int a[n];
     53         for(int i=0;i<n;i++) {
     54             cin>>a[i];
     55         }
     56         //initialize answer..
     57         int ans=0;
     58         for(int i=0;i+1<n;i++) {
     59             ans+=(!((a[i]^a[i+1])&1));
     60             /*XOR the two numbers and check 0th bit in the resultant, if it is 1
     61             then, numbers are of different parity, otherwise both are of same parity*/
     62         }
     63         cout<<ans<<"\n";
     64     }
     65     return 0;
     66 }
     67 ```
     68 
     69 **Implementation (Python)**
     70 
     71 ```
     72 def main():
     73     T = int(input())
     74     while T > 0:
     75         T = T - 1
     76         n = int(input())
     77         a = [int(x) for x in input().split()]
     78         ans = 0
     79  
     80         for i in range(1, n):
     81             ans += 1 - ((a[i] + a[i - 1]) & 1)
     82  
     83         print(ans)
     84  
     85  
     86 if __name__ == '__main__':
     87     main()
     88 ```
     89 
     90 **Feedback**
     91 
     92 * Good problem:
     93 * Average problem:
     94 * Bad problem:
     95 * Did not solve:
     96 
     97 [1777B - Emordnilap](/contest/1777/problem/B "Codeforces Round 845 (Div. 2) and ByteRace 2023")
     98 
     99 Idea: [TimeWarp101](/profile/TimeWarp101 "Candidate Master TimeWarp101") [quantau](/profile/quantau "Expert quantau")   
    100  Preparation: [TimeWarp101](/profile/TimeWarp101 "Candidate Master TimeWarp101")   
    101  Editorialist: [TimeWarp101](/profile/TimeWarp101 "Candidate Master TimeWarp101")
    102 
    103 **Hints**
    104 
    105 **Hint 1**
    106 
    107 Will the answer differ for different permutations?
    108 
    109 **Hint 2**
    110 
    111 If you only look at 2 elements, how much will they contribute to the answer?
    112 
    113 **Solution**
    114 
    115 Tutorial is loading...
    116 
    117 **Implementation (C++)**
    118 
    119 ```
    120 #include<bits/stdc++.h>
    121 using namespace std;
    122 #define int long long
    123 signed main()
    124 {
    125     const int N = 1e5 + 5;
    126     const int mod = 1e9 + 7;
    127     vector<int> fact(N);
    128     fact[0] = 1;
    129     for(int i = 1; i < N; i++)
    130     {
    131         fact[i] = fact[i - 1] * i;
    132         fact[i] %= mod;
    133     }
    134     int t;
    135     cin >> t;
    136     while(t--)
    137     {
    138         int n;
    139         cin >> n;
    140         int ans = n * (n - 1);
    141         ans %= mod;
    142         ans = (ans * fact[n]) % mod;
    143         cout << ans << endl;
    144     }
    145     return 0;
    146 }
    147 ```
    148 
    149 **Implementation (Python)**
    150 
    151 ```
    152 t = int(input())
    153 for _ in range(t):
    154     n = int(input())
    155     nf = 1
    156     mod = int(1e9 + 7)
    157     for i in range(n):
    158         nf = nf * (i + 1)
    159         nf %= mod
    160     ans = n * (n - 1) * nf
    161     ans %= mod
    162     print(ans)
    163 ```
    164 
    165 **Feedback**
    166 
    167 * Good problem:
    168 * Average problem:
    169 * Bad problem:
    170 * Did not solve:
    171 
    172 [1777C - Quiz Master](/contest/1777/problem/C "Codeforces Round 845 (Div. 2) and ByteRace 2023")
    173 
    174 Idea: [quantau](/profile/quantau "Expert quantau")   
    175  Preparation: [TimeWarp101](/profile/TimeWarp101 "Candidate Master TimeWarp101") [quantau](/profile/quantau "Expert quantau")   
    176  Editorialist: [TimeWarp101](/profile/TimeWarp101 "Candidate Master TimeWarp101")
    177 
    178 **Hints**
    179 
    180 **Hint 1**
    181 
    182 Would sorting the array help?
    183 
    184 **Hint 2**
    185 
    186 Would iterating over the factors help?
    187 
    188 **Hint 3**
    189 
    190 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.
    191 
    192 **Hint 4**
    193 
    194 Two pointers?
    195 
    196 **Solution**
    197 
    198 Tutorial is loading...
    199 
    200 **Implementation (C++)**
    201 
    202 ```
    203 #include <bits/stdc++.h>
    204 #define all(v) v.begin(), v.end()
    205 #define var(x, y, z) cout << x << " " << y << " " << z << endl;
    206 #define ll long long int
    207 #define pii pair<ll, ll>
    208 #define pb push_back
    209 #define ff first
    210 #define ss second
    211 #define FASTIO                \
    212     ios ::sync_with_stdio(0); \
    213     cin.tie(0);               \
    214     cout.tie(0);
    215 
    216 using namespace std;
    217 
    218 const ll inf = 1e17;
    219 const ll MAXM = 1e5;
    220 vector<ll> factors[MAXM + 5];
    221 
    222 void init()
    223 {
    224     for (ll i = 1; i <= MAXM; i++)
    225     {
    226         for (ll j = i; j <= MAXM; j += i)
    227         {
    228             factors[j].pb(i);
    229         }
    230     }
    231 }
    232 
    233 void solve()
    234 {
    235     ll n, m;
    236     cin >> n >> m;
    237     vector<pii> vec;
    238     for (ll i = 0; i < n; i++)
    239     {
    240         ll value;
    241         cin >> value;
    242         vec.pb({value, i});
    243     }
    244     sort(all(vec));
    245     vector<ll> frequency(m + 5, 0);
    246     ll curr_count = 0;
    247     ll j = 0;
    248     ll global_ans = inf;
    249     for (ll i = 0; i < n; i++)
    250     {
    251         for (auto x : factors[vec[i].ff])
    252         {
    253             if (x > m)
    254                 break;
    255             if (!frequency[x]++)
    256             {
    257                 curr_count++;
    258             }
    259         }
    260         while (curr_count == m)
    261         {
    262             ll curr_ans = vec[i].ff - vec[j].ff;
    263             if (curr_ans < global_ans)
    264             {
    265                 global_ans = curr_ans;
    266             }
    267             for (auto x : factors[vec[j].ff])
    268             {
    269                 if (x > m)
    270                     break;
    271                 if (--frequency[x] == 0)
    272                 {
    273                     curr_count--;
    274                 }
    275             }
    276             j++;
    277         }
    278     }
    279     cout << (global_ans >= inf ? -1 : global_ans) << "\n";
    280 }
    281 
    282 int main()
    283 {
    284     FASTIO
    285     init();
    286     ll t;
    287     cin >> t;
    288     while (t--)
    289     {
    290         solve();
    291     }
    292     return 0;
    293 }
    294 ```
    295 
    296 **Feedback**
    297 
    298 * Good problem:
    299 * Average problem:
    300 * Bad problem:
    301 * Did not solve:
    302 
    303 [1777D - Score of a Tree](/contest/1777/problem/D "Codeforces Round 845 (Div. 2) and ByteRace 2023")
    304 
    305 Idea: [AwakeAnay](/profile/AwakeAnay "International Master AwakeAnay")   
    306  Preparation: [mayankfrost](/profile/mayankfrost "Candidate Master mayankfrost") [ShivanshJ](/profile/ShivanshJ "Candidate Master ShivanshJ")   
    307  Editorialist: [AwakeAnay](/profile/AwakeAnay "International Master AwakeAnay")
    308 
    309 **Hints**
    310 
    311 **Hint 1**
    312 
    313 What would be the value of a node at time $t$?
    314 
    315 **Hint 2**
    316 
    317 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$.
    318 
    319 **Hint 3**
    320 
    321 What is the expected value of xor of $k$ boolean values?
    322 
    323 **Solution**
    324 
    325 Tutorial is loading...
    326 
    327 **Implementation (C++)**
    328 
    329 ```
    330 #include <bits/stdc++.h>
    331 using namespace std;
    332  
    333 #define MOD 1000000007
    334  
    335 long long power(long long a, int b)
    336 {
    337     long long ans = 1;
    338     while (b)
    339     {
    340         if (b & 1)
    341         {
    342             ans *= a;
    343             ans %= MOD;
    344         }
    345         a *= a;
    346         a %= MOD;
    347         b >>= 1;
    348     }
    349     return ans;
    350 }
    351  
    352 int DFS(int v, vector<int> edges[], int p, int dep, int ped[])
    353 {
    354     int mdep = dep;
    355     for (auto it : edges[v])
    356         if (it != p)
    357             mdep = max(DFS(it, edges, v, dep + 1, ped), mdep);
    358     ped[v] = mdep - dep + 1;
    359     return mdep;
    360 }
    361  
    362 int main()
    363 {
    364     ios_base::sync_with_stdio(false);
    365     cin.tie(NULL);
    366     int T, i, j, n, u, v;
    367     cin >> T;
    368     while (T--)
    369     {
    370         cin >> n;
    371         vector<int> edges[n];
    372         for (i = 0; i < n - 1; i++)
    373         {
    374             cin >> u >> v;
    375             u--, v--;
    376  
    377             edges[u].push_back(v);
    378             edges[v].push_back(u);
    379         }
    380  
    381         int ped[n];
    382         DFS(0, edges, 0, 0, ped);
    383  
    384         long long p = power(2, n - 1), ans = 0;
    385         for (i = 0; i < n; i++)
    386         {
    387             ans += p * ped[i] % MOD;
    388             ans %= MOD;
    389         }
    390         cout << ans << "\n";
    391     }
    392 }
    393 ```
    394 
    395 **Feedback**
    396 
    397 * Good problem:
    398 * Average problem:
    399 * Bad problem:
    400 * Did not solve:
    401 
    402 [1777E - Edge Reverse](/contest/1777/problem/E "Codeforces Round 845 (Div. 2) and ByteRace 2023")
    403 
    404 Idea: [Crocuta](/profile/Crocuta "Candidate Master Crocuta")   
    405  Preparation: [mayankfrost](/profile/mayankfrost "Candidate Master mayankfrost")   
    406  Editorialist: [mayankfrost](/profile/mayankfrost "Candidate Master mayankfrost")
    407 
    408 **Hints**
    409 
    410 **Hint 1**
    411 
    412 If the cost is c, all edges with weight less than or equal to c are reversible.
    413 
    414 **Hint 2**
    415 
    416 If an edge can be reversed, can it be treated as bidirectional?
    417 
    418 **Hint 3**
    419 
    420 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.
    421 
    422 **Solution**
    423 
    424 Tutorial is loading...
    425 
    426 **Implementation (C++)**
    427 
    428 ```
    429 #include <bits/stdc++.h>
    430 using namespace std;
    431  
    432 // Using Kosa Raju, we guarantee the topmost element (indicated by root) of stack is from the root SCC
    433  
    434 void DFS(int v, bool visited[], int &root, vector<int> edges[])
    435 {
    436     visited[v] = true;
    437     for (auto it : edges[v])
    438         if (!visited[it])
    439             DFS(it, visited, root, edges);
    440     root = v;
    441 }
    442  
    443 int cnt(int v, bool visited[], vector<int> edges[])
    444 {
    445     int ans = 1;
    446     visited[v] = true;
    447     for (auto it : edges[v])
    448         if (!visited[it])
    449             ans += cnt(it, visited, edges);
    450     return ans;
    451 }
    452  
    453 int main()
    454 {
    455     ios_base::sync_with_stdio(false);
    456     cin.tie(NULL);
    457     int T;
    458     cin >> T;
    459     while (T--)
    460     {
    461         int i, j, n, m, u, v, w;
    462         cin >> n >> m;
    463         vector<pair<int, int>> og_edges[n];
    464         for (i = 0; i < m; i++)
    465         {
    466             cin >> u >> v >> w;
    467             u--, v--;
    468  
    469             og_edges[u].push_back({v, w});
    470         }
    471  
    472         int l = -1, r = 1e9 + 1, mid;
    473         while (r - l > 1)
    474         {
    475             mid = l + (r - l) / 2;
    476  
    477             vector<int> edges[n];
    478             for (i = 0; i < n; i++)
    479             {
    480                 for (auto it : og_edges[i])
    481                 {
    482                     edges[i].push_back(it.first);
    483                     if (it.second <= mid)
    484                         edges[it.first].push_back(i);
    485                 }
    486             }
    487  
    488             bool visited[n] = {};
    489             int root;
    490             for (i = 0; i < n; i++)
    491             {
    492                 if (!visited[i])
    493                     DFS(i, visited, root, edges);
    494             }
    495  
    496             memset(visited, false, sizeof(visited));
    497  
    498             if (cnt(root, visited, edges) == n)
    499                 r = mid;
    500             else
    501                 l = mid;
    502         }
    503  
    504         if (r == 1e9 + 1)
    505             r = -1;
    506         cout << r << '\n';
    507     }
    508     return 0;
    509 }
    510 ```
    511 
    512 **Feedback**
    513 
    514 * Good problem:
    515 * Average problem:
    516 * Bad problem:
    517 * Did not solve:
    518 
    519 [1777F - Comfortably Numb](/contest/1777/problem/F "Codeforces Round 845 (Div. 2) and ByteRace 2023")
    520 
    521 Idea: [Crocuta](/profile/Crocuta "Candidate Master Crocuta")   
    522  Preparation: [TimeWarp101](/profile/TimeWarp101 "Candidate Master TimeWarp101")   
    523  Editorialist: [Crocuta](/profile/Crocuta "Candidate Master Crocuta")
    524 
    525 **Hints**
    526 
    527 **Hint 1**
    528 
    529 Can we somehow fix the maximum element ?
    530 
    531 **Hint 2**
    532 
    533 To calculate the answer over all subarrays with the same maximum element, can we use the trie trick for calculating the maximum xor.
    534 
    535 **Solution**
    536 
    537 Tutorial is loading...
    538 
    539 **Implementation (C++)**
    540 
    541 ```
    542 #include <bits/stdc++.h>
    543  
    544 using namespace std;
    545  
    546 struct Trie{
    547 	struct Trie *child[2]={0};
    548 };
    549 typedef struct Trie trie;
    550  
    551 void insert(trie *dic, int x)
    552 {
    553 	trie *temp = dic;
    554 	for(int i=30;i>=0;i--) 
    555 	{
    556 		int curr = x>>i&1;
    557 		if(temp->child[curr])
    558 			temp = temp->child[curr];
    559 		else
    560 		{
    561 			temp->child[curr] = new trie;
    562 			temp = temp->child[curr];
    563 		}
    564 	}
    565 }
    566  
    567 int find_greatest(trie *dic, int x) {
    568 	int res = 0;
    569 	trie *temp = dic;
    570 	for(int i=30;i>=0;i--) {
    571 		int curr = x>>i&1;
    572 		if(temp->child[curr^1]) {
    573 			res ^= 1<<i;
    574 			temp = temp->child[curr^1];
    575 		}
    576 		else {
    577 			temp = temp->child[curr];
    578 		}
    579 	}
    580 	return res;	
    581 }
    582  
    583 int main() {
    584 	int test_cases;
    585 	cin >> test_cases;
    586 	while(test_cases--)
    587 	{
    588 		int n;
    589 		cin>>n;
    590 		int a[n+1];
    591 		for(int i=1;i<=n;i++) {
    592 			cin>>a[i];
    593 		}
    594  
    595 		trie *t[n+2];
    596 		int prexor[n+1];
    597 		prexor[0] = 0;
    598 		for(int i=1;i<=n;i++) {
    599 			t[i] = new trie;
    600 			insert(t[i], prexor[i-1]);
    601 			prexor[i] = prexor[i-1]^a[i];
    602 		}
    603 		t[n+1] = new trie;
    604 		insert(t[n+1], prexor[n]);
    605 		
    606 		pair<int,int> asc[n+1];
    607 		for(int i=1;i<=n;i++) {
    608 			asc[i] = make_pair(a[i],i);
    609 		}
    610 		sort(asc+1,asc+n+1);
    611 		
    612 		int left[n+1], right[n+1];
    613 		stack<int> s;
    614 		for(int i=1;i<=n;i++) {
    615 			while(!s.empty() && a[i]>=a[s.top()])
    616 				s.pop();
    617 			if(s.empty())
    618 				left[i] = 0;
    619 			else
    620 				left[i] = s.top();
    621 			s.push(i);
    622 		}
    623 		while(!s.empty()) 
    624 			s.pop();
    625 		for(int i=n;i>0;i--) {
    626 			while(!s.empty() && a[i]>a[s.top()])
    627 				s.pop();
    628 			if(s.empty())
    629 				right[i] = n+1;
    630 			else
    631 				right[i] = s.top();
    632 			s.push(i);
    633 		}
    634 		
    635 		int ans = 0;
    636 		for(int i=1;i<=n;i++) {
    637 			int x = asc[i].second;
    638 			int r = right[x]-1;
    639 			int l = left[x]+1;
    640 			if(x-l < r-x) {
    641 				for(int j=l-1;j<x;j++) {
    642 					ans = max(ans, find_greatest(t[x+1], prexor[j]^a[x]));
    643 				}
    644 				t[l] = t[x+1];
    645 				for(int j=l-1;j<x;j++) {
    646 					insert(t[l], prexor[j]);
    647 				}
    648 			}
    649 			else {
    650 				for(int j=x;j<=r;j++) {
    651 					ans = max(ans, find_greatest(t[l], prexor[j]^a[x]));
    652 				}
    653 				for(int j=x;j<=r;j++) {
    654 					insert(t[l], prexor[j]);
    655 				}
    656 			}
    657 		}
    658 		cout<<ans << endl;
    659 	}
    660 }
    661 ```
    662 
    663 **Feedback**
    664 
    665 * Good problem:
    666 * Average problem:
    667 * Bad problem:
    668 * Did not solve: