codeforces-scrape

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

869.md (11290B)


      1 Source: https://codeforces.com/blog/entry/55009
      2 
      3 Hi, all!
      4 
      5 This is not [Tommyr7](/profile/Tommyr7 "Master Tommyr7"), but the **impostor** behind the round (guess who I am? :P). The statements are written by me. The characters in the round feature, again, the *Monogatari* anime series, and to be more specific, *Nisemonogatari: Fake Tale*. The statements involve stories with fake things and oddities, but as per tradition, contain no spoilers. Thank you, everyone, and hope you've all enjoyed the round!
      6 
      7 On a side note, special kudos to [the best impostors of the round](//codeforces.com/blog/entry/54971?#comment-389321) (except me, lol)!
      8 
      9 Any feedback on problems and tutorials are welcome -- we look forward to doing even better in the future!
     10 
     11 Here are hints for all problems and detailed tutorials!
     12 
     13 ---
     14 
     15 ### Hints
     16 
     17 **Problem A**
     18 
     19 First approach: Optimize the straightforward solution.
     20 
     21 **... or even...**
     22 
     23 Second approach: Believe in magic.
     24 
     25 **Problem B**
     26 
     27 Multiply instead of divide. What happens to the last digit when multiplying?
     28 
     29 **Problem C**
     30 
     31 Consider islands of **two** colours and the bridges between them.
     32 
     33 **Problem D**
     34 
     35 Iterate over all possible combination, order and direction of extra edges.
     36 
     37 **Problem E**
     38 
     39 First approach: 2D segment tree (or quadtree) with a `set` or `vector` on each node, representing the set of barriers that cover this node.
     40 
     41 **... or may as well...**
     42 
     43 Second approach: Assign a random value to each barrier. Then utilise 2D Fenwick trees.
     44 
     45 ---
     46 
     47 ### Tutorials
     48 
     49 ### [869A - The Artful Expedient](/contest/869/problem/A "Codeforces Round 439 (Div. 2)")
     50 
     51 **Author** [Tommyr7](/profile/Tommyr7 "Master Tommyr7"), [cyand1317](/profile/cyand1317 "Grandmaster cyand1317") / **Preparation** [Tommyr7](/profile/Tommyr7 "Master Tommyr7"), [cyand1317](/profile/cyand1317 "Grandmaster cyand1317") / **Tutorial** [cyand1317](/profile/cyand1317 "Grandmaster cyand1317")
     52 
     53 **Tutorial**
     54 
     55 Tutorial is loading...
     56 
     57 **Solution 1 (Tommyr7)**
     58 
     59 ```
     60 #include <bits/stdc++.h>
     61 using namespace std;
     62 #define Maxn 4000007
     63 bool vis[Maxn];
     64 int a[4007],b[4007],n;
     65 int main()
     66 {
     67 	scanf("%d",&n);
     68 	memset(vis,false,sizeof(vis));
     69 	for (int i=1;i<=n;i++)
     70 	{
     71 		scanf("%d",&a[i]);
     72 		vis[a[i]]=true;
     73 	}
     74 	for (int i=1;i<=n;i++)
     75 	{
     76 		scanf("%d",&b[i]);
     77 		vis[b[i]]=true;
     78 	}
     79 	int ans=0;
     80 	for (int i=1;i<=n;i++)
     81 		for (int j=1;j<=n;j++)
     82 			if (vis[a[i]^b[j]]) ++ans;
     83 	if (ans%2==0) printf("Karen\n"); else printf("Koyomi\n");
     84 	return 0;
     85 }
     86 ```
     87 
     88 **Solution 2 (cyand1317)**
     89 
     90 ```
     91 #include <stdio.h>
     92 
     93 int main()
     94 {
     95     puts("Karen");
     96     return 0;
     97 }
     98 ```
     99 
    100 ### [869B - The Eternal Immortality](/contest/869/problem/B "Codeforces Round 439 (Div. 2)")
    101 
    102 **Author** [Tommyr7](/profile/Tommyr7 "Master Tommyr7") / **Preparation** [Tommyr7](/profile/Tommyr7 "Master Tommyr7") / **Tutorial** [cyand1317](/profile/cyand1317 "Grandmaster cyand1317")
    103 
    104 **Tutorial**
    105 
    106 Tutorial is loading...
    107 
    108 **Model solution (Tommyr7)**
    109 
    110 ```
    111 #include <bits/stdc++.h>
    112 using namespace std;
    113 long long L,R;
    114 int ans;
    115 int main()
    116 {
    117 	scanf("%lld%lld",&L,&R);
    118 	if (R-L>=10) printf("%d\n",0);
    119 	else
    120 	{
    121 		ans=1;
    122 		for (long long i=L+1;i<=R;i++)
    123 			ans=(1LL*ans*(i%10))%10;
    124 		printf("%d\n",ans);
    125 	}
    126 	return 0;
    127 }
    128 ```
    129 
    130 ### [869C - The Intriguing Obsession](/contest/869/problem/C "Codeforces Round 439 (Div. 2)")
    131 
    132 **Author** [Tommyr7](/profile/Tommyr7 "Master Tommyr7") / **Preparation** [Tommyr7](/profile/Tommyr7 "Master Tommyr7") / **Tutorial** [Tommyr7](/profile/Tommyr7 "Master Tommyr7")
    133 
    134 **Tutorial**
    135 
    136 Tutorial is loading...
    137 
    138 **Model solution (Tommyr7)**
    139 
    140 ```
    141 #include <bits/stdc++.h>
    142 #define Maxn 5007
    143 #define modp 998244353
    144 int p[Maxn][Maxn];
    145 int pre[Maxn];
    146 int a,b,c;
    147 int solve(int x,int y)
    148 {
    149 	int res=0;
    150 	for (int k=0;k<=x&&k<=y;k++)
    151 	{
    152 		int del=pre[k];
    153 		del=(1LL*del*p[x][k])%modp;
    154 		del=(1LL*del*p[y][k])%modp;
    155 		res=(res+del)%modp;
    156 	}
    157 	return res;
    158 }
    159 int main()
    160 {
    161 	scanf("%d%d%d",&a,&b,&c);
    162 	memset(p,0,sizeof(p));
    163 	p[0][0]=1;
    164 	for (int i=1;i<=5000;i++)
    165 	{
    166 		p[i][0]=1;
    167 		for (int j=1;j<=i;j++)
    168 			p[i][j]=(p[i-1][j-1]+p[i-1][j])%modp;
    169 	}
    170 	memset(pre,0,sizeof(pre));
    171 	pre[0]=1;
    172 	for (int i=1;i<=5000;i++)
    173 		pre[i]=(1LL*pre[i-1]*i)%modp;
    174 	int ans=1;
    175 	ans=(1LL*ans*solve(a,b))%modp;
    176 	ans=(1LL*ans*solve(b,c))%modp;
    177 	ans=(1LL*ans*solve(a,c))%modp;
    178 	printf("%d\n",ans);
    179 	return 0;
    180 }
    181 ```
    182 
    183 ### [869D - The Overdosing Ubiquity](/contest/869/problem/D "Codeforces Round 439 (Div. 2)")
    184 
    185 **Author** [quailty](/profile/quailty "Grandmaster quailty") / **Preparation** [quailty](/profile/quailty "Grandmaster quailty") / **Tutorial** [quailty](/profile/quailty "Grandmaster quailty")
    186 
    187 **Tutorial**
    188 
    189 Tutorial is loading...
    190 
    191 **Model solution (quailty)**
    192 
    193 ```
    194 #include<cstdio>
    195 #include<cstdlib>
    196 #include<cstring>
    197 #include<cmath>
    198 #include<iostream>
    199 #include<algorithm>
    200 #include<map>
    201 
    202 using namespace std;
    203 
    204 const int MAXN=255;
    205 
    206 const int Mod=1000000007;
    207 inline void add_mod(int &x,int y)
    208 {
    209     x=(x+y<Mod ? x+y : x+y-Mod);
    210 }
    211 
    212 int u[MAXN],v[MAXN];
    213 
    214 map<int,int> mp;
    215 inline int get_id(int x)
    216 {
    217     if(!mp[x])mp[x]=(int)mp.size();
    218     return mp[x];
    219 }
    220 
    221 vector<int> e[MAXN];
    222 void add_edge(int u,int v)
    223 {
    224     e[u].push_back(v);
    225     e[v].push_back(u);
    226 }
    227 
    228 inline int cal_size(int u,int n,int d)
    229 {
    230     int t=u,c=0,res;
    231     while(t)c++,t>>=1;
    232     res=(1<<(d-c+1))-1,t=c;
    233     while(t<d)t++,u=u<<1|1;
    234     return res-max(min(u-n,1<<(d-c)),0);
    235 }
    236 
    237 int num[MAXN];
    238 void pre_dp(int u,int f)
    239 {
    240     for(auto &v:e[u])
    241     {
    242         if(v==f)continue;
    243         num[u]-=num[v];
    244         pre_dp(v,u);
    245     }
    246 }
    247 
    248 int vis[MAXN];
    249 void dfs(int u,int &tot)
    250 {
    251     add_mod(tot,num[u]);
    252     vis[u]=1;
    253     for(auto &v:e[u])
    254         if(!vis[v])dfs(v,tot);
    255     vis[u]=0;
    256 }
    257 
    258 int main()
    259 {
    260     int n,m,d=0;
    261     scanf("%d%d",&n,&m);
    262     while((1<<d)<=n)d++;
    263     get_id(1);
    264     for(int i=0;i<m;i++)
    265     {
    266         scanf("%d%d",&u[i],&v[i]);
    267         int t=u[i];
    268         while(t)get_id(t),t>>=1;
    269         t=v[i];
    270         while(t)get_id(t),t>>=1;
    271     }
    272     for(auto &t:mp)
    273     {
    274         int u=t.first,id=t.second;
    275         if(u>1)add_edge(get_id(u),get_id(u>>1));
    276         num[id]=cal_size(u,n,d);
    277     }
    278     pre_dp(1,0);
    279     for(int i=0;i<m;i++)
    280         add_edge(get_id(u[i]),get_id(v[i]));
    281     int res=0;
    282     for(int i=1;i<=(int)mp.size();i++)
    283     {
    284         int tot=0;
    285         dfs(i,tot);
    286         add_mod(res,1LL*tot*num[i]%Mod);
    287     }
    288     printf("%d\n",res);
    289     return 0;
    290 }
    291 ```
    292 
    293 ### [869E - The Untended Antiquity](/contest/869/problem/E "Codeforces Round 439 (Div. 2)")
    294 
    295 **Author** [Tommyr7](/profile/Tommyr7 "Master Tommyr7") / **Preparation** [Tommyr7](/profile/Tommyr7 "Master Tommyr7"), [cyand1317](/profile/cyand1317 "Grandmaster cyand1317"), [visitWorld](/profile/visitWorld "Expert visitWorld") / **Tutorial** [cyand1317](/profile/cyand1317 "Grandmaster cyand1317")
    296 
    297 **Tutorial**
    298 
    299 Tutorial is loading...
    300 
    301 **Solution 1 (visitWorld)**
    302 
    303 ```
    304 #include <bits/stdc++.h>
    305 
    306 #define rep(i, x, y) for (int i = (x), _ = (y); i <= _; ++i)
    307 #define down(i, x, y) for (int i = (x) - 1, _ = (y); i >= _; --i)
    308 #define x first
    309 #define y second
    310 #define mp make_pair
    311 #define pb push_back
    312 #define bin(x) (1<<(x))
    313 //#define LX_JUDGE
    314 
    315 using namespace std;
    316 typedef long long ll;
    317 typedef pair<int, int> pii;
    318 
    319 template<typename T> inline void upmax(T &x, T y) { x < y ? x = y : 0; }
    320 template<typename T> inline void upmin(T &x, T y) { x > y ? x = y : 0; }
    321 
    322 template<typename T> inline void read(T &x) {
    323 	char c;
    324 	while ((c = getchar()) < '0' or c > '9');
    325 	for (x = c - '0'; (c = getchar()) >= '0' and c <= '9'; x = x * 10 + c - '0');
    326 }
    327 
    328 const int inf = 0x3f3f3f3f;
    329 const int MAX_N = 2500;
    330 
    331 struct Data {
    332 	int u, d, id;
    333 	Data() {}
    334 	Data(int u, int d, int id) : u(u), d(d), id(id) {}
    335 };
    336 
    337 class SegmentTree {
    338 	map<pii, int> G;
    339 	int n, pcnt;
    340 	vector<Data> H[MAX_N * 4 + 255];
    341 #define ls (o << 1)
    342 #define rs (o << 1 | 1)
    343 
    344 	int _l, _r, _u, _d, _id;
    345 
    346 	void ins(int o, int l, int r) {
    347 		if (_l <= l and r <= _r) {
    348 			//printf("%d %d %d %d\n", l, r, _u, _d);
    349 			H[o].pb(Data(_u, _d, _id));
    350 			return ;
    351 		}
    352 		int m = (l + r) / 2;
    353 		if (_l <= m) ins(ls, l, m);
    354 		if (m < _r) ins(rs, m + 1, r);
    355 	}
    356 	void del(int o, int l, int r) {
    357 		if (_l <= l and r <= _r) {
    358 			for (vector<Data>::iterator it = H[o].begin(); it != H[o].end(); it++) {
    359 				if (it->id == _id) {
    360 					H[o].erase(it);
    361 					break ;
    362 				}
    363 			}
    364 			return ;
    365 		}
    366 		int m = (l + r) / 2;
    367 		if (_l <= m) del(ls, l, m);
    368 		if (m < _r) del(rs, m + 1, r);
    369 	}
    370 	inline int _ask(const vector<Data> &q, int h) {
    371 		int best = inf, ans = -1;
    372 		for (auto to : q) {
    373 			if (to.u <= h and h <= to.d and to.d - to.u < best) {
    374 				best = to.d - to.u;
    375 				ans = to.id;
    376 			}
    377 		}
    378 		return ans;
    379 	}
    380 	int ask(int o, int l, int r) {
    381 		if (l == r) return _ask(H[o], _u);
    382 		int m = (l + r) / 2;
    383 		int ans = m >= _l ? ask(ls, l, m) : ask(rs, m + 1, r);
    384 		return ans < 0 ? _ask(H[o], _u) : ans;
    385 	}
    386 #undef ls
    387 #undef rs
    388 public :
    389 	void init(int n) {
    390 		this->n = n;
    391 		pcnt = 1;
    392 	}
    393 	void ins(int l, int u, int r, int d) {
    394 		G[mp(l, u)] = _id = pcnt++;
    395 		_l = l, _r = r, _u = u, _d = d;
    396 		ins(1, 1, n);
    397 	}
    398 	void del(int l, int u, int r, int d) {
    399 		_id = G[mp(l, u)];
    400 		G.erase(mp(l, u));
    401 		_l = l, _r = r;
    402 		del(1, 1, n);
    403 	}
    404 	int ask(int x, int y) {
    405 		_l = x, _u = y;
    406 		return ask(1, 1, n);
    407 	}
    408 } my;
    409 
    410 int main() {
    411 	int n, m, Q;
    412 	read(n), read(m), read(Q);
    413 	my.init(2500); // FIX ME
    414 	int opt, r1, c1, r2, c2;
    415 	while (Q--) {
    416 		read(opt), read(r1), read(c1), read(r2), read(c2);
    417 		if (opt == 3) {
    418 			//int a = my.ask(r1, c1), b = my.ask(r2, c2);
    419 			//printf("%d %d\n", a, b);
    420 			puts(my.ask(r1, c1) == my.ask(r2, c2) ? "Yes" : "No");
    421 		} else if (opt == 1) {
    422 			my.ins(r1, c1, r2, c2);
    423 		} else {
    424 			my.del(r1, c1, r2, c2);
    425 		}
    426 	}
    427 	return 0;
    428 }
    429 ```
    430 
    431 **Solution 2 (Tommyr7)**
    432 
    433 ```
    434 #include <bits/stdc++.h>
    435 #define Maxn 2507
    436 using namespace std;
    437 int n,m,q;
    438 map<pair<pair<int,int>,pair<int,int> >,pair<unsigned long long,unsigned long long> > mp;
    439 pair<unsigned long long,unsigned long long> s[Maxn][Maxn];
    440 void add(int x,int y,pair<unsigned long long,unsigned long long> del)
    441 {
    442 	for (int kx=x;kx<=2503;kx+=kx&(-kx))
    443 		for (int ky=y;ky<=2503;ky+=ky&(-ky))
    444 		{
    445 			s[kx][ky].first+=del.first;
    446 			s[kx][ky].second+=del.second;
    447 		}
    448 }
    449 pair<unsigned long long,unsigned long long> query(int x,int y)
    450 {
    451 	pair<unsigned long long,unsigned long long> res=make_pair(0,0);
    452 	for (int kx=x;kx;kx-=kx&(-kx))
    453 		for (int ky=y;ky;ky-=ky&(-ky))
    454 		{
    455 			res.first+=s[kx][ky].first;
    456 			res.second+=s[kx][ky].second;
    457 		}
    458 	return res;
    459 }
    460 int main()
    461 {
    462 	scanf("%d%d%d",&n,&m,&q);
    463 	memset(s,0,sizeof(s));
    464 	srand(20001206);
    465 	mp.clear();
    466 	for (int i=1;i<=q;i++)
    467 	{
    468 		int t,r1,c1,r2,c2;
    469 		scanf("%d%d%d%d%d",&t,&r1,&c1,&r2,&c2);
    470 		pair<unsigned long long,unsigned long long> del,udel;
    471 		if (t==1)
    472 		{
    473 			del.first=rand();
    474 			del.second=rand();
    475 			udel=make_pair(-del.first,-del.second);
    476 			mp[make_pair(make_pair(r1,c1),make_pair(r2,c2))]=del;
    477 			add(r1,c1,del);
    478 			add(r1,c2+1,udel);
    479 			add(r2+1,c1,udel);
    480 			add(r2+1,c2+1,del);
    481 		} else if (t==2)
    482 		{
    483 			del=mp[make_pair(make_pair(r1,c1),make_pair(r2,c2))];
    484 			mp[make_pair(make_pair(r1,c1),make_pair(r2,c2))]=make_pair(0,0);
    485 			udel=make_pair(-del.first,-del.second);
    486 			add(r1,c1,udel);
    487 			add(r1,c2+1,del);
    488 			add(r2+1,c1,del);
    489 			add(r2+1,c2+1,udel);
    490 		}
    491 		else
    492 		{
    493 			del=query(r1,c1);
    494 			udel=query(r2,c2);
    495 			if (del==udel) printf("Yes\n"); else printf("No\n");
    496 		}
    497 	}
    498 	return 0;
    499 }
    500 ```
    501 
    502 ---
    503 
    504 **Tommyr7: I do hope you all enjoyed yourselves during the contest. See you next time!**