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!**