codeforces-scrape

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

1598.md (9433B)


      1 Source: https://codeforces.com/blog/entry/95890
      2 
      3 [1598A - Computer Game](/contest/1598/problem/A "Educational Codeforces Round 115 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (BledDest)**
     12 
     13 ```
     14 def solve():
     15 	n = int(input())
     16 	s1 = input()
     17 	s2 = input()
     18 	bad = False
     19 	for i in range(n):
     20 		bad |= s1[i] == '1' and s2[i] == '1'
     21 	if bad:
     22 		print('NO')
     23 	else:
     24 		print('YES')
     25 
     26 t = int(input())
     27 for i in range(t):
     28 	solve()
     29 ```
     30 
     31 [1598B - Groups](/contest/1598/problem/B "Educational Codeforces Round 115 (Rated for Div. 2)")
     32 
     33 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm")
     34 
     35 **Tutorial**
     36 
     37 Tutorial is loading...
     38 
     39 **Solution (BledDest)**
     40 
     41 ```
     42 t = int(input())
     43 for i in range(t):
     44     n = int(input())
     45     a = [[] for i in range(n)]
     46     for j in range(n):
     47         a[j] = list(map(int, input().split()))
     48     ans = False
     49     for j in range(5):
     50         for k in range(5):
     51             if k != j:
     52                 cnt1 = 0
     53                 cnt2 = 0
     54                 cntno = 0
     55                 for z in range(n):
     56                     if a[z][j] == 1:
     57                         cnt1 += 1
     58                     if a[z][k] == 1:
     59                         cnt2 += 1
     60                     if a[z][j] == 0 and a[z][k] == 0:
     61                         cntno += 1
     62                 if cnt1 >= n // 2 and cnt2 >= n // 2 and cntno == 0:
     63                     ans = True
     64     if ans:
     65         print('YES')
     66     else:
     67         print('NO')
     68 ```
     69 
     70 [1598C - Delete Two Elements](/contest/1598/problem/C "Educational Codeforces Round 115 (Rated for Div. 2)")
     71 
     72 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm")
     73 
     74 **Tutorial**
     75 
     76 Tutorial is loading...
     77 
     78 **Solution (Neon)**
     79 
     80 ```
     81 #include <bits/stdc++.h>
     82 
     83 using namespace std;
     84 
     85 int main() {
     86   int t;
     87   scanf("%d", &t);
     88   while (t--) {
     89     int n;
     90     scanf("%d", &n);
     91     vector<int> a(n);
     92     map<int, int> cnt;
     93     for (auto &x : a) {
     94       scanf("%d", &x);
     95       cnt[x] += 1;
     96     }
     97     long long sum = accumulate(a.begin(), a.end(), 0LL);
     98     if ((2 * sum) % n != 0) {
     99       puts("0");
    100       continue;
    101     }
    102     long long need = (2 * sum) / n;
    103     long long ans = 0;
    104     for (int i = 0; i < n; ++i) {
    105       int a1 = a[i];
    106       int a2 = need - a1;
    107       if (cnt.count(a2)) ans += cnt[a2];
    108       if (a1 == a2) ans -= 1;
    109     }
    110     printf("%lld\n", ans / 2);
    111   }
    112 }
    113 ```
    114 
    115 [1598D - Training Session](/contest/1598/problem/D "Educational Codeforces Round 115 (Rated for Div. 2)")
    116 
    117 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    118 
    119 **Tutorial**
    120 
    121 Tutorial is loading...
    122 
    123 **Solution (Neon)**
    124 
    125 ```
    126 #include <bits/stdc++.h>
    127 
    128 using namespace std;
    129 
    130 int main() {
    131   ios_base::sync_with_stdio(false);
    132   cin.tie(NULL); 
    133   int t;
    134   cin >> t;
    135   while (t--) {
    136     int n;
    137     cin >> n;
    138     vector<int> a(n), b(n), ca(n + 1), cb(n + 1);
    139     for (int i = 0; i < n; ++i) {
    140       cin >> a[i] >> b[i];
    141       ca[a[i]]++; cb[b[i]]++;
    142     }
    143     long long ans = n * 1LL * (n - 1) * (n - 2) / 6;
    144     for (int i = 0; i < n; ++i) 
    145       ans -= (ca[a[i]] - 1) * 1LL * (cb[b[i]] - 1);
    146     cout << ans << '\n';
    147   }
    148 }
    149 ```
    150 
    151 [1598E - Staircases](/contest/1598/problem/E "Educational Codeforces Round 115 (Rated for Div. 2)")
    152 
    153 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    154 
    155 **Tutorial**
    156 
    157 Tutorial is loading...
    158 
    159 **Solution (awoo)**
    160 
    161 ```
    162 #include <bits/stdc++.h>
    163 
    164 #define forn(i, n) for (int i = 0; i < int(n); i++)
    165 
    166 using namespace std;
    167 
    168 int main() {
    169 	int n, m, q;
    170 	scanf("%d%d%d", &n, &m, &q);
    171 	vector<vector<int>> a(n, vector<int>(m, 1));
    172 	long long ans = 0;
    173 	forn(x, n) forn(y, m){
    174 		if (x == 0){
    175 			for (int k = 1;; ++k){
    176 				int nx = x + k / 2;
    177 				int ny = y + (k + 1) / 2;
    178 				if (nx == n || ny == m) break;
    179 				ans += k;
    180 			}
    181 		}
    182 		if (y == 0){
    183 			for (int k = 1;; ++k){
    184 				int nx = x + (k + 1) / 2;
    185 				int ny = y + k / 2;
    186 				if (nx == n || ny == m) break;
    187 				ans += k;
    188 			}
    189 		}
    190 	}
    191 	ans += n * m;
    192 	forn(i, q){
    193 		int x, y;
    194 		scanf("%d%d", &x, &y);
    195 		--x, --y;
    196 		forn(c, 2){
    197 			int l = 1, r = 1;
    198 			while (true){
    199 				int nx = x + (l + c) / 2;
    200 				int ny = y + (l + !c) / 2;
    201 				if (nx == n || ny == m || a[nx][ny] == 0) break;
    202 				++l;
    203 			}
    204 			while (true){
    205 				int nx = x - (r + !c) / 2;
    206 				int ny = y - (r + c) / 2;
    207 				if (nx < 0 || ny < 0 || a[nx][ny] == 0) break;
    208 				++r;
    209 			}
    210 			if (a[x][y] == 0){
    211 				ans += l * r;
    212 			}
    213 			else{
    214 				ans -= l * r;
    215 			}
    216 		}
    217 		ans += a[x][y];
    218 		a[x][y] ^= 1;
    219 		ans -= a[x][y];
    220 		printf("%lld\n", ans);
    221 	}
    222 }
    223 ```
    224 
    225 [1598F - RBS](/contest/1598/problem/F "Educational Codeforces Round 115 (Rated for Div. 2)")
    226 
    227 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    228 
    229 **Tutorial**
    230 
    231 Tutorial is loading...
    232 
    233 **Solution (BledDest)**
    234 
    235 ```
    236 #include <bits/stdc++.h>     
    237 
    238 using namespace std;
    239 
    240 const int INF = int(1e9);
    241 
    242 const int N = 20;
    243 const int M = (1 << N);
    244 
    245 struct BracketSeqn
    246 {
    247  	int balance;
    248  	int lowestBalance;
    249  	vector<int> queryAns;
    250 
    251  	pair<int, bool> go(int x, bool f)
    252  	{
    253      	if(f)
    254      		return make_pair(0, true);
    255        	else
    256        		return make_pair(x < queryAns.size() ? queryAns[x] : 0, x + lowestBalance < 0);
    257     }
    258 
    259 	BracketSeqn() {};
    260 	BracketSeqn(string s)
    261 	{
    262 		vector<int> bal;
    263 		int cur = 0;
    264 		int n = s.size();
    265 		for(auto x : s)
    266 		{
    267 		 	if(x == '(')
    268 		 		cur++;
    269 		 	else	
    270 		 		cur--;
    271 		 	bal.push_back(cur);	
    272 		}
    273 		balance = bal.back();
    274 		lowestBalance = min(0, *min_element(bal.begin(), bal.end()));
    275 		vector<vector<int>> negPos(-lowestBalance + 1);
    276 		for(int i = 0; i < n; i++)
    277 		{
    278 		 	if(bal[i] > 0) continue;
    279 		 	negPos[-bal[i]].push_back(i);
    280 		}
    281 		queryAns.resize(-lowestBalance + 1);
    282 		for(int i = 0; i < queryAns.size(); i++)
    283 		{
    284 		 	int lastPos = int(1e9);
    285 		 	if(i != -lowestBalance)
    286 		 		lastPos = negPos[i + 1][0];
    287 		 	queryAns[i] = lower_bound(negPos[i].begin(), negPos[i].end(), lastPos) - negPos[i].begin();
    288 		}
    289 	};
    290 };
    291 
    292 int dp[M][2];
    293 char buf[M];
    294 int total_bal[M];
    295 
    296 int main()
    297 {
    298 	int n;
    299 	scanf("%d", &n);
    300 	vector<BracketSeqn> bs;
    301 	for(int i = 0; i < n; i++)
    302 	{
    303 	 	scanf("%s", buf);
    304 	 	string s = buf;
    305 	 	bs.push_back(BracketSeqn(s));
    306 	}
    307 	for(int i = 0; i < (1 << n); i++)               
    308 	 	for(int j = 0; j < n; j++)
    309 	 		if(i & (1 << j))
    310 	 			total_bal[i] += bs[j].balance;
    311 	for(int i = 0; i < (1 << n); i++)
    312 		for(int j = 0; j < 2; j++)
    313 			dp[i][j] = -int(1e9);
    314 	dp[0][0] = 0;
    315 	for(int i = 0; i < (1 << n); i++)
    316 		for(int f = 0; f < 2; f++)
    317 		{
    318 		 	if(dp[i][f] < 0) continue;
    319 		 	for(int k = 0; k < n; k++)
    320 		 	{
    321 		 	 	if(i & (1 << k)) continue;
    322 		 	 	pair<int, bool> res = bs[k].go(total_bal[i], f);
    323 		 	 	dp[i ^ (1 << k)][res.second] = max(dp[i ^ (1 << k)][res.second], dp[i][f] + res.first);
    324 		 	}
    325 		}
    326 	printf("%d\n", max(dp[(1 << n) - 1][0], dp[(1 << n) - 1][1]));
    327 }
    328 ```
    329 
    330 [1598G - The Sum of Good Numbers](/contest/1598/problem/G "Educational Codeforces Round 115 (Rated for Div. 2)")
    331 
    332 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    333 
    334 **Tutorial**
    335 
    336 Tutorial is loading...
    337 
    338 **Solution (Neon)**
    339 
    340 ```
    341 #include <bits/stdc++.h>
    342 
    343 using namespace std;
    344 
    345 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    346 
    347 const int MOD[] = { 597804841, 618557587, 998244353 };
    348 const int N = 500 * 1000 + 13;
    349 const int K = 3;
    350 
    351 using hs = array<int, K>;
    352 
    353 int add(int x, int y, int mod) {
    354   x += y;
    355   if (x >= mod) x -= mod;
    356   if (x < 0) x += mod;
    357   return x;
    358 }
    359 
    360 int mul(int x, int y, int mod) {
    361   return x * 1LL * y % mod;
    362 }
    363 
    364 hs get(const int& x) {
    365   hs c;
    366   forn(i, K) c[i] = x;
    367   return c;
    368 }
    369 
    370 hs operator +(const hs& a, const hs& b) { 
    371   hs c;
    372   forn(i, K) c[i] = add(a[i], b[i], MOD[i]);
    373   return c;
    374 }
    375 
    376 hs operator -(const hs& a, const hs& b) {
    377   hs c;
    378   forn(i, K) c[i] = add(a[i], -b[i], MOD[i]);
    379   return c; 
    380 }
    381 
    382 hs operator *(const hs& a, const hs& b) {
    383   hs c;
    384   forn(i, K) c[i] = mul(a[i], b[i], MOD[i]);
    385   return c; 
    386 }
    387 
    388 int n, m;
    389 string s, sx;
    390 hs sum[N], pw[N];
    391 
    392 hs get(int l, int r) {
    393   return sum[r] - sum[l] * pw[r - l];
    394 }
    395 
    396 vector<int> zfunction(const string& s) {
    397   int n = s.size();
    398   vector<int> z(n);
    399   int l = 0, r = 0;
    400   for (int i = 1; i < n; ++i) {
    401     if (i <= r) z[i] = min(z[i - l], r - i + 1);
    402     while (i + z[i] < n && s[z[i]] == s[i + z[i]])
    403       ++z[i];
    404     if (i + z[i] - 1 > r) {
    405       l = i;
    406       r = i + z[i] - 1;
    407     }
    408   }
    409   return z;
    410 }
    411 
    412 int main() {
    413   ios_base::sync_with_stdio(false);
    414   cin.tie(NULL); 
    415   
    416   cin >> s >> sx;
    417   n = s.size();
    418   m = sx.size();
    419   
    420   pw[0] = get(1);
    421   forn(i, N - 1) pw[i + 1] = pw[i] * get(10); 
    422   sum[0] = get(0);
    423   forn(i, n) sum[i + 1] = sum[i] * get(10) + get(s[i] - '0'); 
    424   hs x = get(0);
    425   forn(i, m) x = x * get(10) + get(sx[i] - '0');
    426   
    427   if (m > 1) for (int i = 0; i + 2 * (m - 1) <= n; ++i) {
    428     if (get(i, i + m - 1) + get(i + m - 1, i + 2 * (m - 1)) == x) {
    429       cout << i + 1 << ' ' << i + m - 1 << '\n';
    430       cout << i + m << ' ' << i + 2 * (m - 1) << '\n';
    431       return 0;
    432     }
    433   }
    434   
    435   auto z = zfunction(sx + "#" + s);
    436   
    437   for (int i = 0; i + m <= n; ++i) {
    438     int lcp = z[m + i + 1];
    439     for (int len = m - lcp - 1; len <= m - lcp; ++len) {
    440       if (len < 1) continue;
    441       if (i + m + len <= n && get(i, i + m) + get(i + m, i + m + len) == x) {
    442         cout << i + 1 << ' ' << i + m << '\n';
    443         cout << i + m + 1 << ' ' << i + m + len << '\n';
    444         return 0;
    445       }
    446       if (i >= len && get(i - len, i) + get(i, i + m) == x) {
    447         cout << i - len + 1 << ' ' << i << '\n';
    448         cout << i + 1 << ' ' << i + m << '\n';
    449         return 0;
    450       }
    451     }
    452   }
    453   
    454   assert(false);
    455 }
    456 ```