codeforces-scrape

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

1537.md (8657B)


      1 Source: https://codeforces.com/blog/entry/91381
      2 
      3 [1537A - Arithmetic Array](/contest/1537/problem/A "Codeforces Round 726 (Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 To make the arithmetic mean be equal to exactly $1$ the sum needs to be equal to the number of elements in the array.
      8 
      9 Let's consider $3$ cases for this problem:
     10 
     11 1) The sum of the array equals $n$: Here the answer is $0$ since the arithmetic mean of the array is initially $1$.
     12 
     13 2) The sum of the array is smaller than $n$: The answer is always $1$ since we can add a single integer $k$ such that $sum + k = n + 1$ is satisfied and more specifically $k = n - sum + 1$.
     14 
     15 3) The sum of the array is greater than $n$: If we add any number apart from $0$ will add to the sum more or equal than to the number of elements. The number of $0$'s to add can be found by a loop of adding $0$'s until the number of elements is equal to the sum or by the simple formula of $sum-n$.
     16 
     17 **Code**
     18 
     19 ```
     20 #include "bits/stdc++.h"
     21  using namespace std;
     22 
     23  int main()
     24  {
     25 	 int t;
     26 	 cin >> t;
     27 	 while(t--){
     28 		 int n;
     29 		 cin >> n;
     30 		 int sum = 0;
     31 		 for (int i = 0;i < n; i++){
     32 			 int a;
     33 			 cin >> a;
     34 			 sum += a;
     35 		 }
     36    if(sum < n)cout << "1\n";
     37    else cout << sum - n << "\n";
     38 	 }
     39  }
     40 ```
     41 
     42 [1537B - Bad Boy](/contest/1537/problem/B "Codeforces Round 726 (Div. 2)")
     43 
     44 **Tutorial**
     45 
     46 Tutorial is loading...
     47 
     48 **Code**
     49 
     50 ```
     51 #include "bits/stdc++.h"
     52 using namespace std;
     53 
     54 int main()
     55 {
     56     int t;
     57     cin >> t;
     58     while(t--){
     59         int n, m, i, j;
     60         cin >> n >> m >> i >> j;
     61 
     62         cout << 1 << " " << 1 << " " << n << " " << m << "\n";
     63     }
     64 }
     65 ```
     66 
     67 [1537C - Challenging Cliffs](/contest/1537/problem/C "Codeforces Round 726 (Div. 2)")
     68 
     69 **Tutorial**
     70 
     71 Tutorial is loading...
     72 
     73 **Code**
     74 
     75 ```
     76 #include "bits/stdc++.h"
     77 using namespace std;
     78 
     79 int main()
     80 {
     81     int t;
     82     cin >> t;
     83     while(t--){
     84         int n;
     85         cin >> n;
     86         vector<int> h(n);
     87 
     88         for (int i = 0;i < n; i++){
     89             cin >> h[i];
     90         }
     91         sort(h.begin(), h.end());
     92 
     93         if(n == 2){
     94             cout << h[0] << " " << h[1] << "\n";
     95             continue;
     96         }
     97 
     98         int pos = -1, mn = INT_MAX;
     99 
    100         for (int i = 1;i < n; i++){
    101             if(mn > abs(h[i] - h[i - 1])){
    102                 pos = i;
    103                 mn = abs(h[i] - h[i - 1]);
    104             }
    105         }
    106         
    107         for (int i = pos;i < n; i++){
    108             cout << h[i] << " ";
    109         }
    110         for(int i = 0;i < pos; i++){
    111             cout << h[i] << " ";
    112         }
    113 
    114         cout << "\n";
    115 
    116     }
    117 }
    118 ```
    119 
    120 [1537D - Deleting Divisors](/contest/1537/problem/D "Codeforces Round 726 (Div. 2)")
    121 
    122 **Tutorial**
    123 
    124 Tutorial is loading...
    125 
    126 **Code**
    127 
    128 ```
    129 #include "bits/stdc++.h"
    130 using namespace std;
    131  
    132 int main()
    133 {
    134     int t;
    135     cin >> t;
    136  
    137     while(t--){
    138         
    139         int n;
    140         cin >> n;
    141         if(n % 2 == 1){
    142             cout << "Bob\n";
    143             continue;
    144         }
    145         int cnt = 0;
    146         while(n % 2 == 0){
    147             cnt++;
    148             n /= 2;
    149         }
    150  
    151         if(n > 1){
    152             cout << "Alice\n";
    153         }else if(cnt % 2 == 0){
    154             cout << "Alice\n";
    155         }else cout << "Bob\n";
    156     }
    157 }
    158 ```
    159 
    160 [1537E1 - Erase and Extend (Easy Version)](/contest/1537/problem/E1 "Codeforces Round 726 (Div. 2)")
    161 
    162 **Tutorial**
    163 
    164 Tutorial is loading...
    165 
    166 **Code**
    167 
    168 ```
    169 #include "bits/stdc++.h"
    170 using namespace std;
    171 
    172 string get(string s, int k){
    173     while((int)s.size() < k){
    174         s = s + s;
    175     }
    176     while((int)s.size() > k)
    177         s.pop_back();
    178     return s;
    179 }
    180 int main()
    181 {
    182     int n, k;
    183     string s;
    184     cin >> n >> k;
    185     cin >> s;
    186 
    187     string pref = "";
    188     pref += s[0];
    189 
    190     string mn = get(pref, k);
    191 
    192     for(int i = 1;i < n;i++){
    193         if(s[i] > s[0])break;
    194         pref += s[i];
    195         mn = min(mn, get(pref, k));
    196     }
    197     cout << mn << "\n";
    198 }
    199 ```
    200 
    201 [1537E2 - Erase and Extend (Hard Version)](/contest/1537/problem/E2 "Codeforces Round 726 (Div. 2)")
    202 
    203 **Tutorial**
    204 
    205 We know that the final string is some prefix repeated a bunch of times. Incrementally for $i$ from $1$ to $n$ we will keep the longest among the first $i$ prefixes that gives the best answer we've seen so far.
    206 
    207 So assume the $m-th$ prefix is currently the best and we're considering position $p$. If the $p-th$ character is greater than the corresponding character in $s_{1..m} \cdot (a lot)$ then the $p-th$ prefix and any further prefixes can't possibly give a smaller answer, so we just print the current one and finish. Otherwise all the characters before the $p-th$ are all less than or equal to the corresponding characters in $s_1..m \cdot (a lot)$, so if the $p-th$ is smaller than the corresponding we set the $p-th$ prefix as the best.
    208 
    209 Now the interesting case is if the current character is the same as the corresponding one. Say then that $p = m + t$, by the logic of the previous paragraph we must have $s_{(m + 1)..(m + t)} = s_{1..t}$. If $t = m$ then the new prefix is just the old one twice, so set $p$ as the best prefix now. This ensures that otherwise $t \lt m$.
    210 
    211 Denote $A = s_{1..t}$ and $B = s_{(t + 1)..m}$, so the string formed by the current best prefix is $ABABABABA...$ and the new one is $ABAABAABA...$ Now if $AB = BA$ then these strings are in fact the same, so set $m + t$ as the new best prefix. Otherwise we can find the first position where $AB$ and $BA$ differ, and use that to determine whether the new prefix is better. This can be done in $O(1)$ with Z function, thus giving a linear solution for the full problem.
    212 
    213 Solution by [Ari](/profile/Ari "Grandmaster Ari").
    214 
    215 **Code**
    216 
    217 ```
    218 #include <bits/stdc++.h>
    219 using namespace std;
    220 using ll = long long;
    221 
    222 string s;
    223 int n, k;
    224 
    225 vector<int> z_func(string &s) {
    226     int n = s.size(), L = -1, R = -1;
    227     vector<int> z(n);
    228     z[0] = n;
    229     for(int i = 1; i < n; i++) {
    230         if(i <= R)
    231             z[i] = min(z[i - L], R - i + 1);
    232         while(i + z[i] < n && s[i + z[i]] == s[z[i]])
    233             z[i]++;
    234         if(i + z[i] - 1 > R) {
    235             L = i;
    236             R = i + z[i] - 1;
    237         }
    238     }
    239     return z;
    240 }
    241 
    242 void finish(int m) {
    243     for(int i = 0; i < k; i++)
    244         cout << s[i % m];
    245     cout << '\n';
    246     exit(0);
    247 }
    248 
    249 int main() {
    250     ios_base::sync_with_stdio(false);
    251     cin.tie(0);
    252 
    253     cin >> n >> k >> s;
    254     auto z = z_func(s);
    255 
    256     int cur = 1;
    257     for(int i = 1; i < n; i++) {
    258         if(s[i] > s[i % cur])
    259             finish(cur);
    260         if(s[i] < s[i % cur]) {
    261             cur = i + 1;
    262             continue;
    263         }
    264         int off = i - cur + 1;
    265         if(off == cur) {
    266             cur = i + 1;
    267             continue;
    268         }
    269         if(z[off] < cur - off) {
    270             if(cur + off + z[off] >= k) {
    271                 cur = i + 1;
    272                 continue;
    273             }
    274             if(s[off + z[off]] > s[z[off]])
    275                 cur = i + 1;
    276             continue;
    277         }
    278         if(z[cur - off] < off) {
    279             if(2 * cur + z[cur - off] >= k) {
    280                 cur = i + 1;
    281                 continue;
    282             }
    283             if(s[cur - off + z[cur - off]] < s[z[cur - off]])
    284                 cur = i + 1;
    285             continue;
    286         }
    287         cur = i + 1;
    288     }
    289 
    290     finish(cur);
    291 }
    292 ```
    293 
    294 [1537F - Figure Fixing](/contest/1537/problem/F "Codeforces Round 726 (Div. 2)")
    295 
    296 **Tutorial**
    297 
    298 Tutorial is loading...
    299 
    300 **Code**
    301 
    302 ```
    303 #include "bits/stdc++.h"
    304  using namespace std;
    305 
    306  const int N = 2e5 + 10;
    307  vector<long long> adj[N];
    308  long long s[N], n, m;
    309  bool bipartite()
    310  {
    311 	 bool bip = true;
    312 
    313 	 for(long long i = 0;i < n;i++)
    314 		 s[i] = -1;
    315 
    316 	 queue<long long> q;
    317 
    318 	 for(long long i = 0;i < n;i++){
    319 		 if(s[i] != -1)continue;
    320 
    321 		 q.push(i);
    322 		 s[i] = 0;
    323 
    324 		 while(!q.empty()){
    325 			 long long v = q.front();
    326 			 q.pop();
    327 
    328 			 for(long long u: adj[v]){
    329 				 if(s[u] == -1){
    330 					 s[u] = s[v] ^ 1;
    331 					 q.push(u);
    332 				 }else bip &= s[u] != s[v];
    333 			 }
    334 		 }
    335 	 }
    336 	 return bip;
    337  }
    338 
    339  int main()
    340  {
    341 	 ios_base::sync_with_stdio(0);cin.tie(0);
    342 	 long long T;
    343 	 cin >> T;
    344 	 while(T--)
    345 	 {
    346 		 cin >> n >> m;
    347 		 for(long long i = 0;i < n;i++)
    348 			 adj[i].clear();
    349 
    350 		 vector<long long> v(n), t(n);
    351 		long long p1 = 0, p2 = 0;
    352 		 for(long long i = 0;i < n; i++){
    353 			 cin >> v[i];
    354 			 p1 = (p1 + abs(v[i])) % 2;
    355 		 }
    356 		 for (long long i = 0;i < n; i++){
    357 			 cin >> t[i];
    358 			 p2 = (p2 + abs(t[i])) % 2;
    359 		 }
    360 
    361 		 for(long long i = 0;i < m;i++){
    362 			 long long a, b;
    363 			 cin >> a >> b;
    364 			 --a, --b;
    365 			 adj[a].push_back(b);
    366 			 adj[b].push_back(a);
    367 		 }
    368 		 
    369 		 if(p1 != p2){
    370 		   cout << "NO\n";
    371 		   continue;
    372 		 }
    373 
    374 		 if(bipartite() == false){
    375 			 cout << "YES\n";
    376 		 }else{
    377 			 vector<long long> c(2, 0);
    378 
    379 			 for(int i = 0;i < n;i++){
    380 				 c[s[i]] += v[i] - t[i];
    381 			 }
    382 
    383 			 if(c[0] == c[1]){
    384 				 cout << "YES\n";
    385 			 }else cout << "NO\n";
    386 		 }
    387 	 }
    388 
    389  }
    390 ```