1699.md (13921B)
1 Source: https://codeforces.com/blog/entry/108560 2 3 The [original blog](https://web.archive.org/web/20220705073720/https://codeforces.com/blog/entry/104088) was deleted yesterday by one of the other authors. We are very sorry about this. 4 5 # [A — The Third Three Number Problem](https://codeforces.com/contest/1699/problem/A) 6 7 Authors: [antontrygubO_o](/profile/antontrygubO_o "International Grandmaster antontrygubO_o"), [Gheal](/profile/Gheal "Master Gheal") 8 9 **Hints** 10 11 **Hint 1** 12 13 An answer exists only when $n$ is even. 14 15 **Hint 2** 16 17 $a \oplus a = 0$ 18 19 $a \oplus 0 = a$ 20 21 **Solution** 22 23 First and foremost, it can be proven that $(a \oplus b) + (b \oplus c) + (a \oplus c)$ is always even, for all possible non-negative values of $a$, $b$ and $c$. 24 25 **Proof** 26 27 Firstly, $a \oplus b$ and $a+b$ have the same parity, since $a + b = a \oplus b + 2 \cdot (a \text{&} b) $. Therefore, $(a \oplus b) + (b \oplus c) + (a \oplus c)$ has the same parity as $(a+b)+(b+c)+(a+c)=2 \cdot (a+b+c)$. 28 29 Therefore, if $n$ is even, one possible solution is $a=0$, $b=0$ and $c=\frac{n}{2}$. In this case, $(a \oplus b) + (b \oplus c) + (a \oplus c)= 0+\frac{n}{2}+\frac{n}{2}=n$. Otherwise, there are no solutions. 30 31 Time complexity per testcase: $O(1)$. 32 33 **Code (C++)** 34 35 ``` 36 #include<bits/stdc++.h> 37 38 using namespace std; 39 40 void testcase(){ 41 int n; 42 cin>>n; 43 44 if(n%2==0) 45 cout<<"0 "<<n/2<<' '<<n/2<<'\n'; 46 else 47 cout<<"-1\n"; 48 } 49 int main() 50 { 51 ios_base::sync_with_stdio(false); cin.tie(0); 52 int t; 53 cin>>t; 54 while(t--) 55 testcase(); 56 return 0; 57 } 58 ``` 59 60 **Rate Problem** 61 62 Good problem 63 64 Ok problem 65 66 Bad problem 67 68 Didn't solve it, idk 69 70 **Post Scriptum** 71 72 This is actually the third iteration of the problem, which was suggested by [antontrygubO_o](/profile/antontrygubO_o "International Grandmaster antontrygubO_o"). 73 74 The first iteration had $|a-b|+|b-c|+|a-c|=n$, and the second one had $gcd(a,b)+gcd(b,c)+gcd(a,c)=n$. 75 76 # [B — Almost Ternary Matrix](https://codeforces.com/contest/1699/problem/B) 77 78 Author: [Gheal](/profile/Gheal "Master Gheal") 79 80 **Solution** 81 82 The general construction consists of a $2 \times 2$ checkerboard with a $1$-thick border. Here is the intended solution for $n=6$ and $m=8$: 83 84  85 86 Time complexity per testcase: $O(nm)$. 87 88 **Code (C++)** 89 90 ``` 91 #include<bits/stdc++.h> 92 93 using namespace std; 94 typedef long long ll; 95 96 void testcase(){ 97 ll n,m; 98 cin>>n>>m; 99 100 for(ll i=1;i<=n;i++){ 101 for(ll j=1;j<=m;j++){ 102 cout<<((i%4<=1)!=(j%4<=1))<<" \n"[j==m]; 103 } 104 } 105 } 106 int main() 107 { 108 ios_base::sync_with_stdio(false); cin.tie(0); 109 int t; 110 cin>>t; 111 while(t--) 112 testcase(); 113 return 0; 114 } 115 ``` 116 117 **Rate Problem** 118 119 Good problem 120 121 Ok problem 122 123 Bad problem 124 125 Didn't solve it, idk 126 127 # [C — The Third Problem](https://codeforces.com/contest/1699/problem/C) 128 129 Author: [Gheal](/profile/Gheal "Master Gheal") 130 131 **Hints** 132 133 **Hint 1** 134 135 Let $p[x]$ be the position of $x$ in permutation $a$. 136 137 Since $MEX([a_{p[0]}])=1$, the only possible position of $0$ in permutation $b$ is exactly $p[0]$. 138 139 **Hint 2** 140 141 Continuing this line of thought, where can $1$ be placed in permutation $b$? 142 143 **Hint 3** 144 145 Without loss of generality, we will assume that $p[0] \lt p[1]$. 146 147 If $p[2] \lt p[0]$, then how many possible positions can $2$ have in permutation $b$? 148 149 If $p[0] \lt p[2] \lt p[1]$, then how many possible positions can $2$ have in permutation $b$? 150 151 If $p[2] \gt p[1]$, then how many possible positions can $2$ have in permutation $b$? 152 153 **Solution** 154 155 Let $p[x]$ be the position of $x$ in permutation $a$. 156 157 Since $MEX([a_{p[0]}])=1$, the only possible position of $0$ in permutation $b$ is exactly $p[0]$. 158 159 Without loss of generality, we will assume that $p[0] \lt p[1]$. For every interval $[l,r]$ ($l \le p[0] \lt p[1]\le r$), $MEX([b_l,\ldots,b_r])$ must be at least $2$. For every other interval, $MEX([b_l,\ldots,b_r])$ cannot exceed $2$. The only position for $1$ which satisfies both of these constraints is exactly $p[1]$. 160 161 Let's consider the current interval $[l,r]$ as being $[p[0],p[1]]$. 162 163 If $p[2] \in [l,r]$, we can say that, for every interval $[x,y]$ ($x \le l \lt r \le y$), $MEX([b_x,\ldots,b_y])$ must be at least $3$. Similarly, for every other interval, $MEX([b_x,\ldots,b_y])$ cannot exceed $3$. Both of these constraints are only met if $2$ occurs in permutation $b$ on some position $p \in [l,r]$. Since only $2$ positions are currently occupied in $[l,r]$, the total number of similar permutations will be multiplied by $(r-l+1)-2$. 164 165 Otherwise, $2$ can be placed in permutation $b$ only on $p[2]$. Additionally, the current interval will be "extended" to include $p[2]$, resuting in either $[p[2],r]$ or $[l,p[2]]$. 166 167 After processing $0,1, \ldots, k-2$ and $k-1$, the algorithm for processing $k$ is very similar to the one presented earlier. If $p[k] \in [l,r]$, the answer gets multiplied by $(r-l+1)-k$. Otherwise, the current interval is extended to include $p[k]$. 168 169 Time complexity per testcase: $O(n)$ 170 171 **Code (C++)** 172 173 ``` 174 #include<bits/stdc++.h> 175 176 using namespace std; 177 typedef long long ll; 178 const ll NMAX=1e5+5,MOD=1e9+7; 179 ll v[NMAX],pos[NMAX]; 180 void tc(){ 181 ll n,l,r,ans=1; 182 cin>>n; 183 for(ll i=0;i<n;i++){ 184 cin>>v[i]; 185 pos[v[i]]=i; 186 } 187 l=r=pos[0]; 188 for(ll i=1;i<n;i++){ 189 if(pos[i]<l) l=pos[i]; 190 else if(pos[i]>r) r=pos[i]; 191 else ans=ans*(r-l+1-i)%MOD; 192 } 193 cout<<ans<<'\n'; 194 } 195 int main() 196 { 197 ios_base::sync_with_stdio(false); cin.tie(0); 198 ll t; 199 cin>>t; 200 while(t--) 201 tc(); 202 return 0; 203 } 204 ``` 205 206 **Rate Problem** 207 208 Good problem 209 210 Ok problem 211 212 Bad problem 213 214 Didn't solve it, idk 215 216 # [D — Almost Triple Deletions](https://codeforces.com/contest/1699/problem/D) 217 218 Authors: [Gheal](/profile/Gheal "Master Gheal") 219 220 **Hints** 221 222 **Hint 1** 223 224 Consider the opposite problem: What is the smallest possible length of a final array? 225 226 **Hint 2** 227 228 For which arrays is the smallest possible final length equal to $0$? 229 230 **Hint 3** 231 232 Considering the second hint, it is possible to completely remove some subarrays from the array. 233 234 **Solution** 235 236 Lemma: An array $a_1,a_2,\ldots, a_n$ can be fully deleted via a sequence of operations if and only if it satisfies both of the following constraints: 237 238 * $n$ is even 239 * The maximum frequency of any element in the array is at most $\frac n2$. 240 241 **Proof** 242 243 If $n$ is odd, then any final array will also have an odd length, which can't be $0$. 244 245 An optimal strategy is to always delete one of the most frequent elements and any one of its neighbours. If the most frequent element occurs $k \gt \frac n2$ times, then the final array will have at least $n-2 \cdot (n-k)=2\cdot k - n \gt 0$ elements. Otherwise, this strategy ensures the full deletion of the array, since, after performing an operation, it is impossible for an element to occur more than $\frac {n-2}{2}$ times in the array. 246 247 Since the maximum frequency of a value for every subarray $[a_l,a_{l+1},\ldots,a_r]$ can be computed in $O(n^2)$, it is possible to precompute all subarrays which can be deleted via a sequence of operations. 248 249 Let $dp[i]$ be the maximum length of a final array consisting of $a_i$ and some subsequence from the first $i-1$ elements. Initially, $dp[i]$ is set to $1$ if the prefix $[a_1,a_2,\ldots, a_{i-1}]$ can be fully deleted. Otherwise, $dp[i]=0$. 250 251 For every pair of indices $i$ and $j$ ($1 \le j \lt i \le n, a_i=a_j$), if we can fully delete the subarray $[a_{j+1},a_{j+2},\ldots a_{i-1}]$, then we can append $a_i$ to any final array ending in $a_j$. Naturally, $dp[i]$ will be strictly greater than $dp[j]$. This gives us the following recurrence: 252 253 $dp[i]=\max_{j=1}^{i-1}(dp[j] \gt 0 \text{ and } a_i=a_j \text{ and } [a_{j+1},a_{j+2},\ldots,a_{i-1}] \text{ is deletable}) \cdot (dp[j]+1)$ 254 255 If we define a final array as a subsequence of equal elements from the array $a$, to which $a_{n+1}$ is forcefully appended, then the final answer can be written as $dp[n+1]-1$. Note that, when computing $dp[n+1]$, $a_j$ should not be compared to $a_{n+1}$. 256 257 Total time complexity per testcase: $O(n^2)$. 258 259 **Code (C++)** 260 261 ``` 262 #include<bits/stdc++.h> 263 264 using namespace std; 265 typedef long long ll; 266 const ll NMAX=5e3+5; 267 ll dp[NMAX],v[NMAX],fr[NMAX]; 268 void testcase(){ 269 ll n,ans=0; 270 cin>>n; 271 for(ll i=1;i<=n;i++){ 272 cin>>v[i]; 273 dp[i]=0; 274 } 275 for(ll i=0;i<=n;i++){ 276 277 if(i && dp[i]==0) continue; 278 ll frmax=0; 279 for(int j=1;j<=n;j++) fr[j]=0; 280 281 for(int j=i+1;j<=n;j++){ 282 if((j-i)%2 && frmax<=(j-i)/2 && (i==0 || v[i]==v[j])) 283 dp[j]=max(dp[j],dp[i]+1); 284 frmax=max(frmax,++fr[v[j]]); 285 } 286 } 287 288 ll frmax=0; 289 for(int j=1;j<=n;j++) fr[j]=0; 290 291 for(int i=n;i>=0;i--){ 292 if((n-i)%2==0 && frmax<=(n-i)/2) ans=max(ans,dp[i]); 293 frmax=max(frmax,++fr[v[i]]); 294 } 295 cout<<ans<<'\n'; 296 } 297 int main() 298 { 299 ios_base::sync_with_stdio(false); cin.tie(0); 300 int t; 301 cin>>t; 302 while(t--) 303 testcase(); 304 return 0; 305 } 306 ``` 307 308 **Rate Problem** 309 310 Good problem 311 312 Ok problem 313 314 Bad problem 315 316 Didn't solve it, idk 317 318 # [E — Three Days Grace](https://codeforces.com/contest/1699/problem/E) 319 320 Author: [tibinyte2006](/profile/tibinyte2006 "Pupil tibinyte2006") 321 322 **Solution** 323 324 We can see that in the final multiset, each number $A_i$ from the initial multiset will be assigned to a subset of values $x_1, x_2,....,x_k$ such that their product is $A_i$. Every such multiset can be created. Also let $vmax$ be the maximum value in the initial multiset. 325 326 Consider iterating through the minimum value. To get the best maximum value that has this minimum we fixed, one can use dynamic programming $dp[i][j] = $the best possible maximum if we had number $i$ and the minimum value in the product is $j$, $j$ is a divisor of $i$. This dp can be calculated in $O(vmax \cdot log^2(vmax))$ for all values. We can also process all updates when incrementing the minimum and keeping the result with a total effort of $O(vmax \cdot log^2(vmax))$. Thus we have a total time complexity of $O(vmax \cdot log^2(vmax))$. However, this ( we hope ) won't pass. 327 328 Here is a way more elegant solution ( thanks to [cadmiumky](/profile/cadmiumky "Candidate Master cadmiumky") ): 329 330 To get things straight, we observe that when we decompose a number, we just actually write it as a product of numbers. We still consider fixing the minimum value used in our multiset, call it $L$. We will further consider that we iterate $L$ from the greatest possible value (i.e. $vmax$) to $1$, and as such, we try at each iteration to calculate the minimum possible value which will appear in any decomposition as the maximum value in said decomposition. 331 332 We shall now retain for each element the minimal maximum value in a decomposition where the minimum of that decomposition is $L$, let's say for element $i$, this value will be stored in $dp[i]$. Naturally, after calculating this value for every number, we now try to tweak the calculated values as to match the fact that, after this iteration concluded, we will decrease $L$. For further simplicity, we denote $L' = L - 1$. 333 334 So, we changed the minimum value allowed. What changes now? Well, it is easy to see that any element that is not divisible by $L'$ won't be affected by this modification, as much as it is impossible to include $L'$ in any decomposition of said number. So it remains to modify the multiples of $L'$. Let's take a such number, $M$. How can we modify $dp[M]$? Well, we can include $L'$ in the decomposition as many times as we want, and then when we decide to stop including it, we remain with a number which needs to be further decomposed. The attributed maximum of this value should already be calculated, so we can consider it as a new candidate for the update of $dp[M]$. This idea could be implemented simpler by going through multiples of $L'$, and for an element, updating $dp[i]$ with $dp[i / L']$ (by taking the minimum of either) 335 336 We now need for each iteration to keep track of the attributed maximums of each element that actually appears in our initial list. This can be done by keeping a frequency of all these elements, and after all updates, taking the (already known) maximum of the previous iteration and decreasing it until we find another element that actually appears in our set (this can be verified by simply checking the frequency). This is correct, as much as all the values gradually decrease as $L$ decreases, so their maximum would have to decrease as well. 337 338 Final time complexity: $O(vmax * log(vmax))$ 339 340 **Code (C++)** 341 342 ``` 343 #include <bits/stdc++.h> 344 345 using namespace std; 346 347 using ll = long long; 348 349 const int nmax = 5e6 + 5; 350 int appear[nmax]; 351 int mxval[nmax]; 352 int toggle[nmax]; 353 354 int main() 355 { 356 cin.tie(nullptr)->sync_with_stdio(false); 357 int t; 358 cin >> t; 359 while (t--) 360 { 361 int n, m, mn = nmax, mx = 0; 362 cin >> n >> m; 363 for (int i = 0; i <= m; ++i) 364 { 365 appear[i] = toggle[i] = mxval[i] = 0; 366 } 367 for (int i = 0, x; i < n; i++) 368 { 369 cin >> x; 370 appear[x] = 1; 371 toggle[x] = 1; 372 mn = min(mn, x); 373 mx = max(mx, x); 374 } 375 for (int i = 0; i <= mx; i++) 376 { 377 mxval[i] = i; 378 } 379 int ptr = mx, smax = mx - mn; 380 for (int i = mx; i >= 1; i--) 381 { 382 for (ll j = (ll)i * i; j <= mx; j += i) 383 { 384 if (appear[j]) 385 toggle[mxval[j]]--; 386 mxval[j] = min(mxval[j], mxval[j / i]); 387 if (appear[j]) 388 toggle[mxval[j]]++; 389 } 390 while (toggle[ptr] == 0) 391 ptr--; 392 if (i <= mn) 393 smax = min(smax, ptr - i); 394 } 395 cout << smax << '\n'; 396 } 397 } 398 ``` 399 400 **Rate Problem** 401 402 Good problem 403 404 Ok problem 405 406 Bad problem 407 408 Didn't solve it, idk