codeforces-scrape

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

1902.md (7285B)


      1 Source: https://codeforces.com/blog/entry/122951
      2 
      3 [1902A - Binary Imbalance](/contest/1902/problem/A "Educational Codeforces Round 159 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (awoo)**
     12 
     13 ```
     14 for _ in range(int(input())):
     15 	n = int(input())
     16 	s = input()
     17 	print("NO" if s.count('1') == n else "YES")
     18 ```
     19 
     20 [1902B - Getting Points](/contest/1902/problem/B "Educational Codeforces Round 159 (Rated for Div. 2)")
     21 
     22 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     23 
     24 **Tutorial**
     25 
     26 Tutorial is loading...
     27 
     28 **Solution (adedalic)**
     29 
     30 ```
     31 fun main(args: Array<String>) {
     32     repeat(readln().toInt()) {
     33         val (n, p, l, t) = readln().split(' ').map { it.toLong() }
     34         val cntTasks = (n + 6) / 7
     35         
     36         fun calc(k: Long) = k * l + minOf(2 * k, cntTasks) * t
     37         var lf = 0L
     38         var rg = n
     39         while (rg - lf > 1) {
     40             val mid = (lf + rg) / 2
     41             if (calc(mid) >= p)
     42                 rg = mid
     43             else
     44                 lf = mid
     45         }
     46         println(n - rg)
     47     }
     48 }
     49 ```
     50 
     51 [1902C - Insert and Equalize](/contest/1902/problem/C "Educational Codeforces Round 159 (Rated for Div. 2)")
     52 
     53 Idea: [Roms](/profile/Roms "Master Roms") и [BledDest](/profile/BledDest "International Grandmaster BledDest")
     54 
     55 **Tutorial**
     56 
     57 Tutorial is loading...
     58 
     59 **Solution (awoo)**
     60 
     61 ```
     62 from math import gcd
     63  
     64 for _ in range(int(input())):
     65 	n = int(input())
     66 	a = list(map(int, input().split()))
     67 	g = 0
     68 	for i in range(n - 1):
     69 		g = gcd(g, a[i + 1] - a[i])
     70 	g = max(g, 1)
     71 	a.sort()
     72 	j = n - 1
     73 	res = a[-1]
     74 	while True:
     75 		while j >= 0 and a[j] > res:
     76 			j -= 1
     77 		if j < 0 or a[j] != res:
     78 			break
     79 		res -= g
     80 	print((a[-1] * (n + 1) - (sum(a) + res)) // g)
     81 ```
     82 
     83 [1902D - Robot Queries](/contest/1902/problem/D "Educational Codeforces Round 159 (Rated for Div. 2)")
     84 
     85 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     86 
     87 **Tutorial**
     88 
     89 Tutorial is loading...
     90 
     91 **Solution (Neon)**
     92 
     93 ```
     94 #include <bits/stdc++.h>
     95  
     96 using namespace std;
     97  
     98 #define x first
     99 #define y second
    100  
    101 using pt = pair<int, int>;
    102  
    103 int main() {
    104   ios::sync_with_stdio(false); cin.tie(0);
    105   int n, q;
    106   cin >> n >> q;
    107   string s;
    108   cin >> s;
    109   vector<pt> pos(n + 1);
    110   for (int i = 0; i < n; ++i) {
    111     pos[i + 1].x = pos[i].x + (s[i] == 'R') - (s[i] == 'L');
    112     pos[i + 1].y = pos[i].y + (s[i] == 'U') - (s[i] == 'D');
    113   }
    114   map<pt, vector<int>> mp;
    115   for (int i = 0; i <= n; ++i) mp[pos[i]].push_back(i);
    116   auto check = [&](pt p, int l, int r) {
    117   	if (!mp.count(p)) return false;
    118   	auto it = lower_bound(mp[p].begin(), mp[p].end(), l);
    119   	return it != mp[p].end() && *it <= r;
    120   };
    121   while (q--) {
    122   	int x, y, l, r;
    123   	cin >> x >> y >> l >> r;
    124   	int nx = pos[r].x + pos[l - 1].x - x, ny = pos[r].y + pos[l - 1].y - y;
    125   	bool f = check({x, y}, 0, l - 1)
    126   	       | check({nx, ny}, l, r - 1)
    127   	       | check({x, y}, r, n);
    128   	cout << (f ? "YES" : "NO") << '\n';
    129   }
    130 }
    131 ```
    132 
    133 [1902E - Collapsing Strings](/contest/1902/problem/E "Educational Codeforces Round 159 (Rated for Div. 2)")
    134 
    135 Idea: [Roms](/profile/Roms "Master Roms")
    136 
    137 **Tutorial**
    138 
    139 Tutorial is loading...
    140 
    141 **Solution (Roms)**
    142 
    143 ```
    144 #include <bits/stdc++.h>
    145  
    146 using namespace std;
    147  
    148 const int N = int(1e6) + 99;
    149  
    150 int nxt;
    151 int to[N][26];
    152 int sum[N];
    153 long long res;
    154  
    155 void add(const string& s) {
    156     int v = 0;
    157     ++sum[v];
    158     for (auto c : s) {
    159         int i = c - 'a';
    160         if (to[v][i] == -1)
    161             to[v][i] = nxt++;
    162         v = to[v][i];
    163         ++sum[v];
    164     }
    165 }
    166  
    167 void upd(const string& s) {
    168     int curLen = s.size();
    169     int v = 0;
    170     
    171     for (auto c : s) {
    172         int i = c - 'a';
    173         if (to[v][i] == -1) {
    174             res += sum[v] * 1LL * curLen;
    175             break;
    176         } else {
    177             int nxtV = to[v][i];
    178             res += (sum[v] - sum[nxtV]) * 1LL * curLen;
    179             --curLen;
    180             v = nxtV;
    181         }
    182     }
    183 }
    184  
    185 void solve(int n, vector <string> v) {
    186     int sumSizes = 0;
    187     for (int i = 0; i < n; ++i)
    188         sumSizes += v[i].size();
    189         
    190     nxt = 1;
    191     memset(sum, 0, sizeof sum);
    192     memset(to, -1, sizeof to);
    193     
    194     for(int i = 0; i < n; ++i) 
    195         add(v[i]);
    196     for (int i = 0; i < n; ++i) {
    197         reverse(v[i].begin(), v[i].end());
    198         upd(v[i]);
    199     }
    200 }
    201  
    202 int main() {
    203     ios_base::sync_with_stdio(false);
    204     int n;
    205     cin >> n;
    206     vector <string> v(n);
    207     for (int i = 0; i < n; ++i) 
    208         cin >> v[i];
    209     
    210     res = 0;
    211     solve(n, v);
    212     for(int i = 0; i < n; ++i)
    213         reverse(v[i].end(), v[i].end());
    214     solve(n, v);
    215     
    216     cout << res << endl;
    217     
    218     return 0;
    219 }
    220 ```
    221 
    222 [1902F - Trees and XOR Queries Again](/contest/1902/problem/F "Educational Codeforces Round 159 (Rated for Div. 2)")
    223 
    224 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    225 
    226 **Tutorial**
    227 
    228 Tutorial is loading...
    229 
    230 **Solution (BledDest)**
    231 
    232 ```
    233 #include<bits/stdc++.h>
    234  
    235 using namespace std;
    236  
    237 const int N = 200043;
    238 const int K = 20;
    239  
    240 typedef array<int, K> base;
    241 int a[N];
    242 vector<int> g[N];
    243 vector<int> path_up[N];
    244 int tin[N], tout[N];
    245 int T = 0;
    246 int fup[N][K];
    247  
    248 base make_empty()
    249 {
    250     base b;
    251     for(int i = 0; i < K; i++)
    252         b[i] = 0;
    253     return b;
    254 }
    255  
    256 int reduce(const base& b, int x)
    257 {
    258     for(int i = K - 1; i >= 0; i--)
    259         if(x & (1 << i))
    260             x ^= b[i];
    261     return x;
    262 }   
    263  
    264 bool add(base& b, int x)
    265 {
    266     x = reduce(b, x);
    267     if(x != 0)
    268     {
    269         for(int i = K - 1; i >= 0; i--)
    270             if(x & (1 << i))
    271             {
    272                 b[i] = x;
    273                 return true;
    274             }
    275     }   
    276     return false;
    277 }
    278  
    279 bool check(const base& b, int x)
    280 {
    281     return reduce(b, x) == 0;
    282 }
    283  
    284 vector<int> rebuild_path(const vector<int>& path, int v)
    285 {
    286     base b = make_empty();
    287     vector<int> ans;
    288     if(add(b, a[v])) ans.push_back(v);
    289     for(auto x : path) if(add(b, a[x])) ans.push_back(x);
    290     return ans;
    291 }
    292  
    293 void dfs(int v, int u)
    294 {
    295     tin[v] = T++;      
    296     if(u == v)
    297         path_up[v] = rebuild_path(vector<int>(0), v);
    298     else
    299         path_up[v] = rebuild_path(path_up[u], v);
    300     fup[v][0] = u;
    301     for(int i = 1; i < K; i++)
    302         fup[v][i] = fup[fup[v][i - 1]][i - 1];
    303     for(auto y : g[v])
    304         if(y != u)
    305             dfs(y, v);
    306     tout[v] = T++;   
    307 }
    308  
    309 bool is_ancestor(int u, int v)
    310 {
    311     return tin[u] <= tin[v] && tout[u] >= tout[v];
    312 }
    313  
    314 int LCA(int x, int y)
    315 {
    316     if(is_ancestor(x, y)) return x;
    317     for(int i = K - 1; i >= 0; i--)
    318         if(!is_ancestor(fup[x][i], y))
    319             x = fup[x][i];
    320     return fup[x][0];
    321 }
    322  
    323 bool query(int x, int y, int k)
    324 {
    325     base b = make_empty();
    326     int z = LCA(x, y);
    327     for(auto v : path_up[x])
    328         if(!is_ancestor(v, y))
    329             add(b, a[v]);
    330     for(auto v : path_up[y])
    331         if(!is_ancestor(v, x))
    332             add(b, a[v]);
    333     add(b, a[z]);
    334     return check(b, k);            
    335 }
    336  
    337 int main()
    338 {
    339     int n;
    340 	scanf("%d", &n);
    341 	for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    342 	for(int i = 0; i < n - 1; i++)
    343 	{
    344 		int x, y;
    345 		scanf("%d %d", &x, &y);
    346 		--x;
    347 		--y;
    348 		g[x].push_back(y);
    349 		g[y].push_back(x);
    350 	}
    351 	dfs(0, 0);
    352 	int q;
    353 	scanf("%d", &q);
    354 	for(int i = 0; i < q; i++)
    355 	{
    356 		int x, y, k;
    357 		scanf("%d %d %d", &x, &y, &k);
    358 		--x;
    359 		--y;
    360 		if(query(x, y, k)) puts("YES");
    361 		else puts("NO");
    362 	}
    363 }
    364 ```