codeforces-scrape

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

1815.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 ![ ](/predownloaded/05/74/0574f09a909e85ed02c545a6b11f9c714deefa1e.png)
    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 ```