codeforces-scrape

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

1787.md (6613B)


      1 Source: https://codeforces.com/blog/entry/112009
      2 
      3 [1787A - Exponential Equation](/contest/1787/problem/A)
      4 
      5 Idea & Solution: [rsj](/profile/rsj "Master rsj")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 [1787B - Number Factorization](/contest/1787/problem/B)
     12 
     13 Idea & Solution: [rsj](/profile/rsj "Master rsj")
     14 
     15 **Tutorial**
     16 
     17 Tutorial is loading...
     18 
     19 **Solution**
     20 
     21 ```
     22 #include <bits/stdc++.h>
     23 using namespace std;
     24 #define mp make_pair
     25 pair<int, int> s[110];
     26 int d[110];
     27 void get() {
     28 	int n, l = 0, i, c;
     29 	cin >> n;
     30 	for (i = 2; i * i <= n; i++) {
     31 		if (n % i == 0) {
     32 			c = 0;
     33 			while (n % i == 0) c++, n /= i;
     34 			s[++l] = make_pair(c, i);
     35 		}
     36 	}
     37 	if (n != 1) s[++l] = make_pair(1, n);
     38 	sort(s + 1, s + l + 1), d[l + 1] = 1;
     39 	for (i = l; i >= 1; i--) d[i] = d[i + 1] * s[i].second;
     40 	int ans = 0;
     41 	for (i = 1; i <= l; i++) if (s[i].first != s[i - 1].first) ans += d[i] * (s[i].first - s[i - 1].first);
     42 	cout << ans << endl;
     43 }
     44 signed main() {
     45 	ios::sync_with_stdio(0);
     46 	cin.tie(0);
     47 	int T;
     48 	cin >> T;
     49 	while (T--) get();
     50 	return 0;
     51 }
     52 ```
     53 
     54 [1787C - Remove the Bracket](/contest/1787/problem/C)
     55 
     56 Idea & Solution: [rsj](/profile/rsj "Master rsj")
     57 
     58 **Fact**
     59 
     60 This is the reason why the problem was named as *Remove the Bracket*.
     61 
     62 $ \begin{aligned} \text{Product} &= a_1 \cdot a_2 \cdot a_3 \cdot \ldots \cdot a_n = \\ &= a_1 \cdot (x_2+y_2) \cdot (x_3+y_3) \cdot \ldots \cdot (x_{n-1}+y_{n-1}) \cdot a_n = \\ &\overset{\text{?}}{=} a_1 \cdot x_2+y_2 \cdot x_3+y_3 \cdot \ldots \cdot x_{n-1}+y_{n-1} \cdot a_n. \end{aligned} $
     63 
     64 However, We discussed to remove it on 28th Jan in the statement. Really sorry for inconvenience of the statement!
     65 
     66 **Tutorial**
     67 
     68 Tutorial is loading...
     69 
     70 **Solution**
     71 
     72 ```
     73 #include <bits/stdc++.h>
     74 using namespace std;
     75 const int N = 200005;
     76 long long f[N][2],x[N],y[N];
     77 void get() {
     78 	int i,n,s,j;
     79 	cin>>n>>s;
     80 	for(i=1; i<=n; i++) {
     81 		cin>>j;
     82 		if(i==1||i==n) x[i]=y[i]=j;
     83 		else if(j<=s) x[i]=0,y[i]=j;
     84 		else x[i]=s,y[i]=j-s;
     85 	}
     86 	f[1][0]=f[1][1]=0;
     87 	for(i=2; i<=n; i++) {
     88 		f[i][0]=min(f[i-1][0]+y[i-1]*x[i],f[i-1][1]+x[i-1]*x[i]);
     89 		f[i][1]=min(f[i-1][0]+y[i-1]*y[i],f[i-1][1]+x[i-1]*y[i]);
     90 	}
     91 	cout<<f[n][0]<<endl;
     92 }
     93 int main() {
     94 	ios::sync_with_stdio(0);
     95 	cin.tie(0);
     96 	int T; cin>>T;
     97 	while(T--) get();
     98 	return 0;
     99 }
    100 ```
    101 
    102 [1787D - Game on Axis](/contest/1787/problem/D)
    103 
    104 Idea & Solution: [jiangtaizhe001](/profile/jiangtaizhe001 "Candidate Master jiangtaizhe001")
    105 
    106 **Tutorial**
    107 
    108 Tutorial is loading...
    109 
    110 **Solution**
    111 
    112 ```
    113 #include <bits/stdc++.h>
    114 using namespace std;
    115 const int N = 200005;
    116 int a[N];
    117 int v[N]; //= 1 -> in the tree with the end node
    118 int s[N]; //subtree size
    119 struct E {
    120 	int to;
    121 	E *nex;
    122 } *h[N];
    123 void add(int u, int v) {
    124 	E *cur = new E;
    125 	cur->to = v, cur->nex = h[u], h[u] = cur;
    126 }
    127 void dfs(int u) {
    128 	s[u] = v[u] = 1;
    129 	for (E *cur = h[u]; cur; cur = cur->nex)
    130 		dfs(cur->to), s[u] += s[cur->to];
    131 }
    132 void get() {
    133 	int i, j, n;
    134 	cin >> n;
    135 	for (i = 1; i <= n + 1; i++)
    136 		s[i] = v[i] = 0, h[i] = 0;
    137 	for (i = 1; i <= n; i++) {
    138 		cin >> a[i], a[i] = min(i + a[i], n + 1);
    139 		if (a[i] <= 0) a[i] = n + 1;
    140 		add(a[i], i);
    141 	}
    142 	dfs(n + 1); //start with the end point, dfs the tree
    143 	long long ans = 0;
    144 	if (v[1] == 1) {
    145 		j = 1; do { ans -= s[j] + (n - s[n + 1] + 1), j = a[j]; }
    146 		while (j != n + 1);
    147 		ans += 1ll * n * (2 * n + 1);
    148 	} else {
    149 		j = 1; do { ans += (n + s[n + 1]), v[j] = 2, j = a[j]; }
    150 		while (v[j] != 2);
    151 	}
    152 	cout << ans << endl;
    153 }
    154 int main() {
    155 	ios::sync_with_stdio(0);
    156 	cin.tie(0);
    157 	int T;
    158 	cin >> T;
    159 	while (T--) get();
    160 	return 0;
    161 }
    162 ```
    163 
    164 [1787E - The Harmonization of XOR](/contest/1787/problem/E)
    165 
    166 Idea & Solution: [jiangtaizhe001](/profile/jiangtaizhe001 "Candidate Master jiangtaizhe001"), [rsj](/profile/rsj "Master rsj")
    167 
    168 **Tutorial**
    169 
    170 Tutorial is loading...
    171 
    172 **Bonus Problem**
    173 
    174 **Bonus Problem:** What if $x=0$?
    175 
    176 [1787F - Inverse Transformation](/contest/1787/problem/F)
    177 
    178 Idea & Solution: [qzhwlzy](/profile/qzhwlzy "Specialist qzhwlzy"), [rsj](/profile/rsj "Master rsj")
    179 
    180 **Tutorial**
    181 
    182 Tutorial is loading...
    183 
    184 **Solution**
    185 
    186 ```
    187 #include <bits/stdc++.h>
    188 using namespace std;
    189 const int N = 200005;
    190 int dest[N], visit[N], ans[N], mp[N], ansinv[N], sp;
    191 int pow2(int y, int M) {
    192 	long long x = 2, ans = 1;
    193 	while (y) {
    194 		if (y & 1) ans = ans * x % M;
    195 		x = x * x % M, y >>= 1;
    196 	}
    197 	return ans % M;
    198 }
    199 vector<int> cyc[N];
    200 void get() {
    201 	sp = 0;
    202 	int n, i, j, m, z, o;
    203 	cin >> n >> m;
    204 	for (i = 1; i <= n; i++) cyc[i].clear();
    205 	for (i = 1; i <= n; i++) visit[i] = 0, cin >> dest[i];
    206 	for (i = 1; i <= n; i++) {
    207 		if (visit[i]) continue;
    208 		j = i, z = 0; do { ++z, visit[j] = 1, j = dest[j]; } while (j != i);
    209 		cyc[z].push_back(i);
    210 	}
    211 	int lim = pow2(min(m, 20), 1e9), s = 0, d, t, num, cp;
    212 	for (i = 1; i <= n; i++) {
    213 		if (!cyc[i].size()) continue;
    214 		int siz = cyc[i].size();
    215 		if (i % 2 == 0 && siz % lim) {
    216 			cout << "NO" << endl; return;
    217 		} else {
    218 			cp = -1;
    219 			for (j = lim; j > 0; j /= 2) {
    220 				while (siz >= j) {
    221 					siz -= j, d = s + j * i, t = j;
    222 					while (t--) {
    223 						++s, ++cp, num = s, o = cyc[i][cp];
    224 						do {
    225 						    ans[num] = o, num += pow2(m, i * j);
    226 						    if (num > d) num -= j * i;
    227 						    o = dest[o];
    228 						} while (o != cyc[i][cp]);
    229 					}
    230 					for (int k = sp + 1; k < sp + j * i; k++) mp[k] = k + 1;
    231 					mp[sp + j * i] = sp + 1, sp += j * i, s = d;
    232 				}
    233 			}
    234 		}
    235 	}
    236 	cout << "YES" << endl;
    237 	for (i = 1; i <= n; i++) ansinv[ans[i]] = i;
    238 	for (i = 1; i <= n; i++) cout << ans[mp[ansinv[i]]] << " \n"[i == n];
    239 }
    240 int main() {
    241 	ios::sync_with_stdio(0), cin.tie(0);
    242 	int T;
    243 	cin >> T;
    244 	while (T--) get();
    245 	return 0;
    246 }
    247 ```
    248 
    249 [1787G - Colorful Tree Again](/contest/1787/problem/G)
    250 
    251 Idea & Solution: [rsj](/profile/rsj "Master rsj"), [275307894a](/profile/275307894a "Grandmaster 275307894a")
    252 
    253 **Tutorial**
    254 
    255 Tutorial is loading...
    256 
    257 **UPD:** An alternative implementation using segment tree [comment link](https://codeforces.com/blog/entry/112009?#comment-998516).
    258 
    259 [1787H - Codeforces Scoreboard](/contest/1787/problem/H)
    260 
    261 Idea & Solution: [jiangtaizhe001](/profile/jiangtaizhe001 "Candidate Master jiangtaizhe001"), [rsj](/profile/rsj "Master rsj")
    262 
    263 **Something To Say**
    264 
    265 Have to declare that we built up Problem H from zero. ;)
    266 
    267 **Tutorial**
    268 
    269 Tutorial is loading...
    270 
    271 [1787I - Treasure Hunt](/contest/1787/problem/I)
    272 
    273 Idea & Solution: [275307894a](/profile/275307894a "Grandmaster 275307894a")
    274 
    275 **Tutorial**
    276 
    277 Tutorial is loading...
    278 
    279 I'm really sorry for the unsatisfactory problems and the tough 3 hours ;)
    280 
    281 However, I still hope you can enjoy the problems after the contest. The editorial hasn't been fully checked, so feel free to comment if there're errors, typos or you have questions about them. We'll check them out tomorrow. Thanks!