codeforces-scrape

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

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 ![](https://espresso.codeforces.com/f7300d739da3a486f0ee285092bc4ba7f85e27d4.png) 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 ```