codeforces-scrape

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

1606.md (8953B)


      1 Source: https://codeforces.com/blog/entry/96454
      2 
      3 [1606A - AB Balance](/contest/1606/problem/A "Educational Codeforces Round 116 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (adedalic)**
     12 
     13 ```
     14 fun main() {
     15     repeat(readLine()!!.toInt()) {
     16         val s = readLine()!!
     17         println(s.last() + s.substring(1))
     18     }
     19 }
     20 ```
     21 
     22 [1606B - Update Files](/contest/1606/problem/B "Educational Codeforces Round 116 (Rated for Div. 2)")
     23 
     24 **Tutorial**
     25 
     26 Tutorial is loading...
     27 
     28 **Solution (Neon)**
     29 
     30 ```
     31 #include <bits/stdc++.h>
     32 
     33 using namespace std;
     34 
     35 using li = long long;
     36 
     37 int main() {
     38   ios_base::sync_with_stdio(false);
     39   cin.tie(NULL); 
     40   int t;
     41   cin >> t;
     42   while (t--) {
     43     li n, k;
     44     cin >> n >> k;
     45     li ans = 0, cur = 1;
     46     while (cur < k) {
     47       cur *= 2;
     48       ++ans;
     49     }
     50     if (cur < n) ans += (n - cur + k - 1) / k;
     51     cout << ans << '\n';
     52   }
     53 }
     54 ```
     55 
     56 [1606C - Banknotes](/contest/1606/problem/C "Educational Codeforces Round 116 (Rated for Div. 2)")
     57 
     58 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     59 
     60 **Tutorial**
     61 
     62 Tutorial is loading...
     63 
     64 **Solution (Neon)**
     65 
     66 ```
     67 #include <bits/stdc++.h>
     68 
     69 using namespace std;
     70 
     71 int main() {
     72   int t;
     73   cin >> t;
     74   while (t--) {
     75     int n, k;
     76     cin >> n >> k;
     77     k += 1;
     78     vector<int> a(n);
     79     for (int& x : a) {
     80       cin >> x;
     81       int cur = 1;
     82       while (x--) cur *= 10;
     83       x = cur;
     84     }
     85     long long res = 0;
     86     for (int i = 0; i < n; i++) {
     87       int cnt = k;
     88       if (i + 1 < n) cnt = min(cnt, a[i + 1] / a[i] - 1);
     89       res += a[i] * 1LL * cnt;
     90       k -= cnt;
     91     }
     92     cout << res << '\n';
     93   }
     94 }
     95 ```
     96 
     97 [1606D - Red-Blue Matrix](/contest/1606/problem/D "Educational Codeforces Round 116 (Rated for Div. 2)")
     98 
     99 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    100 
    101 **Tutorial**
    102 
    103 Tutorial is loading...
    104 
    105 **Solution (awoo)**
    106 
    107 ```
    108 #include <bits/stdc++.h>
    109 
    110 #define forn(i, n) for (int i = 0; i < int(n); i++)
    111 
    112 using namespace std;
    113 
    114 const int INF = 1e9;
    115 
    116 int main() {
    117 	int tc;
    118 	scanf("%d", &tc);
    119 	while (tc--){
    120 		int n, m;
    121 		scanf("%d%d", &n, &m);
    122 		vector<vector<int>> a(n, vector<int>(m));
    123 		forn(i, n) forn(j, m) scanf("%d", &a[i][j]);
    124 		vector<int> ord(n);
    125 		iota(ord.begin(), ord.end(), 0);
    126 		sort(ord.begin(), ord.end(), [&a](int x, int y){ return a[x][0] > a[y][0]; });
    127 		vector<vector<int>> mxl(n, vector<int>(m, -INF));
    128 		vector<vector<int>> mnr(n, vector<int>(m, INF));
    129 		for (int i = n - 1; i >= 0; --i) forn(j, m){
    130 			mxl[i][j] = a[ord[i]][j];
    131 			if (i < n - 1) mxl[i][j] = max(mxl[i][j], mxl[i + 1][j]);
    132 			if (j > 0) mxl[i][j] = max(mxl[i][j], mxl[i][j - 1]);
    133 		}
    134 		for (int i = n - 1; i >= 0; --i) for (int j = m - 1; j >= 0; --j){
    135 			mnr[i][j] = a[ord[i]][j];
    136 			if (i < n - 1) mnr[i][j] = min(mnr[i][j], mnr[i + 1][j]);
    137 			if (j < m - 1) mnr[i][j] = min(mnr[i][j], mnr[i][j + 1]);
    138 		}
    139 		vector<int> mnl(m, INF), mxr(m, -INF);
    140 		pair<int, int> ans(-1, -1);
    141 		forn(i, n - 1){
    142 			forn(j, m){
    143 				mnl[j] = min(mnl[j], a[ord[i]][j]);
    144 				if (j > 0) mnl[j] = min(mnl[j], mnl[j - 1]);
    145 			}
    146 			for (int j = m - 1; j >= 0; --j){
    147 				mxr[j] = max(mxr[j], a[ord[i]][j]);
    148 				if (j < m - 1) mxr[j] = max(mxr[j], mxr[j + 1]);
    149 			}
    150 			forn(j, m - 1) if (mnl[j] > mxl[i + 1][j] && mxr[j + 1] < mnr[i + 1][j + 1]){
    151 				ans = {i, j};
    152 			}
    153 		}
    154 		if (ans.first == -1){
    155 			puts("NO");
    156 			continue;
    157 		}
    158 		puts("YES");
    159 		string res(n, '.');
    160 		forn(i, n) res[ord[i]] = i <= ans.first ? 'R' : 'B';
    161 		printf("%s %d\n", res.c_str(), ans.second + 1);
    162 	}
    163 	return 0;
    164 }
    165 ```
    166 
    167 [1606E - Arena](/contest/1606/problem/E "Educational Codeforces Round 116 (Rated for Div. 2)")
    168 
    169 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    170 
    171 **Tutorial**
    172 
    173 Tutorial is loading...
    174 
    175 **Solution (Neon)**
    176 
    177 ```
    178 #include <bits/stdc++.h>
    179 
    180 using namespace std;
    181 
    182 const int N = 505;
    183 const int MOD = 998244353;
    184 
    185 int n, x;
    186 int c[N][N], dp[N][N];
    187 
    188 int add(int x, int y) {
    189   x += y;
    190   if (x >= MOD) x -= MOD;
    191   return x;
    192 }
    193 
    194 int mul(int x, int y) {
    195   return x * 1ll * y % MOD;
    196 }
    197 
    198 int main() {
    199   cin >> n >> x;
    200   for (int i = 0; i <= n; ++i) {
    201     c[i][0] = c[i][i] = 1;
    202     for (int j = 1; j < i; ++j) 
    203       c[i][j] = add(c[i - 1][j], c[i - 1][j - 1]);
    204   }
    205   dp[n][0] = 1;
    206   for (int i = n; i > 1; i--) {
    207     for (int j = 0; j < x; ++j) {
    208       if (!dp[i][j]) continue;
    209       int pw = 1, nj = min(x, j + i - 1);
    210       for (int k = i; k >= 0; k--) {
    211         dp[k][nj] = add(dp[k][nj], mul(dp[i][j], mul(c[i][k], pw)));
    212         pw = mul(pw, nj - j);
    213       }
    214     }
    215   }
    216   int ans = 0;
    217   for (int i = 0; i <= x; ++i)
    218     ans = add(ans, dp[0][i]);
    219   cout << ans << endl;
    220 }
    221 ```
    222 
    223 [1606F - Tree Queries](/contest/1606/problem/F "Educational Codeforces Round 116 (Rated for Div. 2)")
    224 
    225 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    226 
    227 **Tutorial**
    228 
    229 Tutorial is loading...
    230 
    231 **Solution (BledDest)**
    232 
    233 ```
    234 #include <bits/stdc++.h>     
    235 
    236 using namespace std;
    237 
    238 struct Vertex
    239 {
    240  	int cost;
    241  	int depth;
    242  	int idx;
    243  	Vertex() {};
    244  	Vertex(int cost, int depth, int idx) : cost(cost), depth(depth), idx(idx) {};
    245 };
    246 
    247 bool operator <(const Vertex& a, const Vertex& b)
    248 {
    249  	if(a.cost != b.cost)
    250  		return a.cost > b.cost;
    251  	if(a.depth != b.depth)
    252  		return a.depth > b.depth;
    253  	return a.idx < b.idx;
    254 }
    255 
    256 struct DSU
    257 {
    258 	int n;
    259  	vector<int> p;
    260  	vector<int> top;
    261 
    262  	int get(int x)
    263  	{
    264  		if(p[x] == x)
    265  			return x;
    266  		return p[x] = get(p[x]); 	
    267  	}
    268 
    269  	int get_top(int x)
    270  	{
    271  	 	return top[get(x)];
    272  	}
    273 
    274  	void merge(int x, int par)
    275  	{
    276  	 	p[x] = par;
    277  	}
    278 
    279  	DSU(int k = 0)
    280  	{
    281  	 	n = k;
    282  	 	p.resize(n);
    283  	 	iota(p.begin(), p.end(), 0);
    284  	 	top = p;
    285  	};
    286 };
    287 
    288 const int N = 200043;
    289 
    290 int n;
    291 vector<int> g[N];
    292 int p[N], d[N], tin[N], tout[N];
    293 int qv[N];
    294 int qk[N];
    295 int T = 0;
    296 
    297 void dfs(int v = 0, int par = -1)
    298 {
    299  	tin[v] = T++;
    300  	p[v] = par;
    301  	if(par == -1)
    302  		d[v] = 0;
    303  	else
    304  		d[v] = d[par] + 1;
    305  	for(auto x : g[v])
    306  		if(x != par)
    307  			dfs(x, v);
    308  	tout[v] = T;
    309 }
    310 
    311 pair<long long, long long> tree[4 * N];
    312 
    313 pair<long long, long long> operator+(const pair<long long, long long>& a, const pair<long long, long long>& b)
    314 {
    315  	return make_pair(a.first + b.first, a.second + b.second);
    316 }
    317 
    318 pair<long long, long long> get(int v, int l, int r, int L, int R)
    319 {
    320  	if(L >= R) return {0, 0};
    321  	if(l == L && r == R) return tree[v];
    322  	int m = (l + r) / 2;
    323  	return get(v * 2 + 1, l, m, L, min(R, m)) + get(v * 2 + 2, m, r, max(m, L), R);
    324 }
    325 
    326 void add(int v, int l, int r, int pos, pair<long long, long long> val)
    327 {
    328  	if(l == r - 1)
    329  		tree[v] = tree[v] + val;
    330  	else
    331  	{
    332  	 	int m = (l + r) / 2;
    333  	 	if(pos < m) add(v * 2 + 1, l, m, pos, val);
    334  	 	else add(v * 2 + 2, m, r, pos, val);
    335  	 	tree[v] = tree[v] + val;
    336  	}                                                                  
    337 }
    338 
    339 pair<long long, long long> get_vertex_value(int v)
    340 {
    341  	return get(0, 0, n, tin[v], tout[v]);
    342 }
    343 
    344 void add_on_path(int x, int y, pair<long long, long long> val)
    345 {
    346  	// x is a descendant of y
    347  	add(0, 0, n, tin[x], val);
    348  	if(p[y] != -1)
    349  		add(0, 0, n, tin[p[y]], make_pair(-val.first, -val.second));
    350 }
    351 
    352 int calculate_cost(int v, int correction)
    353 {
    354 	//cerr << v << " " << correction << endl;
    355  	pair<long long, long long> res = get_vertex_value(v);
    356  	// first - (second + 1) * k <= 0
    357  	long long k = (res.first + res.second) / (res.second + 1) - 1;
    358  	if(correction < k) return correction;
    359  	return k;
    360 }
    361 
    362 int main()
    363 {
    364 	scanf("%d", &n);
    365 	for(int i = 1; i < n; i++)
    366 	{
    367 	 	int x, y;
    368 	 	scanf("%d %d", &x, &y);
    369 	 	--x;
    370 	 	--y;
    371 	 	g[x].push_back(y);
    372 	 	g[y].push_back(x);
    373 	}
    374 	int q;
    375 	scanf("%d", &q);
    376 	for(int i = 0; i < q; i++)
    377 	{
    378 	 	scanf("%d %d", &qv[i], &qk[i]);
    379 	 	--qv[i];
    380 	}                   
    381 
    382 	dfs();
    383 	DSU dsu(n);
    384                         
    385 	vector<long long> ans(q);
    386 	set<Vertex> pq;
    387 	vector<Vertex> curv(n);
    388 	for(int i = 0; i < n; i++)
    389 	{                     
    390 	 	int count_children = g[i].size();
    391 	 	if(i != 0) count_children--;               
    392 	 	add_on_path(i, i, make_pair((long long)(count_children), 0ll)); 
    393 	 	if(i != 0)
    394 	 	{
    395 	 		curv[i] = Vertex(calculate_cost(i, 200000), d[i], i);
    396 			pq.insert(curv[i]);                                   
    397 	 	}
    398                           
    399 	}
    400                         
    401 	for(int i = 0; i < q; i++)
    402 		pq.insert(Vertex(qk[i], -1, i));
    403 
    404 	while(!pq.empty())
    405 	{
    406 		Vertex z = *pq.begin();
    407 		pq.erase(pq.begin());
    408 		if(z.depth == -1)
    409 		{
    410 		 	auto res = get_vertex_value(qv[z.idx]);
    411 		 	ans[z.idx] = res.first - res.second * z.cost;
    412 	    }
    413 	    else
    414 	    {
    415 	     	int v = z.idx;
    416 	     	int pv = p[v];
    417 	     	int newtop = dsu.get_top(pv);
    418 	     	pair<long long, long long> val = get_vertex_value(v);
    419 	     	val.second++;
    420 	     	val.first--;
    421 	     	if(newtop != 0)
    422 	     		pq.erase(curv[newtop]);
    423 	     	add_on_path(pv, newtop, val);
    424 	     	if(newtop != 0)
    425 	     		curv[newtop].cost = calculate_cost(newtop, z.cost);
    426 	     	if(newtop != 0)
    427 	     		pq.insert(curv[newtop]);
    428 	     	dsu.merge(v, pv);
    429 	    }
    430 	}	
    431 
    432 	for(int i = 0; i < q; i++)
    433 		printf("%lld\n", ans[i]);
    434 }
    435 ```