codeforces-scrape

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

1709.md (4855B)


      1 Source: https://codeforces.com/blog/entry/105164
      2 
      3 [1709A - Three Doors](/contest/1709/problem/A "Educational Codeforces Round 132 (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 	x = int(input())
     16 	a = [0] + [int(x) for x in input().split()]
     17 	print("YES" if a[x] != 0 and a[a[x]] != 0 else "NO")
     18 ```
     19 
     20 [1709B - Also Try Minecraft](/contest/1709/problem/B "Educational Codeforces Round 132 (Rated for Div. 2)")
     21 
     22 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     23 
     24 **Tutorial**
     25 
     26 Tutorial is loading...
     27 
     28 **Solution (vovuh)**
     29 
     30 ```
     31 n, m = map(int, input().split())
     32 a = list(map(int, input().split()))
     33 l = [0] + [max(0, a[i] - a[i + 1]) for i in range(n - 1)]
     34 r = [0] + [max(0, a[i] - a[i - 1]) for i in range(1, n)]
     35 for i in range(n - 1):
     36     l[i + 1] += l[i]
     37     r[i + 1] += r[i]
     38 for _ in range(m):
     39     s, t = map(int, input().split())
     40     if s < t:
     41         print(l[t - 1] - l[s - 1])
     42     else:
     43         print(r[s - 1] - r[t - 1])
     44 ```
     45 
     46 [1709C - Recover an RBS](/contest/1709/problem/C "Educational Codeforces Round 132 (Rated for Div. 2)")
     47 
     48 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     49 
     50 **Tutorial**
     51 
     52 Tutorial is loading...
     53 
     54 **Solution (Neon)**
     55 
     56 ```
     57 #include <bits/stdc++.h>
     58 
     59 using namespace std;
     60 
     61 int main() {
     62   auto check = [](const string& s) {
     63     int bal = 0;
     64     for (char c : s) {
     65       if (c == '(') ++bal;
     66       if (c == ')') --bal;
     67       if (bal < 0) return false;
     68     }
     69     return bal == 0;
     70   };
     71   
     72   ios::sync_with_stdio(false); cin.tie(0);
     73   int t;
     74   cin >> t;
     75   while (t--) {
     76     string s;
     77     cin >> s;
     78     vector<int> pos;
     79     int op = s.size() / 2, cl = s.size() / 2;
     80     for (int i = 0; i < s.size(); ++i) {
     81       if (s[i] == '?') pos.push_back(i);
     82       if (s[i] == '(') --op;
     83       if (s[i] == ')') --cl;
     84     }
     85     for (int i = 0; i < pos.size(); ++i) {
     86       if (i < op) s[pos[i]] = '(';
     87       else s[pos[i]] = ')';
     88     }
     89     bool ok = true;
     90     if (op > 0 && cl > 0) {
     91       swap(s[pos[op - 1]], s[pos[op]]);
     92       if (check(s)) ok = false;
     93     }
     94     cout << (ok ? "YES\n" : "NO\n");
     95   }
     96 }
     97 ```
     98 
     99 [1709D - Rorororobot](/contest/1709/problem/D "Educational Codeforces Round 132 (Rated for Div. 2)")
    100 
    101 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    102 
    103 **Tutorial**
    104 
    105 Tutorial is loading...
    106 
    107 **Solution (awoo)**
    108 
    109 ```
    110 #include <bits/stdc++.h>
    111 
    112 #define forn(i, n) for (int i = 0; i < int(n); i++)
    113 
    114 using namespace std;
    115 
    116 int main() {
    117 	int n, m;
    118 	scanf("%d%d", &n, &m);
    119 	vector<int> a(m);
    120 	forn(i, m) scanf("%d", &a[i]);
    121 	
    122 	int l = 0;
    123 	while ((1 << l) <= m) ++l;
    124 	vector<vector<int>> st(l, vector<int>(m));
    125 	forn(i, m) st[0][i] = a[i];
    126 	for (int j = 1; j < l; ++j) forn(i, m){
    127 		st[j][i] = st[j - 1][i];
    128 		if (i + (1 << (j - 1)) < m)
    129 			st[j][i] = max(st[j][i], st[j - 1][i + (1 << (j - 1))]);
    130 	}
    131 	vector<int> pw(m + 1, 0);
    132 	for (int i = 2; i <= m; ++i) pw[i] = pw[i / 2] + 1;
    133 	auto get = [&](int l, int r){
    134 		if (l > r) swap(l, r);
    135 		++r;
    136 		int len = pw[r - l];
    137 		return max(st[len][l], st[len][r - (1 << len)]);
    138 	};
    139 	
    140 	int q;
    141 	scanf("%d", &q);
    142 	forn(_, q){
    143 		int xs, ys, xf, yf, k;
    144 		scanf("%d%d%d%d%d", &xs, &ys, &xf, &yf, &k);
    145 		--xs, --ys, --xf, --yf;
    146 		if (ys % k != yf % k || xs % k != xf % k){
    147 			puts("NO");
    148 			continue;
    149 		}
    150 		int mx = (n - xs - 1) / k * k + xs;
    151 		puts(get(ys, yf) <= mx ? "YES" : "NO");
    152 	}
    153 	return 0;
    154 }
    155 ```
    156 
    157 [1709E - XOR Tree](/contest/1709/problem/E "Educational Codeforces Round 132 (Rated for Div. 2)")
    158 
    159 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    160 
    161 **Tutorial**
    162 
    163 Tutorial is loading...
    164 
    165 **Solution (Neon)**
    166 
    167 ```
    168 #include <bits/stdc++.h>
    169 
    170 using namespace std;
    171 
    172 const int N = 200 * 1000 + 13;
    173 
    174 int n;
    175 int a[N], b[N];
    176 vector<int> g[N];
    177 set<int> vals[N];
    178 
    179 void init(int v, int p) {
    180   b[v] = a[v];
    181   if (p != -1) b[v] ^= b[p];
    182   for (int u : g[v]) if (u != p)
    183     init(u, v);
    184 }
    185 
    186 int ans;
    187 
    188 void calc(int v, int p) {
    189   bool bad = false;
    190   vals[v].insert(b[v]);
    191   for (int u : g[v]) if (u != p) {
    192     calc(u, v);
    193     if (vals[v].size() < vals[u].size()) vals[v].swap(vals[u]);
    194     for (int x : vals[u]) bad |= vals[v].count(x ^ a[v]);
    195     for (int x : vals[u]) vals[v].insert(x);
    196     vals[u].clear();
    197   }
    198   if (bad) {
    199     ans += 1;
    200     vals[v].clear();
    201   }
    202 }
    203 
    204 int main() {
    205   ios::sync_with_stdio(false); cin.tie(0);
    206   cin >> n;
    207   for (int i = 0; i < n; ++i) cin >> a[i];
    208   for (int i = 0; i < n - 1; ++i) {
    209     int x, y;
    210     cin >> x >> y;
    211     --x; --y;
    212     g[x].push_back(y);
    213     g[y].push_back(x);
    214   }
    215   init(0, -1);
    216   calc(0, -1);
    217   cout << ans << '\n';
    218 }
    219 ```
    220 
    221 [1709F - Multiset of Strings](/contest/1709/problem/F "Educational Codeforces Round 132 (Rated for Div. 2)")
    222 
    223 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    224 
    225 **Tutorial**
    226 
    227 Tutorial is loading...