codeforces-scrape

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

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