821.md (17944B)
1 Source: https://codeforces.com/blog/entry/52895 2 3 First, I really need to apologize for the round. There was a serious problem in D that was even covered in the sample test, that the main solution did not handle correctly. I should have been much more careful with this problem and looked for these kind of cases. Unfortunately, it was a big enough issue that caused the round to be unrated. I know this upset a lot of people, but it's tricky to find a solution to this kind of problem after the problem has happened. 4 5 I still hope the problems were good quality. If you learned something new from the round, or from this editorial, then the round was worth it. I would advise to solve the problems you couldn't solve during the contest, so you can take away something from the round. 6 7 **If you want any further clarification on a problem, please ask in comments!** 8 9 [821A — Okabe and Future Gadget Laboratory](//codeforces.com/problemset/problem/821/A) 10 11 We can simulate exactly what's described in the statement: loop over all cells not equal to 1 and check if it doesn't break the city property. To check if a cell breaks the property, just loop over an element in the same row, and an element in the same column, and see if they can add to give the cell's number. The complexity is O(*n*4). 12 13 Sidenote: The definition of lab here was actually inspired from a USAMTS problem in 2016. 14 15 **Code** 16 17 ``` 18 #include <queue> 19 #include <vector> 20 #include <list> 21 #include <map> 22 #include <set> 23 #include <deque> 24 #include <stack> 25 #include <bitset> 26 #include <algorithm> 27 #include <functional> 28 #include <numeric> 29 #include <utility> 30 #include <sstream> 31 #include <iostream> 32 #include <iomanip> 33 #include <cstdio> 34 #include <cmath> 35 #include <cstdlib> 36 #include <ctime> 37 #include <complex> 38 #include <fstream> 39 #include <cstring> 40 #include <string> 41 #include <climits> 42 using namespace std; 43 //macros 44 typedef long long ll; 45 typedef complex<double> point; 46 typedef pair<int,int> ii; 47 typedef vector<int> vi; 48 typedef vector< vector<int> > vvi; 49 50 #define FOR(k,a,b) for(int k=(a); k<=(b); ++k) 51 #define REP(k,a) for(int k=0; k<(a);++k) 52 #define SZ(a) int((a).size()) 53 #define ALL(c) (c).begin(),(c).end() 54 #define PB push_back 55 #define MP make_pair 56 #define INF 999999999 57 #define INFLONG 1000000000000000000LL 58 #define MOD 1000000007 59 #define MAX 100 60 #define ITERS 100 61 #define pi 3.1415926 62 #define MAXN 100000 63 #define _gcd __gcd 64 65 int main() 66 { 67 int n; 68 cin >> n; 69 int grid[50][50]; 70 REP(i,n){ 71 REP(j,n){ 72 cin >> grid[i][j]; 73 } 74 } 75 REP(i,n){ 76 REP(j,n){ 77 if(grid[i][j]==1) continue; 78 bool pass = false; 79 for(int r = 0;r<n;r++){ 80 if(r==i) continue; 81 for(int c = 0; c < n; c++){ 82 if(c==j) continue; 83 int sum = grid[r][j]+grid[i][c]; 84 if(sum==grid[i][j]){ 85 pass=true; 86 break; 87 } 88 } 89 if(pass)break; 90 } 91 if(!pass){ 92 cout << "No"<<endl; 93 return 0; 94 } 95 } 96 } 97 cout << "Yes"<<endl; 98 } 99 ``` 100 101 [821B — Okabe and Banana Trees](//codeforces.com/problemset/problem/821/B) 102 103 The critical observation to make is that the optimal rectangle should always have a lower-left vertex at the origin. This is due to the fact that the line has positive y-intercept and negative slope: any rectangle which doesn't have a vertex at the origin could easily be extended to have a vertex at the origin and even more bananas. 104 105 Then, we just need to try every x-coordinate for the upper-right corner of the box and pick the maximum y-coordinate without going over the line. We can compute the sum of any rectangle in *O*(1) using arithmetic series sums, so this becomes *O*(*bm*) because the x-intercept can be up to *bm*. You can make it faster by trying every y-coordinate; this makes the complexity *O*(*b*), but this was unnecessary to solve the problem. 106 107  Can you solve the problem with better complexity? 108 109 **O(b) Code** 110 111 ``` 112 #include <queue> 113 #include <vector> 114 #include <list> 115 #include <map> 116 #include <set> 117 #include <deque> 118 #include <stack> 119 #include <bitset> 120 #include <algorithm> 121 #include <functional> 122 #include <numeric> 123 #include <utility> 124 #include <sstream> 125 #include <iostream> 126 #include <iomanip> 127 #include <cstdio> 128 #include <cmath> 129 #include <cstdlib> 130 #include <ctime> 131 #include <complex> 132 #include <fstream> 133 #include <cstring> 134 #include <string> 135 #include <climits> 136 using namespace std; 137 138 //macros 139 typedef long long ll; 140 typedef complex<double> point; 141 typedef pair<int,int> ii; 142 typedef vector<int> vi; 143 typedef vector< vector<int> > vvi; 144 145 #define FOR(k,a,b) for(int k=(a); k<=(b); ++k) 146 #define REP(k,a) for(int k=0; k<(a);++k) 147 #define SZ(a) int((a).size()) 148 #define ALL(c) (c).begin(),(c).end() 149 #define PB push_back 150 #define MP make_pair 151 #define INF 999999999 152 #define INFLONG 1000000000000000000 153 #define MOD 1000000007 154 #define MAX 100 155 #define ITERS 100 156 #define MAXM 200000 157 #define MAXN 1000000 158 #define _gcd __gcd 159 #define eps 1e-9 160 ll series(ll x){ 161 return x*(x+1)/2; 162 } 163 int main() { 164 int m,b; 165 cin >> m >> b; 166 ll best = 0; 167 for(int y = b; y >=0; y--){ 168 //y = -x/m + b 169 ll x = m*(b-y); 170 ll t = 0; 171 t+=(x+1)*series(y)+(y+1)*series(x); 172 best = max(best,t); 173 } 174 cout << best << endl; 175 } 176 ``` 177 178 [821C — Okabe and Boxes](//codeforces.com/problemset/problem/821/C) 179 180 It looks like Daru should only reorder the boxes when he has to (i.e. he gets a remove operation on a number which isn't at the top of the stack). The proof is simple: reordering when Daru has more boxes is always not worse than reordering when he has less boxes, because Daru can sort more boxes into the optimal arrangement. Therefore, our greedy algorithm is as follows: simulate all the steps until we need to reorder, and then we resort the stack in ascending order from top to bottom. 181 182 This has complexity *O*(*n*2 *log* *n*). However, we can speed this up if we note that whenever we reorder boxes, any box currently on the stack can be put in an optimal position and we can pretty much forget about it. So whenever we reorder, we can just clear the stack as well and continue. This gives us *O*(*n*) complexity because every element is added and removed exactly once. 183 184 **Code** 185 186 ``` 187 #include <vector> 188 #include <utility> 189 #include <iostream> 190 #include <cassert> 191 #include <map> 192 #include <climits> 193 #include <deque> 194 #include <algorithm> 195 #include <set> 196 #include <stack> 197 using namespace std; 198 199 #define ll long long 200 #define REP(i,a) for(int i = 0; i < (a); i++) 201 #define PB push_back 202 #define SZ(a) (a).size() 203 #define MP make_pair 204 #define ALL(a) (a).begin(),(a).end() 205 #define fs first 206 typedef vector<int> vi; 207 typedef pair<int,int> pii; 208 209 int main() 210 { 211 int n; 212 cin >> n; 213 stack<int> st; 214 int curr=1; 215 int ans = 0; 216 REP(i,2*n){ 217 string str; 218 cin >> str; 219 assert(str[0]=='a' || str[0]=='r'); 220 if(str[0]=='a'){ 221 int x; 222 cin >> x; 223 st.push(x); 224 }else if(str[0]=='r'){ 225 if(!st.empty()){ 226 if(st.top()==curr){ //last thing added is what we need to remove 227 st.pop(); 228 }else{ //last thing we added is NOT what we need to remove 229 ans++; 230 while(!st.empty()) st.pop(); //clears the stack 231 } 232 } 233 curr++; 234 } 235 } 236 cout << ans << endl; 237 } 238 ``` 239 240 [821D — Okabe and City](//codeforces.com/problemset/problem/821/D) 241 242 First, let's make this problem into one on a graph. The important piece of information is the row and column we're on, so we'll create a node like this for every lit cell in the grid. Edges in the graph are 0 between 2 nodes if we can reach the other immediately, or 1 if we can light a row/column to get to it. Now it's a shortest path problem: we need to start from a given node, and with minimum distance, reach another node. 243 244 Only problem is, number of edges can be large, causing the algorithm to time out. There are a lot of options here to reduce number of transitions. The most elegant one I found is [Benq](/profile/Benq "Grandmaster Benq")'s solution, which I'll describe here. From a given cell, you can visit any adjacent lit cells. In addition, you can visit any lit cell with difference in rows at most 2, and any lit cell with difference in columns at most 2. So from the cell (r,c), you can just loop over all those cells. 245 246 The only tricky part is asking whether the current lit row/column should be a part of our BFS state. Since we fill the entire row/col and can then visit anything on that row/col, it doesn't matter where we came from. This means that you can temporarily light each row/column at most once during the entire BFS search. 247 248 So complexity is *O*(*n* + *m* + *k*), with a log factor somewhere for map or priority queue. Interestingly enough, you can remove the priority queue log factor because the BFS is with weights 0 and 1 only, but it performs slower in practice. 249 250 You can see the code implementing this approach below. 251 252 **Benq's code:** 253 254 ``` 255 /*#include <ext/pb_ds/assoc_container.hpp> 256 #include <ext/pb_ds/tree_policy.hpp>*/ 257 #include <bits/stdc++.h> 258 259 using namespace std; 260 //using namespace __gnu_pbds; 261 262 typedef long long ll; 263 typedef vector<int> vi; 264 typedef pair<int, int> pii; 265 //typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; 266 267 #define FOR(i, a, b) for (int i=a; i<b; i++) 268 #define F0R(i, a) for (int i=0; i<a; i++) 269 #define FORd(i,a,b) for (int i = (b)-1; i >= a; i--) 270 #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--) 271 272 #define mp make_pair 273 #define pb push_back 274 #define f first 275 #define s second 276 #define lb lower_bound 277 #define ub upper_bound 278 279 const int MOD = 1000000007; 280 double PI = 4*atan(1); 281 282 int dr[10001], dc[10001]; 283 vi row[10001], col[10001]; 284 priority_queue<pii> todo; 285 vector<pii> lights; 286 int dist[10001]; 287 map<pii,int> label; 288 int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; 289 int n,m,k; 290 291 void filrow(int i, int val){ 292 if (i >= 1 && i <= n && dr[i] == 0) { 293 dr[i] = 1; 294 for (int x: row[i]) if (val < dist[x]) { 295 dist[x] = val; 296 todo.push({-dist[x],x}); 297 } 298 } 299 } 300 301 void filcol(int i, int val) { 302 if (i >= 1 && i <= m && dc[i] == 0) { 303 dc[i] = 1; 304 for (int x: col[i]) if (val < dist[x]) { 305 dist[x] = val; 306 todo.push({-dist[x],x}); 307 } 308 } 309 } 310 311 void ad(int x, int y, int val) { 312 if (label.find({x,y}) != label.end()) 313 if (dist[label[{x,y}]] > val) { 314 dist[label[{x,y}]] = val; 315 todo.push({-val,label[{x,y}]}); 316 } 317 } 318 319 int main() { 320 cin >> n >> m >> k; 321 322 F0R(i,k) { 323 int r,c; cin >> r >> c; 324 lights.pb({r,c}); 325 row[r].pb(i); 326 col[c].pb(i); 327 label[{r,c}] = i; 328 } 329 330 F0R(i,10001) dist[i] = MOD; 331 332 if (label.find({n,m}) == label.end()) { 333 filrow(n-1,1); 334 filrow(n,1); 335 filcol(m-1,1); 336 filcol(m,1); 337 } else todo.push({0,label[{n,m}]}); 338 339 340 while (todo.size()) { 341 auto a = todo.top(); todo.pop(); 342 a.f = -a.f; 343 if (a.f > dist[a.s]) continue; 344 345 F0R(i,4) ad(lights[a.s].f+xdir[i],lights[a.s].s+ydir[i],a.f); 346 FOR(i,lights[a.s].f-2,lights[a.s].f+3) filrow(i,a.f+1); 347 FOR(i,lights[a.s].s-2,lights[a.s].s+3) filcol(i,a.f+1); 348 } 349 350 if (dist[0] != MOD) cout << dist[0]; 351 else cout << -1; 352 } 353 ``` 354 355 Another approach to this problem was using "virtual nodes". Virtual nodes are an easy way to put transitions between related states while keeping number of edges low. In this problem, we can travel to any lit cell if its row differs by <=2, or its column differs by at most 2, but naively adding edges would cause O(k^2) edges. 356 357 Instead, for every row, lets make a virtual node. For every lit cell in this row, put an edge between the lit cell and this virtual node with cost 1. We can do something similar for every column. 358 359 Now, it's easy to see that the shortest path in this graph suffices. A minor detail is that we should divide the answer by 2 since every skipping of a row or column ends up costing 2 units of cost. 360 361 [821E — Okabe and El Psy Kongroo](//codeforces.com/problemset/problem/821/E) 362 363 You can get a naive DP solution by computing *f*(*x*, *y*), the number of ways to reach the point (*x*, *y*). It's just *f*(*x* - 1, *y* + 1) + *f*(*x* - 1, *y*) + *f*(*x* - 1, *y* - 1), being careful about staying above x axis and under or on any segments. 364 365 To speed it up, note that the transitions are independent of x. This is screaming matrix multiplication! First, if you don't know the matrix exponentiation technique for speeding up DP, you should learn it from [here](https://www.hackerrank.com/topics/matrix-exponentiation). 366 367 Now, let's think of the matrix representation. Since the x dimension is the long one and the y dimension is small, lets store a vector of values *dp* where *dp**i* is the number of ways to get to a y value of i at the current x value. This will be the initial vector for matrix multiplication. 368 369 Now, what about the transition matrix? Since our initial vector has length y and we need a matrix to multiply it with to map it to another vector with length y, we need a y by y matrix. Now, if you think about how matrix multiplication works, you come up with an idea like this: put a 1 in the entry (i,j) if from a y value of i we can reach a y value of j (i.e. |*i* - *j*| ≤ 1). Don't believe me, multiply some vector times a matrix of this form to see how and why the transition works. 370 371 You can then build this matrix quickly and then matrix exponentiate for under every segment and multiply by the initial vector, then make the result as the new initial vector for the next segment. You should make sure to remove values from the vector if the next segment is lower, or add values to the vector if the next segment is higher. This gives complexity *O*(*nh*3 log *w*) where *h* = 16 and *w* = *k*. 372 373 **Code** 374 375 ``` 376 #include <queue> 377 #include <vector> 378 #include <list> 379 #include <map> 380 #include <set> 381 #include <deque> 382 #include <stack> 383 #include <bitset> 384 #include <algorithm> 385 #include <functional> 386 #include <numeric> 387 #include <utility> 388 #include <sstream> 389 #include <iostream> 390 #include <iomanip> 391 #include <cstdio> 392 #include <cmath> 393 #include <cstdlib> 394 #include <ctime> 395 #include <complex> 396 #include <fstream> 397 #include <cstring> 398 #include <string> 399 #include <climits> 400 #include <chrono> 401 #include <ext/pb_ds/assoc_container.hpp> 402 #include <ext/pb_ds/tree_policy.hpp> 403 #include <assert.h> 404 using namespace std; 405 406 //macros 407 typedef long long ll; 408 typedef complex<double> point; 409 typedef pair<int,int> ii; 410 typedef vector<int> vi; 411 typedef vector< vector<int> > vvi; 412 413 #define FOR(k,a,b) for(int k=(a); k<=(b); ++k) 414 #define REP(k,a) for(int k=0; k<(a);++k) 415 #define SZ(a) int((a).size()) 416 #define ALL(c) (c).begin(),(c).end() 417 #define PB push_back 418 #define MP make_pair 419 #define INF 1000000001 420 #define INFLONG 1000000000000000000 421 #define MOD 1000000007 422 #define MAX 100 423 #define ITERS 100 424 #define MAXM 200000 425 #define MAXN 1000000 426 #define _gcd __gcd 427 #define EPS 1e-7 428 #define PI 3.1415926535897932384626 429 #define ERR -987654321 430 431 //multiplies m1 and m2 and stores in m3 432 vector<vector<long long> > matmul(vector<vector<long long> > m1, vector<vector<long long> > m2, vector<vector<long long> > &m3){ 433 m3.clear(); 434 vector<vector<long long> > ans; 435 REP(i,SZ(m1)){ 436 vector<long long> v; 437 438 REP(j,SZ(m2[0])){ 439 v.PB(0); 440 } 441 ans.PB(v); 442 } 443 444 REP(r,SZ(m1)){ 445 REP(c,SZ(m2[0])){ 446 REP(k, SZ(m2)){ 447 ans[r][c] += m1[r][k]*m2[k][c]; 448 ans[r][c]%=MOD; 449 } 450 } 451 } 452 453 REP(i,SZ(m1)){ 454 vector<long long> cur; 455 REP(j,SZ(m2[0])){ 456 cur.PB(ans[i][j]); 457 } 458 m3.PB(cur); 459 } 460 return m3; 461 462 } 463 vector<ll> mymul(vector<ll> vec, vector<vector<ll> > mat, vector<ll> &ret){ 464 vector<ll> res; 465 REP(i,SZ(vec)){ 466 ll sum = 0; 467 for(int co = 0; co < SZ(mat); co++){ 468 sum += vec[co]*mat[co][i]; 469 sum%=MOD; 470 } 471 res.PB(sum); 472 } 473 ret.clear(); 474 REP(i,SZ(res)) ret.PB(res[i]); 475 return ret; 476 } 477 void printmat(vector<vector<long long> > matr){ 478 REP(i,SZ(matr)){ 479 REP(j,SZ(matr[i])){ 480 cout << matr[i][j] << " " ; 481 } 482 cout << endl; 483 } 484 } 485 vector<vector<long long> > matexp(vector<vector<long long> > matr, long long n){ 486 vector<vector<long long> > ans; 487 REP(i,SZ(matr)){ 488 vector<long long> v; 489 REP(j,SZ(matr[0])){ 490 v.PB((i==j)); 491 } 492 ans.PB(v); 493 } 494 long long t = n; 495 496 while(t>0){ 497 498 if(t%2==0){ 499 matmul(matr,matr,matr); 500 t/=2; 501 } 502 else{ 503 matmul(ans,matr,ans); 504 t--; 505 } 506 } 507 508 return ans; 509 } 510 511 int main() 512 { 513 int n; 514 ll k; 515 cin >> n >> k; 516 vector<ll> a1,a2,b; 517 REP(i,n){ 518 ll a1r, a2r, br; 519 cin >> a1r >> a2r >> br; 520 a1.PB(a1r); 521 a2.PB(a2r); 522 b.PB(br); 523 } 524 vector<ll> ans; 525 ans.PB(1); 526 a2[SZ(a2)-1] = k; 527 REP(i,n){ 528 //update ans size 529 while(SZ(ans) < b[i]+1) ans.PB(0); 530 while(SZ(ans) > b[i]+1) ans.erase(prev(ans.end())); 531 vector<vector<ll> > trans; 532 int len = b[i]+1; 533 REP(pr,len){ 534 vector<ll> lol; 535 REP(pro,len){ 536 lol.PB(0); 537 } 538 trans.PB(lol); 539 } 540 REP(co,len){ 541 if(co>0) trans[co-1][co] = 1; 542 trans[co][co] = 1; 543 if(co+1<len) trans[co+1][co] = 1; 544 } 545 mymul(ans,matexp(trans,a2[i]-a1[i]),ans); 546 } 547 cout << ans[0] << endl; 548 } 549 ```