codeforces-scrape

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

1901.md (7254B)


      1 Source: https://codeforces.com/blog/entry/122645
      2 
      3 [1901A - Line Trip](/contest/1901/problem/A "Educational Codeforces Round 158 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Neon)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15  
     16 using namespace std;
     17  
     18 int main() {
     19   ios::sync_with_stdio(false); cin.tie(0);
     20   int t;
     21   cin >> t;
     22   while (t--) {
     23     int n, x;
     24     cin >> n >> x;
     25     int prev = 0, ans = 0;
     26     for (int i = 0; i < n; ++i) {
     27       int a; cin >> a;
     28       ans = max(ans, a - prev);
     29       prev = a;
     30     }
     31     ans = max(ans, 2 * (x - prev));
     32     cout << ans << '\n';
     33   }
     34 }
     35 ```
     36 
     37 [1901B - Chip and Ribbon](/contest/1901/problem/B "Educational Codeforces Round 158 (Rated for Div. 2)")
     38 
     39 Idea: [Roms](/profile/Roms "Master Roms")
     40 
     41 **Tutorial**
     42 
     43 Tutorial is loading...
     44 
     45 **Solution (Roms)**
     46 
     47 ```
     48 #include <bits/stdc++.h>
     49  
     50 using namespace std;
     51  
     52 const int N = 200'000;
     53  
     54 int t;
     55  
     56 int main() {
     57     cin >> t;
     58     for (int tc = 0; tc < t; ++tc) {
     59         int n;
     60         cin >> n;
     61         vector <int> cnt(n);
     62         long long res = 0;
     63         int cur = 0;
     64         for (int i = 0; i < n; ++i) {
     65             cin >> cnt[i];
     66             if (cnt[i] > cur) 
     67                 res += cnt[i] - cur;
     68             cur = cnt[i];
     69         }
     70         
     71         cout << res - 1 << endl;
     72     }
     73     return 0;
     74 }
     75 ```
     76 
     77 [1901C - Add, Divide and Floor](/contest/1901/problem/C "Educational Codeforces Round 158 (Rated for Div. 2)")
     78 
     79 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     80 
     81 **Tutorial**
     82 
     83 Tutorial is loading...
     84 
     85 **Solution (awoo)**
     86 
     87 ```
     88 for _ in range(int(input())):
     89 	n = int(input())
     90 	a = list(map(int, input().split()))
     91 	x, y = min(a), max(a)
     92 	res = []
     93 	while x != y:
     94 		res.append(x % 2)
     95 		x = (x + res[-1]) // 2
     96 		y = (y + res[-1]) // 2
     97 	print(len(res))
     98 	if len(res) <= n:
     99 		print(*res)
    100 ```
    101 
    102 [1901D - Yet Another Monster Fight](/contest/1901/problem/D "Educational Codeforces Round 158 (Rated for Div. 2)")
    103 
    104 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    105 
    106 **Tutorial**
    107 
    108 Tutorial is loading...
    109 
    110 **Solution (vovuh)**
    111 
    112 ```
    113 #include <bits/stdc++.h>
    114  
    115 using namespace std;
    116  
    117 int main() {
    118 #ifdef _DEBUG
    119     freopen("input.txt", "r", stdin);
    120 //  freopen("output.txt", "w", stdout);
    121 #endif
    122     
    123     int n;
    124     cin >> n;
    125     vector<int> a(n);
    126     for (auto &it : a) cin >> it;
    127     
    128     vector<int> pref(n), suf(n);
    129     for (int i = 0; i < n; ++i) {
    130         pref[i] = a[i] + (n - i - 1);
    131         suf[i] = a[i] + i;
    132     }
    133     for (int i = 1; i < n; ++i) {
    134         pref[i] = max(pref[i], pref[i - 1]);
    135     }
    136     for (int i = n - 2; i >= 0; --i) {
    137         suf[i] = max(suf[i], suf[i + 1]);
    138     }
    139     
    140     int ans = 2e9;
    141     for (int i = 0; i < n; ++i) {
    142         int cur = a[i];
    143         if (i > 0) cur = max(cur, pref[i - 1]);
    144         if (i + 1 < n) cur = max(cur, suf[i + 1]);
    145         ans = min(ans, cur);
    146     }
    147     
    148     cout << ans << endl;
    149     
    150     return 0;
    151 }
    152 ```
    153 
    154 [1901E - Compressed Tree](/contest/1901/problem/E "Educational Codeforces Round 158 (Rated for Div. 2)")
    155 
    156 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    157 
    158 **Tutorial**
    159 
    160 Tutorial is loading...
    161 
    162 **Solution (Neon)**
    163 
    164 ```
    165 #include <bits/stdc++.h>
    166  
    167 using namespace std;
    168  
    169 using li = long long;
    170  
    171 const li INF = 1e18;
    172 const int N = 555555;
    173  
    174 int n;
    175 int a[N];
    176 vector<int> g[N];
    177 li dp[N];
    178 li ans;
    179  
    180 void calc(int v, int p) {
    181   vector<li> sum(4, -INF);
    182   sum[0] = 0;
    183   for (int u : g[v]) if (u != p) {
    184     calc(u, v);
    185     for (int i = 3; i >= 0; --i) {
    186       sum[min(i + 1, 3)] = max(sum[min(i + 1, 3)], sum[i] + dp[u]);
    187     }
    188   }
    189   dp[v] = -INF;
    190   for (int j = 0; j < 4; ++j) {
    191     dp[v] = max(dp[v], sum[j] + (j == 1 ? 0 : a[v]));
    192     ans = max(ans, sum[j] + (j == 2 ? 0 : a[v]));
    193   }
    194 }
    195  
    196 int main() {
    197   ios::sync_with_stdio(false); cin.tie(0);
    198   int t;
    199   cin >> t;
    200   while (t--) {
    201     cin >> n;
    202     for (int i = 0; i < n; ++i) cin >> a[i];
    203     for (int i = 0; i < n; ++i) g[i].clear();
    204     for (int i = 0; i < n - 1; ++i) {
    205       int x, y;
    206       cin >> x >> y;
    207       --x; --y;
    208       g[x].push_back(y);
    209       g[y].push_back(x);
    210     }
    211     ans = 0;
    212     calc(0, -1);
    213     cout << ans << '\n';
    214   }
    215 }
    216 ```
    217 
    218 [1901F - Landscaping](/contest/1901/problem/F "Educational Codeforces Round 158 (Rated for Div. 2)")
    219 
    220 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    221 
    222 **Tutorial**
    223 
    224 Tutorial is loading...
    225 
    226 **Solution (adedalic)**
    227 
    228 ```
    229 #include<bits/stdc++.h>
    230  
    231 using namespace std;
    232  
    233 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    234 #define sz(a) int((a).size())
    235 #define all(a) (a).begin(), (a).end()
    236  
    237 #define x first
    238 #define y second
    239  
    240 typedef long long li;
    241 typedef long double ld;
    242 typedef pair<int, int> pt;
    243  
    244 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    245 	return out << "(" << p.x << ", " << p.y << ")";
    246 }
    247 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    248 	fore(i, 0, sz(v)) {
    249 		if(i) out << " ";
    250 		out << v[i];
    251 	}
    252 	return out;
    253 }
    254  
    255 pt operator+ (const pt &a, const pt &b) {
    256 	return {a.x + b.x, a.y + b.y};
    257 }
    258 pt operator- (const pt &a, const pt &b) {
    259 	return {a.x - b.x, a.y - b.y};
    260 }
    261 li operator *(const pt &a, const pt &b) {
    262 	return a.x * 1ll * b.x + a.y * 1ll * b.y;
    263 }
    264 li operator %(const pt &a, const pt &b) {
    265 	return a.x * 1ll * b.y - a.y * 1ll * b.x;
    266 }
    267  
    268 const int INF = int(1e9);
    269 const li INF64 = li(1e18);
    270 const ld EPS = 1e-9;
    271  
    272 int n;
    273 vector<pt> old, nw;
    274  
    275 inline bool read() {
    276 	if(!(cin >> n))
    277 		return false;
    278 	old.resize(n);
    279 	nw.resize(n);
    280 	fore (i, 0, n) {
    281 		old[i].x = i;
    282 		cin >> old[i].y;
    283 	}
    284 	fore (i, 0, n) {
    285 		nw[i].x = i;
    286 		cin >> nw[i].y;
    287 	}
    288 	return true;
    289 }
    290  
    291 inline ld getTr(const pt &a, const pt &b) {
    292 	pt tmp = b - a;
    293 	pt v = {-tmp.y, tmp.x};
    294 	ld c = v * a;
    295 	ld y0 = (c - v.x * 0) / v.y;
    296 	ld y1 = (c - v.x * li(n - 1)) / v.y;
    297 	return (y0 + y1);
    298 }
    299  
    300 vector<pt> hull(const vector<pt> &ps, int l, int r) {
    301 	vector<pt> h;
    302 	fore (i, l, r) {
    303 		while (sz(h) > 1 && (h[sz(h) - 1] - h[sz(h) - 2]) % (ps[i] - h[sz(h) - 1]) >= 0)
    304 			h.pop_back();
    305 		h.push_back(ps[i]);
    306 	}
    307 	return h;
    308 }
    309  
    310 inline void solve() {
    311 	vector<ld> maxTr(n - 1, 0);
    312 	fore (t, 0, 2) {
    313 		auto h = hull(old, n / 2, n);
    314  
    315 		auto best = [&](const pt &p) {
    316 			int l = -1, r = sz(h) - 1;
    317 			while (r - l > 1) {
    318 				int mid = (l + r) >> 1;
    319 				if ((h[mid] - p) % (h[mid + 1] - h[mid]) >= 0)
    320 					l = mid;
    321 				else
    322 					r = mid;
    323 			}
    324 			return h[r].x;
    325 		};
    326 		
    327 		vector<ld> bs(n / 2 + 1, 0);
    328 		for (int i = n / 2 - 1; i >= 0; i--) {
    329 			int j = best(old[i]);
    330 			bs[i] = getTr(old[i], old[j]);
    331 			bs[i] = max(bs[i], bs[i + 1]);
    332 		}
    333 		
    334 		ld lans = 0;
    335 		fore (i, 0, n / 2) {
    336 			int j = best(nw[i]);
    337 			lans = max(lans, getTr(nw[i], old[j]));
    338 			maxTr[i] = max({maxTr[i], lans, bs[i + 1]});
    339 		}
    340 		
    341 		reverse(all(old));
    342 		reverse(all(nw));
    343 		swap(old, nw);
    344 		fore (i, 0, n)
    345 			old[i].x = nw[i].x = i;
    346 		
    347 		reverse(all(maxTr));
    348 	}
    349 			
    350 	maxTr.push_back(maxTr.back());
    351 	cout << maxTr << endl;
    352 }
    353  
    354 int main() {
    355 #ifdef _DEBUG
    356 	freopen("input.txt", "r", stdin);
    357 	int tt = clock();
    358 #endif
    359 	ios_base::sync_with_stdio(false);
    360 	cin.tie(0), cout.tie(0);
    361 	cout << fixed << setprecision(12);
    362 	
    363 	if(read()) {
    364 		solve();
    365 		
    366 #ifdef _DEBUG
    367 		cerr << "TIME = " << clock() - tt << endl;
    368 		tt = clock();
    369 #endif
    370 	}
    371 	return 0;
    372 }
    373 ```