codeforces-scrape

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

1914.md (6517B)


      1 Source: https://codeforces.com/blog/entry/123530
      2 
      3 [1914A - Problemsolving Log](/contest/1914/problem/A "Codeforces Round 916 (Div. 3)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (awoo)**
     12 
     13 ```
     14 for _ in range(int(input())):
     15     n = int(input())
     16     s = input()
     17     print(sum([s.count(chr(ord('A') + i)) >= i + 1 for i in range(26)]))
     18 ```
     19 
     20 [1914B - Preparing for the Contest](/contest/1914/problem/B "Codeforces Round 916 (Div. 3)")
     21 
     22 Idea: [Roms](/profile/Roms "Master Roms")
     23 
     24 **Tutorial**
     25 
     26 Tutorial is loading...
     27 
     28 **Solution (BledDest)**
     29 
     30 ```
     31 #include<bits/stdc++.h>
     32  
     33 using namespace std;
     34  
     35 void solve()
     36 {
     37 	int n, k;
     38 	cin >> n >> k;
     39 	vector<int> a(n);
     40 	for(int i = 0; i < n; i++) a[i] = n - i;
     41 	reverse(a.end() - k - 1, a.end());
     42 	for(int i = 0; i < n; i++)
     43 	{
     44 		if(i) cout << " ";
     45 		cout << a[i];
     46 	}
     47 	cout << endl;
     48 }
     49  
     50 int main()
     51 {
     52 	int t;
     53 	cin >> t;
     54 	for(int i = 0; i < t; i++)
     55 		solve();
     56 	return 0;
     57 }
     58 ```
     59 
     60 [1914C - Quests](/contest/1914/problem/C "Codeforces Round 916 (Div. 3)")
     61 
     62 Idea: [Roms](/profile/Roms "Master Roms")
     63 
     64 **Tutorial**
     65 
     66 Tutorial is loading...
     67 
     68 **Solution (Neon)**
     69 
     70 ```
     71 fun main() = repeat(readLine()!!.toInt()) {
     72   val (n, k) = readLine()!!.split(" ").map { it.toInt() }
     73   val a = readLine()!!.split(" ").map { it.toInt() }
     74   val b = readLine()!!.split(" ").map { it.toInt() }
     75   var (res, sum, mx) = intArrayOf(0, 0, 0)
     76   for (i in 0 until minOf(n, k)) {
     77     sum += a[i]
     78     mx = maxOf(mx, b[i])
     79     res = maxOf(res, sum + mx * (k - i - 1))
     80   }
     81   println(res)
     82 }
     83 ```
     84 
     85 [1914D - Three Activities](/contest/1914/problem/D "Codeforces Round 916 (Div. 3)")
     86 
     87 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     88 
     89 **Tutorial**
     90 
     91 Tutorial is loading...
     92 
     93 **Solution (awoo)**
     94 
     95 ```
     96 for _ in range(int(input())):
     97 	n = int(input())
     98 	a = list(map(int, input().split()))
     99 	b = list(map(int, input().split()))
    100 	c = list(map(int, input().split()))
    101 	
    102 	def get_best3(a):
    103 		mx1, mx2, mx3 = -1, -1, -1
    104 		for i in range(len(a)):
    105 			if mx1 == -1 or a[i] > a[mx1]:
    106 				mx3 = mx2
    107 				mx2 = mx1
    108 				mx1 = i
    109 			elif mx2 == -1 or a[i] > a[mx2]:
    110 				mx3 = mx2
    111 				mx2 = i
    112 			elif mx3 == -1 or a[i] > a[mx3]:
    113 				mx3 = i
    114 		return (mx1, mx2, mx3)
    115 	
    116 	ans = 0
    117 	for x in get_best3(a):
    118 		for y in get_best3(b):
    119 			for z in get_best3(c):
    120 				if x != y and x != z and y != z:
    121 					ans = max(ans, a[x] + b[y] + c[z])
    122 	print(ans)
    123 ```
    124 
    125 [1914E1 - Game with Marbles (Easy Version)](/contest/1914/problem/E1 "Codeforces Round 916 (Div. 3)")
    126 
    127 [1914E2 - Game with Marbles (Hard Version)](/contest/1914/problem/E2 "Codeforces Round 916 (Div. 3)")
    128 
    129 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    130 
    131 **Tutorial**
    132 
    133 Tutorial is loading...
    134 
    135 **Solution (adedalic)**
    136 
    137 ```
    138 #include<bits/stdc++.h>
    139  
    140 using namespace std;
    141  
    142 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    143 #define sz(a) int((a).size())
    144  
    145 typedef long long li;
    146  
    147 // S = sum a_i - sum b_i
    148 // if Bob made all steps: then S = 0 - sum (b_i - 1)
    149 // each Alice step: S += (a_i - 1) + (b_i - 1) i. e. the bigger (a_i + b_i) the better
    150  
    151 int n;
    152 vector<int> a, b;
    153  
    154 inline bool read() {
    155 	if(!(cin >> n))
    156 		return false;
    157 	a.resize(n);
    158 	b.resize(n);
    159 	fore (i, 0, n)
    160 		cin >> a[i];
    161 	fore (i, 0, n)
    162 		cin >> b[i];
    163 	return true;
    164 }
    165  
    166 inline void solve() {
    167 	vector<int> ids(n);
    168 	iota(ids.begin(), ids.end(), 0);
    169 	
    170 	sort(ids.begin(), ids.end(), [&](int i, int j) {
    171 		return a[i] + b[i] > a[j] + b[j];
    172 	});
    173 	
    174 	li S = 0;
    175 	fore (i, 0, n) {
    176 		if (i & 1)
    177 			S -= b[ids[i]] - 1;
    178 		else
    179 			S += a[ids[i]] - 1;
    180 	}
    181 	cout << S << endl;
    182 }
    183  
    184 int main() {
    185 #ifdef _DEBUG
    186 	freopen("input.txt", "r", stdin);
    187 	int tt = clock();
    188 #endif
    189 //	ios_base::sync_with_stdio(false);
    190 //	cin.tie(0), cout.tie(0);
    191 	cout << fixed << setprecision(15);
    192 	int t;
    193 	cin >> t;
    194 	for(int i = 0; i < t; i++)
    195 	{
    196 	if(read()) {
    197 		solve();
    198 		
    199 #ifdef _DEBUG
    200 		cerr << "TIME = " << clock() - tt << endl;
    201 		tt = clock();
    202 #endif
    203 	}
    204 	}
    205 	return 0;
    206 }
    207 ```
    208 
    209 [1914F - Programming Competition](/contest/1914/problem/F "Codeforces Round 916 (Div. 3)")
    210 
    211 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    212 
    213 **Tutorial**
    214 
    215 Tutorial is loading...
    216 
    217 **Solution (Neon)**
    218 
    219 ```
    220 #include <bits/stdc++.h>
    221  
    222 using namespace std;
    223  
    224 const int N = 222222;
    225  
    226 int n;
    227 int sz[N];
    228 vector<int> g[N];
    229  
    230 void init(int v) {
    231   sz[v] = 1;
    232   for (int u : g[v]) {
    233     init(u);
    234     sz[v] += sz[u];
    235   }
    236 }
    237  
    238 int calc(int v, int k) {
    239   int tot = 0, mx = -1;
    240   for (int u : g[v]) {
    241     tot += sz[u];
    242     if (mx == -1 || sz[mx] < sz[u]) mx = u;
    243   }
    244   if (tot == 0) return 0;
    245   if (sz[mx] - k <= tot - sz[mx])
    246     return (tot - k) / 2;
    247   int add = tot - sz[mx];
    248   return add + calc(mx, max(0, k + add - 1));
    249 }
    250  
    251 int main() {
    252   ios::sync_with_stdio(false); cin.tie(0);
    253   int t;
    254   cin >> t;
    255   while (t--) {
    256     cin >> n;
    257     for (int i = 0; i < n; ++i) g[i].clear();
    258     for (int i = 1; i < n; ++i) {
    259       int p; cin >> p;
    260       g[p - 1].push_back(i);
    261     }
    262     init(0);
    263     cout << calc(0, 0) << '\n';
    264   }
    265 }
    266 ```
    267 
    268 [1914G1 - Light Bulbs (Easy Version)](/contest/1914/problem/G1 "Codeforces Round 916 (Div. 3)")
    269 
    270 [1914G2 - Light Bulbs (Hard Version)](/contest/1914/problem/G2 "Codeforces Round 916 (Div. 3)")
    271 
    272 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    273 
    274 **Tutorial**
    275 
    276 Tutorial is loading...
    277 
    278 **Solution (BledDest)**
    279 
    280 ```
    281 #include<bits/stdc++.h>
    282  
    283 using namespace std;
    284  
    285 const int MOD = 998244353;
    286  
    287 int add(int x, int y)
    288 {
    289 	return (((x + y) % MOD) + MOD) % MOD;
    290 }
    291  
    292 int mul(int x, int y)
    293 {
    294 	return (x * 1ll * y) % MOD;
    295 }
    296  
    297 mt19937_64 rnd(98275314);
    298  
    299 long long gen()
    300 {
    301 	long long x = 0;
    302 	while(x == 0)
    303 		x = rnd();
    304 	return x;
    305 }
    306  
    307 vector<int> c;
    308 vector<int> g;
    309  
    310 int process_block(int l, int r)
    311 {
    312 	int ans = 0;
    313 	while(l < r)
    314 	{
    315 		if(g[l] != -1 && g[l] < r)
    316 			l = g[l];
    317 		else
    318 		{
    319 			ans++;
    320 			l++;
    321 		}
    322 	}
    323 	return ans;
    324 }
    325  
    326 void solve()
    327 {
    328 	int n;
    329 	scanf("%d", &n);
    330 	int size = 0, cnt = 1;
    331 	c.resize(n * 2);
    332 	g.resize(n * 2, -1);
    333 	for(int i = 0; i < 2 * n; i++)
    334 	{
    335 		scanf("%d", &c[i]);
    336 		--c[i];
    337 	}
    338 	
    339 	vector<long long> val(n);
    340 	for(int i = 0; i < n; i++) val[i] = gen();
    341 	
    342 	map<long long, int> last;
    343 	long long cur = 0;
    344 	last[0] = 0;
    345 	for(int i = 0; i < n * 2; i++)
    346 	{
    347 		cur ^= val[c[i]];
    348 		if(cur == 0)
    349 		{
    350 			size++;
    351 			cnt = mul(cnt, process_block(last[0], i + 1));
    352 			last.clear();
    353 		}
    354 		else if(last.count(cur))
    355 		{
    356 			g[last[cur]] = i + 1;
    357 		}
    358 		last[cur] = i + 1;
    359 	}
    360 	
    361 	printf("%d %d\n", size, cnt);
    362 	c.clear();
    363 	g.clear();
    364 }
    365  
    366 int main()
    367 {
    368 	int t;
    369 	scanf("%d", &t);
    370 	for(int i = 0; i < t; i++) solve();
    371 }
    372 ```