codeforces-scrape

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

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 ![ ](/predownloaded/d1/da/d1da1a74fffa460d52b64d7e30c78eb597277612.png)
     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