1646.md (8158B)
1 Source: https://codeforces.com/blog/entry/100584 2 3 Thanks for participating in the round! I hope you enjoyed the problems! 4 5 [1646A - Square Counting](/contest/1646/problem/A "Codeforces Round 774 (Div. 2)") 6 7 **Solution** 8 9 Tutorial is loading... 10 11 **Code** 12 13 ``` 14 #include <bits/stdc++.h> 15 using namespace std; 16 17 int main(){ 18 int t; cin >> t; 19 for(int i = 0; i < t; i++){ 20 long long n, s; 21 cin >> n >> s; 22 cout << s / (n * n) << "\n"; 23 } 24 return 0; 25 } 26 ``` 27 28 [1646B - Quality vs Quantity](/contest/1646/problem/B "Codeforces Round 774 (Div. 2)") 29 30 **Solution** 31 32 Tutorial is loading... 33 34 **Additional comment** 35 36 It can be proven that (try to prove it!) if some $k$ works, then $k=\displaystyle \left \lfloor \frac{n-1}{2} \right \rfloor$ has to work. This means that there is always an answer using $n$ or $n-1$ elements, depending on parity. 37 38 **Code** 39 40 ``` 41 #include <bits/stdc++.h> 42 using namespace std; 43 44 int main(){ 45 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); 46 int t; cin >> t; 47 for(int test_number = 0; test_number < t; test_number++){ 48 int n; cin >> n; 49 vector <long long> a(n); 50 for(int i = 0; i < n; i++){ 51 cin >> a[i]; 52 } 53 sort(a.begin(), a.end()); 54 vector <long long> prefix_sums = {0}; 55 for(int i = 0; i < n; i++){ 56 prefix_sums.push_back(prefix_sums.back() + a[i]); 57 } 58 vector <long long> suffix_sums = {0}; 59 for(int i = n - 1; i >= 0; i--){ 60 suffix_sums.push_back(suffix_sums.back() + a[i]); 61 } 62 bool answer = false; 63 for(int k = 1; k <= n; k++){ 64 if(2 * k + 1 <= n){ 65 long long blue_sum = prefix_sums[k + 1]; 66 long long red_sum = suffix_sums[k]; 67 if(blue_sum < red_sum){ 68 answer = true; 69 } 70 } 71 } 72 if(answer) cout << "YES\n"; 73 else cout << "NO\n"; 74 } 75 return 0; 76 } 77 ``` 78 79 [1646C - Factorials and Powers of Two](/contest/1646/problem/C "Codeforces Round 774 (Div. 2)") 80 81 **Solution** 82 83 Tutorial is loading... 84 85 **Additional comment** 86 87 Actually, there is no problem in repeating $1$, $2$, or any other power of two. This is because it can be proven that (try to prove it!) those sums are not optimal. 88 89 **Code** 90 91 ``` 92 #include <bits/stdc++.h> 93 using namespace std; 94 95 const long long MAXAI = 1000000000000ll; 96 97 int get_first_bit(long long n){ 98 return 63 - __builtin_clzll(n); 99 } 100 101 int get_bit_count(long long n){ 102 return __builtin_popcountll(n); 103 } 104 105 int main(){ 106 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); 107 int t; cin >> t; 108 for(int test_number = 0; test_number < t; test_number++){ 109 long long n; cin >> n; 110 //Computing factorials <= MAXAI 111 vector<long long> fact; 112 long long factorial = 6, number = 4; 113 while(factorial <= MAXAI){ 114 fact.push_back(factorial); 115 factorial *= number; 116 number++; 117 } 118 //Computing masks of factorials 119 vector<pair<long long, long long>> fact_sum(1 << fact.size()); 120 fact_sum[0] = {0, 0}; 121 for(int mask = 1; mask < (1 << fact.size()); mask++){ 122 auto first_bit = get_first_bit(mask); 123 fact_sum[mask].first = fact_sum[mask ^ (1 << first_bit)].first + fact[first_bit]; 124 fact_sum[mask].second = get_bit_count(mask); 125 } 126 long long res = get_bit_count(n); 127 for(auto i : fact_sum){ 128 if(i.first <= n){ 129 res = min(res, i.second + get_bit_count(n - i.first)); 130 } 131 } 132 cout << res << "\n"; 133 } 134 135 return 0; 136 } 137 ``` 138 139 [1646D - Weight the Tree](/contest/1646/problem/D "Codeforces Round 774 (Div. 2)") 140 141 **Solution** 142 143 Tutorial is loading... 144 145 **Code** 146 147 ``` 148 #include <bits/stdc++.h> 149 using namespace std; 150 151 const int MAXN = 400005; 152 153 vector<int> g[MAXN]; 154 155 bool vis[MAXN]; 156 int pa[MAXN]; 157 158 //DFS to compute the parent of each node 159 //parent of node i is stored at pa[i] 160 void dfs(int v){ 161 vis[v] = 1; 162 for(auto i : g[v]){ 163 if(!vis[i]){ 164 pa[i] = v; 165 dfs(i); 166 } 167 } 168 } 169 170 pair<int, int> dp[MAXN][2]; 171 172 //Computes the value of function f, using dp 173 //the second coordinate of the pair is negated (to take maximums) 174 pair<int, int> f(int x, int y){ 175 pair<int, int> & res = dp[x][y]; 176 if(res.first >= 0) return res; 177 res = {y, y ? -((int) g[x].size()) : -1}; 178 for(auto i : g[x]){ 179 if(i != pa[x]){ 180 pair<int, int> maxi = f(i, 0); 181 if(y == 0) maxi = max(maxi, f(i, 1)); 182 res.first += maxi.first; 183 res.second += maxi.second; 184 } 185 } 186 return res; 187 } 188 189 vector<int> is_good; 190 191 //Recursive construction of the answer 192 //is_good[i] tells whether vertex i is good or not. 193 void build(pair<int, int> value, int v){ 194 if(value == f(v, 0)){ 195 is_good[v] = 0; 196 for(auto i : g[v]){ 197 if(i != pa[v]){ 198 build(max(f(i, 0), f(i, 1)), i); 199 } 200 } 201 }else{ 202 is_good[v] = 1; 203 for(auto i : g[v]){ 204 if(i != pa[v]){ 205 build(f(i, 0), i); 206 } 207 } 208 } 209 } 210 211 int main(){ 212 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); 213 int n; cin >> n; 214 for(int i = 0; i < n - 1; i++){ 215 int u, v; 216 cin >> u >> v; u--; v--; 217 g[u].push_back(v); 218 g[v].push_back(u); 219 } 220 if(n == 2){ 221 cout<<"2 2\n1 1\n"; 222 return 0; 223 } 224 pa[0] = -1; 225 dfs(0); 226 for(int i = 0; i < n; i++) dp[i][0] = {-1, -1}, dp[i][1] = {-1, -1}; 227 pair<int, int> res = max(f(0, 0), f(0, 1)); 228 cout << res.first << " " << -res.second << "\n"; 229 is_good.resize(n); 230 build(res, 0); 231 for(int i = 0; i < n; i++){ 232 if(is_good[i]) cout << g[i].size() << " "; 233 else cout << "1 "; 234 } 235 cout << "\n"; 236 return 0; 237 } 238 ``` 239 240 [1646E - Power Board](/contest/1646/problem/E "Codeforces Round 774 (Div. 2)") 241 242 **Solution** 243 244 Tutorial is loading... 245 246 **Additional comment** 247 248 This solution uses the fact that $m\le 10^6$, other solutions do not use this, and work for much larger values of $m$ (like $m\leq 10^{18}$, but taking the answer modulo some big prime number). Try to solve the problem with this new constraint! 249 250 **Code** 251 252 ``` 253 #include <bits/stdc++.h> 254 #define fore(i,a,b) for(ll i=a,ggdem=b;i<ggdem;++i) 255 using namespace std; 256 typedef long long ll; 257 258 const int MAXM = 1000006; 259 260 const int MAXLOGN = 20; 261 262 bool visited_mul[MAXM * MAXLOGN]; 263 264 int main(){ 265 ll n, m; cin >> n >> m; 266 vector<ll> mul_quan(MAXLOGN); 267 ll current_vis = 0; 268 fore(i, 1, MAXLOGN){ 269 fore(j, 1, m+1){ 270 if(!visited_mul[i * j]){ 271 visited_mul[i * j] = 1; 272 current_vis++; 273 } 274 } 275 mul_quan[i] = current_vis; 276 } 277 ll res=1; 278 vector<ll> vis(n + 1); 279 fore(i, 2, n+1){ 280 if(vis[i]) continue; 281 ll power = i, power_quan = 0; 282 while(power <= n){ 283 vis[power] = 1; 284 power_quan++; 285 power *= i; 286 } 287 res += mul_quan[power_quan]; 288 } 289 cout << res << "\n"; 290 291 return 0; 292 } 293 ``` 294 295 [1646F - Playing Around the Table](/contest/1646/problem/F "Codeforces Round 774 (Div. 2)") 296 297 **Solution** 298 299 Tutorial is loading... 300 301 **Code** 302 303 ``` 304 #include <bits/stdc++.h> 305 #define fore(i, a, b) for(int i = a; i < b; ++i) 306 using namespace std; 307 308 const int MAXN = 1010; 309 310 //c[i][j] = number of cards player i has, with the number j 311 int c[MAXN][MAXN]; 312 313 //extras[i] is the stack of repeated cards for player i. 314 vector<int> extras[MAXN]; 315 316 int main(){ 317 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); 318 int n; cin >> n; 319 fore(i, 0, n){ 320 fore(j, 0, n){ 321 int x; cin >> x; x--; 322 c[i][x]++; 323 if(c[i][x] > 1) extras[i].push_back(x); 324 } 325 } 326 vector<vector<int>> res; 327 //First part 328 while(true){ 329 //oper will describe the next operation to perform 330 vector<int> oper(n); 331 //s will be the first non-diverse player 332 int s = -1; 333 fore(i, 0, n){ 334 if(extras[i].size()){ 335 s = i; 336 break; 337 } 338 } 339 if(s == -1) break; 340 //last_card will be the card that the previous player passed 341 int last_card = -1; 342 fore(i, s, s + n){ 343 int real_i = i % n; 344 if(extras[real_i].size()){ 345 last_card = extras[real_i].back(); 346 extras[real_i].pop_back(); 347 } 348 oper[real_i] = last_card; 349 } 350 res.push_back(oper); 351 fore(i, 0, n){ 352 int i_next = (i + 1) % n; 353 c[i][oper[i]]--; 354 c[i_next][oper[i]]++; 355 } 356 fore(i, 0, n){ 357 int i_next = (i + 1) % n; 358 if(c[i_next][oper[i]] > 1) extras[i_next].push_back(oper[i]); 359 } 360 } 361 //Second part 362 fore(j, 1, n){ 363 vector<int> oper; 364 fore(i, 0, n) oper.push_back((i - j + n) % n); 365 fore(i, 0, j) res.push_back(oper); 366 } 367 cout << res.size() << "\n"; 368 for(auto i : res){ 369 for(auto j : i) cout<< j + 1 << " "; 370 cout << "\n"; 371 } 372 return 0; 373 } 374 ``` 375 376 Additionally, [competitive__programmer](/profile/competitive__programmer "Specialist competitive__programmer") has made video editorials for problems [B](https://youtu.be/MIOUg_frJps), [C](https://youtu.be/BoyqQAXtSQg) and [D](https://youtu.be/j7eGgZd9VF0).