codeforces-scrape

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

924.md (15121B)


      1 Source: https://codeforces.com/blog/entry/58544
      2 
      3 Long time no see!
      4 
      5 As [VK Cup Round 2](//codeforces.com/contest/924) and its two parallel rounds ([Div. 1](//codeforces.com/contest/956) and [Div. 2](//codeforces.com/contest/957)) comes to a close, we're here to congratulate on all who did well on the contest and cheer for everyone who participated — the queue won't stop you!
      6 
      7 Here are the detailed tutorials for the problems. Feel free to discuss in the comments!
      8 
      9 Kudos to [arsor](/profile/arsor "Specialist arsor") for translating the tutorials into Russian!
     10 
     11 ---
     12 
     13 Tutorial is loading...
     14 
     15 **Model solution**
     16 
     17 ```
     18 _, s = input(), input()
     19 print('Yes' if
     20     ('??' in s or 'C?C' in s or 'M?M' in s or 'Y?Y' in s or s[0] == '?' or s[-1] == '?') and
     21     not ('CC' in s or 'MM' in s or 'YY' in s)
     22 else 'No')
     23 ```
     24 
     25 **Alternative solution (Errichto)**
     26 
     27 ```
     28 #include <bits/stdc++.h>
     29 using namespace std;
     30 
     31 void NO() {
     32 	puts("No");
     33 	exit(0);
     34 }
     35 void YES() {
     36 	puts("Yes");
     37 	exit(0);
     38 }
     39 
     40 int main() {
     41 	int n;
     42 	cin >> n;
     43 	string s;
     44 	cin >> s;
     45 	for(int i = 0; i < n - 1; ++i)
     46 		if(s[i] != '?' && s[i] == s[i+1])
     47 			NO();
     48 	for(int i = 0; i < n; ++i) if(s[i] == '?') {
     49 		if(i == 0 || i == n - 1) YES();
     50 		if(s[i+1] == '?') YES();
     51 		if(s[i-1] == s[i+1]) YES();
     52 	}
     53 	NO();
     54 }
     55 ```
     56 
     57 (by [cyand1317](/profile/cyand1317 "Grandmaster cyand1317"))
     58 
     59 Tutorial is loading...
     60 
     61 **Model solution**
     62 
     63 ```
     64 #include <cstdio>
     65 
     66 typedef long long int64;
     67 static const int MAXN = 53;
     68 
     69 static int n, m;
     70 static bool a[MAXN][MAXN];
     71 static int64 b[MAXN];
     72 
     73 int main()
     74 {
     75     scanf("%d%d", &n, &m); getchar();
     76     for (int i = 0; i < n; ++i)
     77         for (int j = 0; j <= m; ++j) a[i][j] = (getchar() == '#');
     78 
     79     for (int i = 0; i < n - 1; ++i)
     80         for (int j = i + 1; j < n; ++j) {
     81             bool all_same = true, no_intersect = true;
     82             for (int k = 0; k < m; ++k) {
     83                 if (a[i][k] != a[j][k]) all_same = false;
     84                 if (a[i][k] && a[j][k]) no_intersect = false;
     85             }
     86             if (!all_same && !no_intersect) {
     87                 puts("No"); return 0;
     88             }
     89         }
     90 
     91     puts("Yes"); return 0;
     92 }
     93 ```
     94 
     95 **Alternative solution with DSU in O(nm alpha(n)) (skywalkert)**
     96 
     97 ```
     98 #include <bits/stdc++.h>
     99 using namespace std;
    100 const int maxn = 5001, maxm = maxn << 1 | 1;
    101 int n, m, dsu[maxm], cB[maxm], cW[maxm], cE[maxm];
    102 char buf[maxn];
    103 int dsu_find(int u) {
    104 	return dsu[u] < 0 ? u : (dsu[u] = dsu_find(dsu[u]));
    105 }
    106 void dsu_merge(int u, int v) {
    107 	u = dsu_find(u);
    108 	v = dsu_find(v);
    109 	if(u == v) {
    110 		++cE[u];
    111 		return;
    112 	}
    113 	if(dsu[u] < dsu[v])
    114 		swap(u, v);
    115 	dsu[v] -= dsu[u] == dsu[v];
    116 	dsu[u] = v;
    117 	cB[v] += cB[u];
    118 	cW[v] += cW[u];
    119 	cE[v] += cE[u] + 1;
    120 }
    121 int main() {
    122 	scanf("%d%d", &n, &m);
    123 	memset(dsu, -1, (n + m) * sizeof(int));
    124 	for(int i = 0; i < n; ++i)
    125 		cB[i] = 1;
    126 	for(int i = 0; i < m; ++i)
    127 		cW[n + i] = 1;
    128 	for(int i = 0; i < n; ++i) {
    129 		scanf("%s", buf);
    130 		for(int j = 0; j < m; ++j)
    131 			if(buf[j] != '.')
    132 				dsu_merge(i, n + j);
    133 	}
    134 	for(int i = 0; i < n + m; ++i)
    135 		if(dsu_find(i) == i && cB[i] * cW[i] != cE[i]) {
    136 			puts("No");
    137 			return 0;
    138 		}
    139 	puts("Yes");
    140 	return 0;
    141 }
    142 ```
    143 
    144 **Alternative solution in O(nm)**
    145 
    146 ```
    147 #include <cstdio>
    148 #include <algorithm>
    149 #include <vector>
    150 static const int MAXN = 1004;
    151 
    152 static int n, m;
    153 static bool g[MAXN][MAXN];
    154 // c[i] = set of rows where the i-th column is coloured
    155 static std::vector<int> c[MAXN];
    156 static bool checked[MAXN] = { false };
    157 
    158 int main()
    159 {
    160     scanf("%d%d", &n, &m); getchar();
    161     for (int i = 0; i < n; ++i)
    162         for (int j = 0; j <= m; ++j) {
    163             g[i][j] = (getchar() == '#');
    164             if (g[i][j]) c[j].push_back(i);
    165         }
    166 
    167     for (int i = 0; i < n; ++i) if (!checked[i]) {
    168         std::vector<int> r;
    169         for (int j = 0; j < m; ++j) if (g[i][j])
    170             for (int k : c[j]) r.push_back(k);
    171         std::sort(r.begin(), r.end());
    172         r.resize(std::unique(r.begin(), r.end()) - r.begin());
    173 
    174         for (int k : r) {
    175             if (checked[k]) { puts("No"); return 0; }
    176             checked[k] = true;
    177             for (int p = 0; p < m; ++p)
    178                 if (g[i][p] != g[k][p]) { puts("No"); return 0; }
    179         }
    180     }
    181 
    182     puts("Yes"); return 0;
    183 }
    184 ```
    185 
    186 (by [cyand1317](/profile/cyand1317 "Grandmaster cyand1317"))
    187 
    188 Tutorial is loading...
    189 
    190 **Model solution**
    191 
    192 ```
    193 #include <iostream>
    194 #include <sstream>
    195 #include <cstdio>
    196 #include <vector>
    197 #include <cmath>
    198 #include <queue>
    199 #include <string>
    200 #include <cstring>
    201 #include <cassert>
    202 #include <iomanip>
    203 #include <algorithm>
    204 #include <set>
    205 #include <map>
    206 #include <ctime>
    207 #include <cmath>
    208 
    209 #define forn(i, n) for(int i=0;i<n;++i)
    210 #define fore(i, l, r) for(int i = int(l); i <= int(r); ++i)
    211 #define sz(v) int(v.size())
    212 #define all(v) v.begin(), v.end()
    213 #define pb push_back
    214 #define mp make_pair
    215 #define x first
    216 #define y1 ________y1
    217 #define y second
    218 #define ft first
    219 #define sc second
    220 #define pt pair<int, int>
    221 
    222 template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
    223 template<typename X> inline X sqr(const X& a) { return a * a; }
    224 
    225 typedef long long li;
    226 typedef long double ld;
    227 
    228 using namespace std;
    229 
    230 const int INF = 1000 * 1000 * 1000;
    231 const ld EPS = 1e-9;
    232 const ld PI = acos(-1.0);
    233 
    234 const int N = 100 * 1000 + 13;
    235 
    236 int n, u;
    237 int a[N];
    238 int idx1 = -1, idx2, idx3;
    239 
    240 inline void read() {	
    241 	scanf("%d%d", &n, &u);
    242 	for (int i = 0; i < n; i++) {
    243 		scanf("%d", &a[i]);
    244 	}
    245 }
    246 
    247 inline void solve() {
    248 	int k = 0;
    249 	for (int i = 0; i < n; i++) {
    250 		k = max(k, i);
    251 		while (k + 1 < n && a[k + 1] - a[i] <= u) {
    252       		k++;
    253 		}
    254         if (k - i - 1 <= 0) {
    255         	continue;
    256         }
    257         int j = i + 1;
    258 
    259         if (idx1 == -1 || (a[k] - a[j]) * 1ll * (a[idx3] - a[idx1]) > (a[idx3] - a[idx2]) * 1ll * (a[k] - a[i])) {
    260 			idx1 = i, idx2 = j, idx3 = k;        	
    261         }
    262 	}	
    263 
    264 	if (idx1 == -1) {
    265 		cout << -1 << endl;
    266 		return;
    267 	}
    268 
    269 	cout.precision(20);
    270     cout << (double)(a[idx3] - a[idx2]) / (a[idx3] - a[idx1]) << endl;
    271 }
    272 
    273 int main () {
    274 #ifdef fcspartakm
    275     freopen("input.txt", "r", stdin);
    276     //freopen("output.txt", "w", stdout);
    277 #endif
    278     srand(time(NULL));
    279     cerr << setprecision(10) << fixed;
    280     
    281     read();
    282     solve();
    283  
    284     //cerr << "TIME: " << clock() << endl;
    285 }
    286 ```
    287 
    288 (by [KAN](/profile/KAN "Grandmaster KAN"), prepared by [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm"))
    289 
    290 Tutorial is loading...
    291 
    292 **Model solution**
    293 
    294 ```
    295 #include <cstdio>
    296 #include <algorithm>
    297 
    298 typedef long long int64;
    299 static const int MAXN = 1e5 + 4;
    300 
    301 static int n, m[MAXN];
    302 static int t[MAXN];
    303 
    304 int main()
    305 {
    306     scanf("%d", &n);
    307     for (int i = 0; i < n; ++i) scanf("%d", &m[i]);
    308 
    309     for (int i = n - 1, cur = 0; i >= 0; --i) {
    310         cur = std::max(0, cur - 1);
    311         cur = std::max(cur, m[i] + 1);
    312         t[i] = cur;
    313     }
    314 
    315     int64 ans = 0;
    316     for (int i = 0, cur = 0; i < n; ++i) {
    317         cur = std::max(cur, t[i]);
    318         ans += cur;
    319     }
    320 
    321     for (int i = 0; i < n; ++i) ans -= (m[i] + 1);
    322     printf("%lld\n", ans);
    323 
    324     return 0;
    325 }
    326 ```
    327 
    328 (by [cyand1317](/profile/cyand1317 "Grandmaster cyand1317"))
    329 
    330 Tutorial is loading...
    331 
    332 **Model solution**
    333 
    334 ```
    335 #include <cstdio>
    336 #include <algorithm>
    337 #include <utility>
    338 
    339 typedef long long int64;
    340 static const int MAXN = 1e5 + 4;
    341 static const int MAXX = 1e8 + 4;
    342 
    343 static int n, w;
    344 static int x[MAXN], v[MAXN];
    345 
    346 struct fraction {
    347     template <typename T> static inline T gcd(const T a, const T b) {
    348         return (b == 0) ? a : gcd(b, a % b);
    349     }
    350 
    351     int64 num, deno;
    352     inline void simplify() {
    353         if (deno < 0) { num *= -1; deno *= -1; }
    354         int64 g = gcd(num < 0 ? -num : num, deno); num /= g; deno /= g;
    355     }
    356 
    357     fraction() { }
    358     fraction(int64 num, int64 deno) : num(num), deno(deno) { simplify(); }
    359 
    360     inline bool operator < (const fraction &rhs) const {
    361         return num * rhs.deno < deno * rhs.num;
    362     }
    363     inline bool operator != (const fraction &rhs) const {
    364         return num * rhs.deno != deno * rhs.num;
    365     }
    366 };
    367 
    368 // Time bounds at which clouds can arrive at the origin
    369 static std::pair<fraction, fraction> t[MAXN];
    370 // Used at discretization
    371 static std::pair<fraction, int> d[MAXN];
    372 static int p[MAXN];
    373 
    374 struct bit {
    375     static const int MAXN = ::MAXN;
    376     int f[MAXN];
    377     bit() { std::fill(f, f + MAXN, 0); }
    378     inline void add(int pos, int inc) {
    379         for (++pos; pos < MAXN; pos += (pos & -pos)) f[pos] += inc;
    380     }
    381     inline int sum(int rg) {
    382         int ans = 0;
    383         for (++rg; rg; rg -= (rg & -rg)) ans += f[rg];
    384         return ans;
    385     }
    386     inline int sum(int lf, int rg) {
    387         return sum(rg) - sum(lf - 1);
    388     }
    389 } arkady;
    390 
    391 int main()
    392 {
    393     scanf("%d%d", &n, &w);
    394     for (int i = 0; i < n; ++i) scanf("%d%d", &x[i], &v[i]);
    395 
    396     for (int i = 0; i < n; ++i) {
    397         int64 v1 = v[i] - w, v2 = v[i] + w;
    398         t[i] = {fraction(-x[i], v1), fraction(-x[i], v2)};
    399     }
    400 
    401     for (int i = 0; i < n; ++i) t[i].second.num *= -1;
    402     std::sort(t, t + n);
    403     for (int i = 0; i < n; ++i) t[i].second.num *= -1;
    404     for (int i = 0; i < n; ++i) d[i] = {t[i].second, i};
    405     std::sort(d, d + n);
    406     for (int i = 0, rk = -1; i < n; ++i) {
    407         if (i == 0 || d[i].first != d[i - 1].first) ++rk;
    408         p[d[i].second] = rk;
    409     }
    410     /*for (int i = 0; i < n; ++i)
    411         printf("%.4lf %.4lf | %d\n",
    412             (double)t[i].first.num / t[i].first.deno,
    413             (double)t[i].second.num / t[i].second.deno, p[i]);*/
    414 
    415     int64 ans = 0;
    416     for (int i = 0; i < n; ++i) {
    417         ans += arkady.sum(p[i], MAXN - 1);
    418         arkady.add(p[i], 1);
    419     }
    420 
    421     printf("%lld\n", ans);
    422 
    423     return 0;
    424 }
    425 ```
    426 
    427 (by [KAN](/profile/KAN "Grandmaster KAN"), prepared by [cyand1317](/profile/cyand1317 "Grandmaster cyand1317"))
    428 
    429 Tutorial is loading...
    430 
    431 **Model solution**
    432 
    433 ```
    434 /**
    435  * This is a solution for problem wardrobe
    436  * This is nk_ok.cpp
    437  * 
    438  * @author: Nikolay Kalinin
    439  * @date: Tue, 20 Mar 2018 21:48:33 +0300
    440  */
    441 #include <bits/stdc++.h>
    442 
    443 using namespace std;
    444 
    445 using ll = long long;
    446 using ld = long double;
    447 using D = double;
    448 using uint = unsigned int;
    449 template<typename T>
    450 using pair2 = pair<T, T>;
    451 
    452 #ifdef WIN32
    453     #define LLD "%I64d"
    454 #else
    455     #define LLD "%lld"
    456 #endif
    457 
    458 #define pb push_back
    459 #define mp make_pair
    460 #define all(x) (x).begin(),(x).end()
    461 #define fi first
    462 #define se second
    463 
    464 struct tbox
    465 {
    466     int h, t;
    467 };
    468 
    469 inline bool operator<(const tbox &a, const tbox &b)
    470 {
    471     if (a.t != b.t) return a.t < b.t;
    472     return a.h > b.h;
    473 }
    474 
    475 const int maxn = 10005;
    476 const int inf = 1e9;
    477 
    478 tbox b[maxn];
    479 int ans[maxn];
    480 int n, l, r;
    481 
    482 int main()
    483 {
    484     scanf("%d%d%d", &n, &l, &r);
    485     int sumh = 0;
    486     for (int i = 0; i < n; i++)
    487     {
    488         scanf("%d", &b[i].h);
    489         sumh += b[i].h;
    490     }
    491     tie(l, r) = pair{sumh - r, sumh - l};
    492     for (int i = 0; i < n; i++) scanf("%d", &b[i].t);
    493     sort(b, b + n);
    494     for (int i = 0; i <= sumh; i++) ans[i] = -inf;
    495     ans[0] = 0;
    496     for (int i = 0; i < n; i++)
    497     {
    498         for (int h = sumh - b[i].h; h >= 0; h--) ans[h + b[i].h] = max(ans[h + b[i].h], ans[h] + b[i].t * (h + b[i].h >= l && h + b[i].h <= r));
    499     }
    500     cout << *max_element(ans, ans + sumh + 1) << endl;
    501     return 0;
    502 }
    503 ```
    504 
    505 (by [KAN](/profile/KAN "Grandmaster KAN"))
    506 
    507 Tutorial is loading...
    508 
    509 **Model solution**
    510 
    511 ```
    512 #include <bits/stdc++.h>
    513 using namespace std;
    514 typedef long long LL;
    515 const int maxd = 10, maxl = 18, maxs = 81, BLEN = 5, BMSK = 31;
    516 struct States {
    517 	vector<LL> keys, vals[maxd + 1];
    518 	void insert(LL key) {
    519 		keys.push_back(key);
    520 	}
    521 	void initialize(LL val = 0) {
    522 		sort(keys.begin(), keys.end());
    523 		keys.erase(unique(keys.begin(), keys.end()), keys.end());
    524 		for(int i = 0; i < maxd; ++i)
    525 			vals[i].assign(keys.size(), val);
    526 	}
    527 	void summation() {
    528 		for(int i = 1; i < maxd; ++i)
    529 			for(vector<LL>::iterator it = vals[i - 1].begin(), jt = vals[i].begin(); jt != vals[i].end(); ++it, ++jt)
    530 				*jt += *it;
    531 	}
    532 	size_t size() const {
    533 		return keys.size();
    534 	}
    535 	void update(int upp, LL key, LL adt) {
    536 		vals[upp][lower_bound(keys.begin(), keys.end(), key) - keys.begin()] += adt;
    537 	}
    538 	LL find(int upp, LL key) {
    539 		vector<LL>::iterator it = lower_bound(keys.begin(), keys.end(), key);
    540 		if(it == keys.end() || *it != key)
    541 			return 0;
    542 		return vals[upp][it - keys.begin()];
    543 	}
    544 } f[maxd + 1][maxl + 1];
    545 LL c[2][maxl + 1], bit[maxd + 1];
    546 bitset<maxs + 1> vis[maxd + 1];
    547 void dfs(int dep, int cnt, int sum, LL msk) {
    548 	if(dep == maxd) {
    549 		for(int i = sum >> 1; i >= 0; --i)
    550 			if(vis[dep - 1].test(i)) {
    551 				int dif = sum - i - i;
    552 				if(dif > 1)
    553 					f[dif][0].insert(msk);
    554 				break;
    555 			}
    556 		return;
    557 	}
    558 	vis[dep] = vis[dep - 1];
    559 	dfs(dep + 1, cnt, sum, msk);
    560 	while(cnt < maxl) {
    561 		vis[dep] |= vis[dep] << dep;
    562 		dfs(dep + 1, ++cnt, sum += dep, msk += bit[dep]);
    563 	}
    564 }
    565 LL solve(int dif, LL lim) {
    566 	char dig[maxl + 3];
    567 	int len = sprintf(dig, "%lld", lim);
    568 	LL ret = 0, msk = 0;
    569 	States *F = f[dif];
    570 	for(int i = 0; i < len; ++i) {
    571 		dig[i] -= '0';
    572 		if(len - i > maxl) {
    573 			for(int j = 0; j < dig[i]; ++j)
    574 				ret += F[len - i - 1].find(maxd - 1, msk);
    575 		} else if(dig[i]) {
    576 			ret += F[len - i].find(dig[i] - 1, msk);
    577 			msk += bit[dig[i]];
    578 		}
    579 	}
    580 	return ret;
    581 }
    582 LL solve2(LL lim) {
    583 	char dig[maxl + 3];
    584 	int len = sprintf(dig, "%lld", lim), part = 0;
    585 	LL ret = 0;
    586 	for(int i = 0; i < len; ++i) {
    587 		dig[i] -= '0';
    588 		int odd = dig[i] >> 1, even = (dig[i] + 1) >> 1;
    589 		ret += c[part][len - 1 - i] * odd + c[part ^ 1][len - 1 - i] * even;
    590 		part ^= dig[i] & 1;
    591 	}
    592 	return ret;
    593 }
    594 int main() {
    595 	c[0][0] = 1;
    596 	for(int i = 0; i < maxl; ++i) {
    597 		int odd = maxd >> 1, even = (maxd + 1) >> 1;
    598 		c[0][i + 1] = c[0][i] * even + c[1][i] * odd;
    599 		c[1][i + 1] = c[0][i] * odd + c[1][i] * even;
    600 	}
    601 	bit[1] = 1;
    602 	for(int i = 2; i < maxd; ++i)
    603 		bit[i] = bit[i - 1] << BLEN;
    604 	vis[0].set(0);
    605 	dfs(1, 0, 0, 0);
    606 	for(int i = 2; i < maxd; ++i) {
    607 		f[i][0].initialize(1);
    608 		for(int j = 0; j < maxl; ++j) {
    609 			States &cur = f[i][j], &nxt = f[i][j + 1];
    610 			for(int idx = 0, sz = cur.size(); idx < sz; ++idx) {
    611 				int cnt = j;
    612 				LL msk = cur.keys[idx], tmp = msk;
    613 				for(int k = 1; k < maxd; ++k, tmp >>= BLEN) {
    614 					int rem = tmp & BMSK;
    615 					if(!rem)
    616 						continue;
    617 					cnt += rem;
    618 					nxt.insert(msk - bit[k]);
    619 				}
    620 				if(cnt < maxl)
    621 					nxt.insert(msk);
    622 			}
    623 			nxt.initialize(0);
    624 			for(int idx = 0, sz = cur.size(); idx < sz; ++idx) {
    625 				int cnt = j;
    626 				LL msk = cur.keys[idx], ways = cur.vals[maxd - 1][idx], tmp = msk;
    627 				for(int k = 1; k < maxd; ++k, tmp >>= BLEN) {
    628 					int rem = tmp & BMSK;
    629 					if(!rem)
    630 						continue;
    631 					cnt += rem;
    632 					nxt.update(k, msk - bit[k], ways);
    633 				}
    634 				if(cnt < maxl)
    635 					nxt.update(0, msk, ways); 
    636 			}
    637 			nxt.summation();
    638 		}
    639 	}
    640 	int t;
    641 	scanf("%d", &t);
    642 	for(int Case = 1; Case <= t; ++Case) {
    643 		LL L, R;
    644 		int k;
    645 		scanf("%lld%lld%d", &L, &R, &k);
    646 		LL ans = R + 1 - L;
    647 		if(!k) {
    648 			ans -= solve2(R + 1) - solve2(L);
    649 			for(int i = 2; i < maxd; i += 2)
    650 				ans -= solve(i, R + 1) - solve(i, L);
    651 		} else {
    652 			for(int i = k + 1; i < maxd; ++i)
    653 				ans -= solve(i, R + 1) - solve(i, L);
    654 		}
    655 		printf("%lld\n", ans);
    656 	}
    657 	return 0;
    658 }
    659 ```
    660 
    661 (by [Claris](/profile/Claris "International Master Claris") and [skywalkert](/profile/skywalkert "Master skywalkert"))
    662 
    663 ---
    664 
    665 My gratitude to the coordinators, problem authors, testers, and every participant. You made all this possible! Cheers \(^ ^)/