1816.md (27234B)
1 Source: https://codeforces.com/blog/entry/114899 2 3 Thanks for participating, and happy Easter! 4 5 ### [1816A - Ян навещает Мэри](/contest/1816/problem/A "Codeforces Round 865 (Div. 2)") 6 7 **Editorial** 8 9 Let us show that Ian can get to Mary within two moves. Indeed, consider $(x_1,y_1)$ and $(x_2,y_2)$ where $x_2-x_1=1$, since the value of the $x$-coordinates of a point lying on the segment joining $(x_1,y_1)$ and $(x_2,y_2)$, and is not at the endpoints, is strictly between $x_1$ and $x_2$, but there are no integers strictly between $x_1$ and $x_2$, the point must not be a lattice point. Similarly, no lattice points lie on the segment joining $(x_1,y_1)$ and $(x_2,y_2)$ with $y_2-y_1=1$ except for the endpoints. Therefore, Ian can jump from $(0,0)$ to $(x-1,1)$ to $(x,y)$. 10 11 **Implementation** 12 13 ``` 14 #include<bits/stdc++.h> 15 using namespace std; 16 17 void solve(){ 18 int a,b; 19 cin >> a >> b; 20 cout << 2 << "\n" << a-1 << ' ' << 1 << "\n" << a << ' ' << b << "\n"; 21 } 22 23 int main(){ 24 int t; 25 cin >> t; 26 while(t--){ 27 solve(); 28 } 29 } 30 ``` 31 32 **Remark** 33 34 Originally, the problem asks you for the minimal amount of steps, which requires gcd. Since it would be too hard, we had a quite last-minute change to the current statement. 35 36 ### [1816B - Реконструкция таблицы](/contest/1816/problem/B "Codeforces Round 865 (Div. 2)") 37 38 **Hint** 39 40 Consider the parity (odd/even) of $i+j$. What do you observe? 41 42 **Editorial** 43 44 Observe that $a_{i,j}$ will be added if $(i+j)$ is even, and will be subtracted otherwise. This forms a checkered pattern. 45 46 Obviously, it is optimal for all values that will be added to be strictly larger than all values that will be subtracted. Also, the difference between the value of adjacent grids should be *almost* equal (by some definition of *almost*). 47 48 We construct array $a$ as follows: 49 50 * $a_{1,1} = 2n-1$ and $a_{2,n} = 2n$ 51 * For $2 \leq i \leq n$ and $i$ is even, $a_{1,i} = i$ and $a_{2,i-1} = i - 1$ 52 * For $2 \leq i \leq n$ and $i$ is odd, $a_{1,i} = n + i - 1$ and $a_{2,i-1} = n + (i - 1) - 1$ 53 54 For example, when $n=10$, the output will be 55 56 ``` 57 19 2 12 4 14 6 16 8 18 10 58 1 11 3 13 5 15 7 17 9 20 59 ``` 60 61 **Insights on how to find the construction** 62 63 (This is a very informal proof. See "Proof" below for a formal proof.) 64 65 First of all, due to the checkered pattern, $a_{1,1}, a_{2,2}, a_{1,3}, \cdots, a_{2,n}$ should be filled with $n+1, n+2, n+3, \cdots, 2n$, and $a_{2,1}, a_{1,2}, a_{2,3}, \cdots, a_{1,n}$ should be filled with $1, 2, 3, \cdots, n$. In particular, $a_{1,1}$ and $a_{2,n}$ should be $2n-1$ and $2n$. 66 67 Next, as we are trying to maximise the minimum, the difference between paths shouldn't be large (since the minimum path will be smaller if the difference is larger). Notice that a path consists of a prefix of $a_1$ and a suffix of $a_2$, and the difference between $2$ adjacent paths is $\pm (a_{1,k} - a_{2,k-1})$ (depending on the parity of $k$). It is optimal for the difference to be as small as possible (which is $1$). 68 69 Finally, it is optimal that $a_{1,k} - a_{2,k-1}$ stays constant in the whole array. If they are different, the difference between $2$ paths (not adjacent) will be larger than $1$, which is suboptimal. 70 71 **Proof** 72 73 Consider the cost of the top right path and bottom left path. 74 75 The cost of the top right path is $a_{1,1} - a_{1,2} + a_{1,3} - \cdots - a_{1,n} + a_{2,n}$. 76 77 The cost of the bottom right path is $a_{1,1} - a_{2,1} + a_{2,2} - a_{2,3} + ... + a_{2,n}$. 78 79 Summing both values, we get 80 81 $a_{1,1} + a_{2,n} + ((a_{1,1} - a_{1,2} + a_{1,3} - a_{1,4} + ... - a_{1,n}) + (-a_{2,1} + a_{2,2} - a_{2,3} + ... + a_{2,n}))$ 82 83 which is equal to 84 85 $a_{1,1} + a_{2,n} + ((a_{1,1} + a_{2,2} + a_{1,3} + a_{2,4} + \cdots + a_{2,n}) - (a_{2,1} + a_{1,2} + a_{2,3} + a_{1,4} + \cdots + a_{1,n}))$ 86 87 This value attains maximum when $a_{1,1} = 2n$, $a_{2,n} = 2n-1$, $(a_{1,1} + a_{2,2} + a_{1,3} + a_{2,4} + \cdots + a_{2,n}) = ((n+1) + (n+2) + (n+3) + \cdots + 2n)$ and $(a_{2,1} + a_{1,2} + a_{2,3} + a_{1,4} + \cdots + a_{1,n}) = (1 + 2 + 3 + \cdots + n)$, which is $(2n + (2n - 1) + (\frac{(n)((n+1)+2n)}{2}) - (\frac{(n)(1+n)}{2})) = (n^2 + 4n - 1)$. 88 89 Therefore, the upper bound for the maximum cost is $\lfloor \frac{n^2 + 4n - 1}{2} \rfloor = \frac{1}{2}n^2 + 2n - 1$. We will now show that the construction above meets the upper bound. 90 91 Let $P_k$ be the cost of the path $a_{1,1}, a_{1,2}, a_{1,3}, \cdots, a_{1,k}, a_{2,k}, a_{2,k+1}, \cdots, a_{2,n}$. 92 93 Observe that $P_k - P_{k-1} = (-1)^k(a_{1,k} - a_{2,k-1}) = (-1)^k$, as the paths differ by exactly $2$ grids and $a_{1,k} - a_{2,k-1} = 1$ (from the above construction). 94 95 Calculating $P$, 96 97 $P_1 = (2n - 1) - 2 + (n + 2) - 4 + (n + 4) - \cdots - (n - 2) + 2n = (2n - 1) + (n)(\frac{n}{2} - 1) - n + 2n = \frac{1}{2}n^2 + 2n - 1$ 98 99 $P_2 = P_1 + (-1)^2 = \frac{1}{2}n^2 + 2n$ 100 101 $P_3 = P_2 + (-1)^3 = \frac{1}{2}n^2 + 2n - 1$ 102 103 $\cdots$ 104 105 Therefore, $min(P) = \frac{1}{2}n^2 + 2n - 1$, which achieves the upper bound. 106 107 **Implementation** 108 109 ``` 110 #include <bits/stdc++.h> 111 using namespace std; 112 int main() { 113 int t; 114 cin >> t; 115 while (t--) { 116 int n; 117 cin >> n; 118 119 int ans[3][n + 1]; 120 121 ans[1][1] = 2 * n - 1; 122 ans[2][n] = 2 * n; 123 124 for (int i = 2; i <= n; i++) { 125 if (i % 2 == 0) { 126 ans[1][i] = i; 127 ans[2][i - 1] = i - 1; 128 } else { 129 ans[1][i] = n + (i - 1); 130 ans[2][i - 1] = n + (i - 1) - 1; 131 } 132 } 133 134 for (int i = 1; i <= 2; i++) { 135 for (int j = 1; j <= n; j++) { 136 cout << ans[i][j] << (j == n ? '\n' : ' '); 137 } 138 } 139 } 140 } 141 ``` 142 143 **Question** 144 145 Can you find a construction for a $n \times n$ grid (and give a formal proof)? (We don't have a solution) 146 147 ### [1815A - Ян и сортировка массива](/contest/1815/problem/A "Codeforces Round 865 (Div. 1)") 148 149 **Hint 1** 150 151 Consider difference array $[a_2-a_1,a_3-a_2,...,a_n-a_{n-1}]$. If the original array is non-decreasing, what properties does the difference array have? 152 153 **Hint 2** 154 155 Operations to the original array correspond to what operations in the difference array? 156 157 **Editorial** 158 159 We consider the difference array $b_i=a_{i+1}-a_i$ ($1\le i\le n-1$). Then the original array is non-decreasing if and only if all elements of the difference array is non-negative. We can see that either $b_i$ is increased by $1$ and $b_{i+2}$ is decreased by $1$ or vice versa for $1\le i\le n-3$, $b_2$ is increased or decreased by $1$ or $b_{n-2}$ is increased or decreased by $1$. 160 161 If $n$ is odd, then $n-2$ is odd. What we can do is to increase $b_2$ and $b_{n-2}$ enough number of times, and then do $b_i$ increase by $1$ and $b_{i+2}$ decrease by $1$ or vice versa enough times to distribute the values to other elements of $b$. Doing this, we can make all of the elements of $b$ non-negative, which is what we want. So we output 'YES' no matter what for odd $n$. 162 163 For even $n$, $n-2$ is even. So by increasing $b_2$ and $b_{n-2}$ enough number of times, then distributing, we can only ensure that the elements of $b$ with even indices are non-negative. Since the only operation that affects odd indices is increasing $b_i$ by $1$ and decreasing $b_{i+2}$ by $1$ or vice versa, we can see that the sum of the elements of $b$ with odd indices will not change. If the sum of the elements of $b$ with odd indices is at least $0$, we can distribute the values such that in the end, all of them are non-negative, so we should output 'YES'. But if the sum of elements of $b$ with odd indices is negative, there must exist a negative $b_i$ in the end, and we should output 'NO'. 164 165 **Implementation** 166 167 ``` 168 #include<bits/stdc++.h> 169 using namespace std; 170 171 void solve(){ 172 int n; 173 cin >> n; 174 int arr[n]; 175 long long int altsum=0; 176 for(int i=0;i<n;i++){ 177 cin >> arr[i]; 178 if(i%2==0){ 179 altsum-=arr[i]; 180 } 181 else{ 182 altsum+=arr[i]; 183 } 184 } 185 if(n%2==1||altsum>=0){ 186 cout << "YES\n"; 187 } 188 else{ 189 cout << "NO\n"; 190 } 191 return; 192 } 193 194 int main(){ 195 ios_base::sync_with_stdio(false); 196 cin.tie(NULL); cout.tie(NULL); 197 int t; 198 cin >> t; 199 while(t--){ 200 solve(); 201 } 202 } 203 ``` 204 205 ### [1815B - Граф сумм](/contest/1815/problem/B "Codeforces Round 865 (Div. 1)") 206 207 **Hint 1** 208 209 Consider using a type 1 operation on $x=n+1$ and $x=n+2$. What do you notice? 210 211 **Hint 2** 212 213 The resulting graph, after performing type 1 operations according to hint 1, will be a chain (e.g. when $n=6$, it should look like $1 - 6 - 2 - 5 - 3 - 4$). Now, try to figure out a position $k$ such that node $p_k$ is one of the endpoints of the chain. Once you figure that out, how can you make use of this to solve the full problem? 214 215 **Editorial** 216 217 There are many ways to solve this problem. My original solution is rather difficult to implement correctly, and a bit complicated. During round testing, tester [rsj](/profile/rsj "Мастер rsj") found an alternative solution, which is, in my opinion, one that's a lot easier to understand and implement. 218 219 Firstly, use a type 1 operation on $x=n+1$ and $x=n+2$ (or you can do $x=n$ and $x=n+1$). Then, the graph should look like a chain (e.g. when $n=6$, it should look like $1 - 6 - 2 - 5 - 3 - 4$). Note that there are actually two edges between each pair of directly connected nodes, but it is irrelevant to the task. 220 221 Next, use a type 2 query on all pairs of $(1,i)$ where $2 \le i \le n$. Take the maximum of the query results. Let $k$ be one of the values such that the query result of $(1,k)$ is maximum among all $(1,i)$. It is easy to see that, node $p_k$ is one of the endpoints of the chain. 222 223 Afterwards, use a type 2 query on all pairs of $(k,i)$ where $1 \le i \le n$ and $i \ne k$. Since node $p_k$ is an endpoint of the chain, all the query results are distinct and you can recover the exact node that each query result corresponds to. 224 225 A problem arises that it is unclear about which endpoint node $p_k$ actually is. But this issue can be solved easily: since the problem allows outputting two permutations that can be $p$, just try both endpoints and output the corresponding permutations. 226 227 In total, $2$ type 1 operations and $2n-2$ type 2 operations are used, which sums up to $2n$ operations. As stated in the sample description, you don't even need any operations when $n=2$. It is also easy to see that the actual number of operations required is $2n-1$ since there is a pair of duplicate type 2 operations, but we allow duplicating the operation anyway. 228 229 **Implementation** 230 231 ``` 232 #include <bits/stdc++.h> 233 using namespace std; 234 void solve(int tc) { 235 int n; cin >> n; 236 cout << "+ " << n+1 << endl; 237 cout << "+ " << n+2 << endl; 238 int l = 1, r = n; 239 int ord[n+1]; 240 for(int i=1; i<=n; i++) { 241 if(i & 1) ord[i] = l++; 242 else ord[i] = r--; 243 } 244 int dist1[n+1]; 245 dist1[1] = 0; 246 int ma = 0, id; 247 for(int i=2; i<=n; i++) { 248 cout << "? 1 " << i << endl; 249 cin >> dist1[i]; 250 if(dist1[i] > ma) { 251 ma = dist1[i]; 252 id= i; 253 } 254 } 255 int p[n+1], q[n+1]; 256 p[id] = ord[1]; 257 q[id] = ord[n]; 258 for(int i=1; i<=n; i++) { 259 if(i != id) { 260 cout << "? " << id << " " << i << endl; 261 int x; 262 cin >> x; 263 p[i] = ord[x+1]; 264 q[i] = ord[n-x]; 265 } 266 } 267 cout << "!"; 268 for(int i=1; i<=n; i++) cout << " " << p[i]; 269 for(int i=1; i<=n; i++) cout << " " << q[i]; 270 cout << endl; 271 272 } 273 int32_t main() { 274 int t = 1; cin >> t; 275 for(int i=1; i<=t; i++) solve(i); 276 } 277 ``` 278 279 **Harder version** 280 281 Try to solve the problem using at most $n + \left \lfloor \frac{n}{2} \right \rfloor + 2$ queries. 282 283 **Solution to harder version** 284 285 Refer to this [comment](https://codeforces.com/blog/entry/114847?#comment-1021812). Thanks to [-1e11](/profile/-1e11 "Мастер -1e11") and [FatihSolak](/profile/FatihSolak "Мастер FatihSolak") for the solution. (To pass this problem using this solution, optimizations for $n=2$ are needed, as mentioned in the editorial section.) 286 287 Another way of solving the harder version provided by [sysia](/profile/sysia "Кандидат в мастера sysia"): refer to this [comment](https://codeforces.com/blog/entry/114899?#comment-1022221). 288 289 ### [1815C - Между](/contest/1815/problem/C "Codeforces Round 865 (Div. 1)") 290 291 **Editorial** 292 293 Construct a graph with $n$ vertices and add a directed edge $a \rightarrow b$ if between every two $a$ there must be a $b$. 294 295 Let $v_a$ be the number of occurrences of $a$. The key observation is that if $a \rightarrow b$, then $v_{a} \leq v_{b} + 1$. 296 297 Suppose $a_k \rightarrow a_{k-1} \rightarrow \cdots a_1$ is a directed path, where $a_1 = 1$. Then since $v_1 = 1$, we must have $v_{a_i} \leq i$. In other words, $v_s \leq d_s $. where $d_s$ is one plus the length of the shortest directed path from $s$ to $1$. 298 299 Therefore, the total array length does not exceed $\sum_{i=1}^{n} d_i$. We claim that we can achieve this. 300 301 It is easy to calculate the $d_s$ by a BFS. Let $T_i$ consists of vertices $x$ such that $v_x = s$. Let $M$ the largest value of $d_i$ among all $i \in {1,2\cdots n}$. Consider 302 303 $ [T_M] , [T_{M-1}][T_M] , [T_{M-2}][T_{M-1}][T_{M}],\cdots [T_1][T_2][T_3]\cdots [T_m]$ 304 305 where for each $i$, vertices in various occurrences of $T_i$ must be arranged in the same order. 306 307 It is easy to check that this construction satisfies all the constraints and achieve the upper bound $\sum_{i=1}^{n} d_i$. Thus, this output is correct. 308 309 The sequence can be arbitrarily long if and only if there is some $v$ that does not have a path directed to $1$. To see this, let $S$ be the set of vertices that do not have path directed to $1$, then the following construction gives an arbitrarily long output that satisfy all constraints: 310 311 $ 1 [S][S][S]\cdots $ 312 313 **Implementation** 314 315 ``` 316 #include<bits/stdc++.h> 317 using namespace std; 318 319 void solve(){ 320 int n,m; 321 cin >> n >> m; 322 vector <int> adj[n+1]; 323 int occ[n+1]; 324 occ[1]=1; 325 for(int i=0;i<m;i++){ 326 int x,y; 327 cin >> x >> y; 328 adj[y].push_back(x); 329 } 330 for(int i=2;i<=n;i++){ 331 occ[i]=0; 332 } 333 queue <int> bfs; 334 bfs.push(1); 335 while(bfs.size()>0){ 336 int f=bfs.front(); 337 bfs.pop(); 338 for(int i=0;i<adj[f].size();i++){ 339 if(occ[adj[f][i]]==0){ 340 occ[adj[f][i]]=occ[f]+1; 341 bfs.push(adj[f][i]); 342 } 343 } 344 } 345 vector <int> v[n+1]; 346 int ans=0; 347 for(int i=1;i<=n;i++){ 348 if(occ[i]==0){ 349 cout << "INFINITE\n"; 350 return; 351 } 352 v[occ[i]].push_back(i); 353 ans+=occ[i]; 354 } 355 cout << "FINITE\n" << ans << endl; 356 for(int i=n;i>=1;i--){ 357 for(int j=n;j>=i;j--){ 358 if(i%2!=j%2){ 359 continue; 360 } 361 for(int k=0;k<v[j].size();k++){ 362 cout << v[j][k] << ' '; 363 } 364 } 365 } 366 for(int i=2;i<=n;i++){ 367 for(int j=n;j>=i;j--){ 368 if(i%2!=j%2){ 369 continue; 370 } 371 for(int k=0;k<v[j].size();k++){ 372 cout << v[j][k] << ' '; 373 } 374 } 375 } 376 cout << endl; 377 return; 378 } 379 380 int main(){ 381 int t; 382 cin >> t; 383 while(t--){ 384 solve(); 385 } 386 } 387 ``` 388 389 ### [1815D - Подсчёт XOR](/contest/1815/problem/D "Codeforces Round 865 (Div. 1)") 390 391 **Hint 1** 392 393 The cases when $m=1$ and $m\ge3$ are relatively much easier than when $m=2$. 394 395 **Hint 2** 396 397 When $m=2$, perform an $O(\log n)$ DP on answer. Notice we have to DP another thing as well. What is it? 398 399 **Editorial** 400 401 If $m=1$, it is clear that we only can have $a_1=n$ so the answer is $n$. 402 403 If $m\ge3$, $\left[x,\frac{n-x}2,\frac{n-x}2,0,0,...\right]$ gives a xor of $x$, so all $x$ with the same parity as $n$ and at most $n$ can be achieved. Notice xor and sum are identical in terms of parity, and $a\oplus b\le a+b$. So these restrict that only values of $x$ that has same parity with $n$ and is at most $n$ is possible as a result of the xor. Therefore, we can use $O(1)$ to calculate the sum of all non-negative integers at most $n$ and have same parity as $n$. 404 405 It remains to handle the case when $m=2$. We create the functions $f(n)$ and $g(n)$, where $f(n)$ is the sum of all possible values of the xor and $g(n)$ counts the number of all possible values of the xor. We then consider the following: 406 407 If $n$ is odd, then one of $a_1,a_2$ is even and the other is odd. WLOG assume $a_1$ is even and $a_2$ is odd. Then we let $a_1'=\frac{a_1}2$ and $a_2'=\frac{a_2-1}2$. We can see that $a_1'+a_2'=\frac{n-1}2$ and $a_1\oplus a_2=2(a_1'\oplus a_2')+1$. Hence we know that $g(n)=g\left(\frac{n-1}2\right)$, and $f(n)=2f\left(\frac{n-1}2\right)+g\left(\frac{n-1}2\right)$. 408 409 If $n$ is even, there are two cases. If $a_1$ and $a_2$ are both even, we let $a_1'=\frac{a_1}2$ and $a_2'=\frac{a_2}2$. We can see that $a_1'+a_2'=\frac{n}2$ and $a_1\oplus a_2=2(a_1'\oplus a_2')$. If $a_1$ and $a_2$ are both odd, we let $a_1'=\frac{a_1-1}2$ and $a_2'=\frac{a_2-1}2$. We can see that $a_1'+a_2'=\frac{n}2-1$ and $a_1\oplus a_2=2(a_1'\oplus a_2')$. Hence we know that $f(n)=2f\left(\frac{n}2\right)+2f\left(\frac{n}2-1\right)$, and $g(n)=g\left(\frac{n}2\right)+g\left(\frac{n}2-1\right)$. 410 411 So we can simply DP. It can be seen that the time complexity is $O(\log n)$ per test case, so we are done. 412 413 **Implementation** 414 415 ``` 416 #include<bits/stdc++.h> 417 using namespace std; 418 419 unordered_map <long long int,long long int> npos,spos; 420 421 const int MOD=998244353; 422 423 long long int solve(long long int n){ 424 if(npos[n]!=0){ 425 return spos[n]; 426 } 427 if(n%2==1){ 428 solve(n/2); 429 npos[n]=npos[n/2]; 430 spos[n]=spos[n/2]*2+npos[n/2]; 431 spos[n]%=MOD; 432 } 433 else{ 434 solve(n/2); solve(n/2-1); 435 npos[n]=npos[n/2]+npos[n/2-1]; 436 spos[n]=(spos[n/2]+spos[n/2-1])*2; 437 spos[n]%=MOD; 438 } 439 return spos[n]; 440 } 441 442 int main(){ 443 ios_base::sync_with_stdio(false); 444 cin.tie(NULL); cout.tie(NULL); 445 npos[0]=1; 446 spos[0]=0; 447 int t; 448 cin >> t; 449 while(t--){ 450 long long int n,m; 451 cin >> n >> m; 452 if(m==2){ 453 cout << solve(n) << endl; 454 } 455 else if(m==1){ 456 cout << n%MOD << endl; 457 } 458 else if(n%2==0){ 459 cout << (((n/2)%MOD)*((n/2+1)%MOD))%MOD << endl; 460 } 461 else{ 462 cout << (((n/2+1)%MOD)*((n/2+1)%MOD))%MOD << endl; 463 } 464 } 465 } 466 ``` 467 468 ### [1815E - Bosco and частица](/contest/1815/problem/E "Codeforces Round 865 (Div. 1)") 469 470 **Hint 1** 471 472 If the oscillator string is periodic, what should we do? 473 474 **Hint 2** 475 476 Use the case when $n=1$ to help you calculate the answer. 477 478 **Observation 1** 479 480 Observe that whole process is periodic. 481 482 Note that the process is reversible. If you are in some state $s$, consisting of position of the particle and the current state position of each oscillator, you can decide the next state and the previous state. This implies the state transition graph is a permutation, so it decomposes into cycles. 483 484 **Editorial** 485 486 Firstly, we can easily see that removing cycles for the oscillator strings does not affect the answer. To help us calculating the answer easier, we have to remove cycle. You can remove cycle using any fast enough string algorithm such as KMP. 487 488 It is not difficult to see that if all strings are non-periodic, then being periodic with respect to the particle position $x$ is the same as being periodic with respect to both $x$ and all oscillator states. 489 490 Let $a_i$ be the number of times the particle hits oscillator $i$ when moving downwards and $b_i$ be the number of times the particle hits oscillator i when moving upwards in each cycle. 491 492 For each oscillator $i$, consider the case when $n=1$ and oscillator $i$ is the only oscillator. Let $a'_i$ be the number of times the particle hits oscillator $i$ when moving downwards and $b'_i$ be the number of times the particle hits the oscillator $i$ when moving upwards in each cycle. 493 494 Then we must have $a_i=ka'_i$ and $b_i=kb'_i$ for some positive integer k. Also, we must have $a_i=b_{i-1}$ as the number of times the particle goes from oscillator $i-1$ to oscillator $i$ is same as the number of times the particle goes from oscillator $i$ to oscillator $i-1$. It can be shown that the smallest integers $a_i$ and $b_i$ satisfying the above constraints must be the period. 495 496 We can calculate the the smallest such integers, by factoring each $k$ and maintain the primes. In other words, we can separately consider the $p$-adic valuation of the $a'_i$'s and $b'_i$'s to get the $p$-adic valuation of $a_i$'s and $b_i$'s for each prime. Below is a visualisation: 497 498  499 500 Notice the answer is $2(a_1+a_2+...+a_n+b_n)$, which can be easily calculated. So we are done. 501 502 **Implementation** 503 504 ``` 505 #include<bits/stdc++.h> 506 using namespace std; 507 508 vector <int> prime; 509 bool p[1000001]; 510 511 const long long int mod=998244353; 512 513 void init(){ 514 p[1]=0; 515 for(int i=2;i<=1000000;i++){ 516 p[i]=1; 517 } 518 for(int i=2;i<=1000000;i++){ 519 if(p[i]){ 520 prime.push_back(i); 521 } 522 for(int j=i;j<=1000000;j+=i){ 523 p[j]=0; 524 } 525 } 526 return; 527 } 528 529 long long int bigmod(long long int n,long long int k){ 530 long long int pown=n,ans=1; 531 while(k>0){ 532 if(k%2){ 533 ans*=pown; 534 ans%=mod; 535 } 536 pown*=pown; 537 pown%=mod; 538 k/=2; 539 } 540 return ans; 541 } 542 543 int vp(long long int n,int p){ 544 int ans=0; 545 if(n==0){ 546 return 10000000; 547 } 548 while(n%p==0){ 549 n/=p; 550 ans++; 551 } 552 return ans; 553 } 554 555 string rpc(string str){ 556 int i=0; 557 int len=str.length(); 558 int j=-1; 559 int nextval[len]; 560 nextval[i]=-1; 561 while (i<len){ 562 if (j==-1||str[i]==str[j]){ 563 i++; 564 j++; 565 nextval[i]=j; 566 } 567 else 568 j=nextval[j]; 569 } 570 if ((len)%(len-nextval[len])==0) return str.substr(0,len-nextval[len]); 571 else return str; 572 } 573 574 int main(){ 575 init(); 576 int n; 577 cin >> n; 578 int lim=n; 579 pair<int,int> arr[n]; 580 for(int i=0;i<n;i++){ 581 string s; 582 cin >> s; 583 s=rpc(s); 584 int x=0,y=0,ptr=0; 585 bool b=true; 586 do{ 587 if(b){ 588 x++; 589 } 590 else{ 591 y++; 592 } 593 if(s[ptr]=='0'){ 594 b=1-b; 595 } 596 ptr++; 597 ptr%=s.length(); 598 }while(!b||(ptr!=0)); 599 arr[i]={x,y}; 600 if(y==0&&lim==n){ 601 lim=i; 602 } 603 } 604 long long int times[n+1]; 605 for(int i=0;i<=n;i++){ 606 times[i]=1; 607 } 608 for(int i=0;i<prime.size();i++){ 609 int p=prime[i],curl=0,curr=0,difp[lim+1]={0}; 610 for(int j=1;j<=lim;j++){ 611 int l=vp(arr[j-1].first,p); 612 int r=vp(arr[j-1].second,p); 613 if(curr<l){ 614 curl+=(l-curr); 615 curr=r; 616 } 617 else{ 618 curr+=(r-l); 619 } 620 difp[j]=r-l; 621 } 622 int cur=curl; 623 for(int j=0;j<=lim;j++){ 624 cur+=difp[j]; 625 times[j]*=bigmod(p,cur); 626 times[j]%=mod; 627 } 628 } 629 long long int ans=0; 630 for(int i=0;i<=lim;i++){ 631 ans+=times[i]; 632 ans%=mod; 633 } 634 cout << (2*ans)%mod << endl; 635 } 636 ``` 637 638 ### [1815F - OH NO1 (-2-3-4)](/contest/1815/problem/F "Codeforces Round 865 (Div. 1)") 639 640 **Key Idea 1** 641 642 Go through from vertex $1$ through $n$ and decided their final weights in this order. When deciding the weights for $v$ , make sure it is different from $w$ if $w \lt v$ and $v$ is adjacent to $w$. Ignore vertices $x$ where $x$ is adjacent to $v$ but have $x \gt v$. 643 644 **Key Idea 2** 645 646 If there are at least $d+1$ options to take from, and $d$ of them are not available, then there is still some option to take. 647 648 **Editorial** 649 650 Let's try to decide the final weights of $1$ through $n$ in this order. For a triangle $a \lt b \lt c$, we call $a$ the first vertex, $b$ the second vertex, $c$ the third vertex. Consider each triangle individually, if we can achieve the following task then we are done: By only adjusting edges of this triangle: 651 652 * There is at least one option for the first vertex 653 * After fixing a particular option for the first vertex, there are at least two options for the the second vertex 654 * After fixing particular options for the first two vertices, there are at least three options for the third vertex 655 656 To see this is enough: Suppose a vertex $v$ is in $A$ triangles as the first vertex, $B$ triangles as the second vertex, and $C$ triangles as the third vertex. It is not difficult to see $v$ have exactly $B + 2 \times C$ neighbours that are of smaller index, and there are at least $B+ 2\times C+ 1$ options. 657 658 Finally, by using the following specific edge weights, the goal can be achieved: 659 660 * $1,4,4$ gives weights $5,5,8$ 661 * $2,3,3$ gives weights $5,5,6$ 662 * $3,2,2$ gives weights $5,5,4$ 663 * $1,4,3$ gives weights $5,4,7$ 664 * $2,3,2$ gives weights $5,4,5$ 665 * $3,2,1$ gives weights $5,4,3$ 666 667 These numbers aren't exactly just completely random. You can see that they are composed of two components: A $(+1,-1,-1)$ part and a $(0,0,-1)$ part. Upto two copies of the first option and upto one copy of the second option have been used. 668 669 There is also a simple solution in this specific case where $G$ consists of triangles and use only weights 1,2,3. 670 671 This is a special case of 1-2-3 conjecture, which states that the above statement holds for arbitrary graph and using only the weights 1,2,3 (and no 4). Recently (March 2023) it has a claimed proof. The claimed algorithm is far from a linear time algorithm however. 672 673 **Implementation (Tester: gamegame)** 674 675 ``` 676 #include<bits/stdc++.h> 677 using namespace std; 678 typedef long long ll; 679 #define fi first 680 #define se second 681 const ll mod=998244353; 682 const int N=2e6+1; 683 ll n,m; 684 vector<pair<int,int> >adj[N]; 685 array<int,3>e[N]; 686 array<int,3>f[N]; 687 ll a[N],b[N]; 688 pair<int,int>vis[10000005]; 689 void solve(){ 690 cin >> n >> m; 691 for(int i=1; i<=n ;i++){ 692 adj[i].clear(); 693 } 694 for(int i=1; i<=n ;i++){ 695 cin >> a[i]; 696 } 697 for(int i=1; i<=m ;i++){ 698 for(int j=0; j<3 ;j++){ 699 cin >> e[i][j]; 700 adj[e[i][j]].push_back({i,j}); 701 } 702 f[i][0]=3; 703 f[i][1]=1; 704 f[i][2]=1; 705 a[e[i][0]]+=f[i][0]+f[i][2]; 706 a[e[i][1]]+=f[i][1]+f[i][0]; 707 a[e[i][2]]+=f[i][2]+f[i][1]; 708 } 709 for(int i=1; i<=n ;i++){ 710 for(auto c:adj[i]){ 711 for(int d=0; d<c.se ;d++){ 712 vis[a[e[c.fi][d]]]={c.fi,d}; 713 } 714 } 715 while(vis[a[i]].fi!=0){ 716 int ed=vis[a[i]].fi; 717 if(i==e[ed][1]){ 718 a[i]++; 719 a[e[ed][2]]++; 720 f[ed][1]++; 721 } 722 else{ 723 a[i]+=2; 724 725 f[ed][0]--; 726 f[ed][1]++; 727 f[ed][2]++; 728 } 729 } 730 731 for(auto c:adj[i]){ 732 for(int d=0; d<c.se ;d++){ 733 vis[a[e[c.fi][d]]]={0,0}; 734 } 735 } 736 } 737 for(int i=1; i<=m ;i++){ 738 cout << f[i][0] << ' ' << f[i][1] << ' ' << f[i][2] << '\n'; 739 } 740 } 741 int main(){ 742 ios::sync_with_stdio(false);cin.tie(0); 743 int t;cin >> t;while(t--) solve(); 744 } 745 ```