codeforces-scrape

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

1934.md (18990B)


      1 Source: https://codeforces.com/blog/entry/126423
      2 
      3 [1934A — Too Min Too Max](https://codeforces.com/contest/1934/problem/A)
      4 
      5 **Solution**
      6 
      7 **Hint 1**
      8 
      9 What will be answer if there were only $4$ elements in the array?
     10 
     11 **Solution**
     12 
     13 Suppose if there were only $4$ elements in the array. Let them be $a \leq b \leq c \leq d$. Then the answer will be maximum of the three cases which are listed as follows:-
     14 
     15 $|a-b|+|b-c|+|c-d|+|d-a| = 2*d - 2*a$ $|a-b|+|b-d|+|d-c|+|c-a| = 2*d-2*a$ $|a-c|+|c-b|+|b-d|+|d-a| = 2*(d+c)-2*(a+b)$
     16 
     17 so clearly $2*(d+c)-2*(a+b)$ is the maximum.
     18 
     19 So, to maximize this we can set $d$, $c$ as large as possible and $a$, $b$ as small as possible i.e. $d=a_n$, $c=a_{n-1}$, $b=a_{2}$ and $a=a_{1}$ where $a_i$ means $i^{th}$ element in sorted order of given array.
     20 
     21 **Code (C++)**
     22 
     23 ```
     24 #include <bits/stdc++.h>
     25 
     26 using namespace std;
     27 
     28 int main()
     29 {
     30     ios::sync_with_stdio(false);
     31     cin.tie(nullptr);
     32     int testcases;
     33     cin >> testcases;
     34     for (int t = 1; t <= testcases; t++)
     35     {
     36         int n;
     37         cin >> n;
     38         vector<int> v(n);
     39         for (int j = 0; j < n; j++)
     40         {
     41             cin >> v[j];
     42         }
     43         sort(v.begin(), v.end());
     44         cout << 2 * (v[n - 1] - v[0]) + 2 * (v[n - 2] - v[1]) << endl;
     45     }
     46 }
     47 ```
     48 
     49 **Code (Python)**
     50 
     51 ```
     52 t = int(input())
     53 for i in range(t):
     54     n = int(input())
     55     a = list(map(int, input().split()))
     56     a = sorted(a)
     57     ans = 2 * (a[n - 1] - a[0] + a[n - 2] - a[1])
     58     print(ans)
     59 ```
     60 
     61 [1934B — Yet Another Coin Problem](https://codeforces.com/contest/1934/problem/B)
     62 
     63 **Solution 1**
     64 
     65 **Hint**
     66 
     67 At max how many $1$, $3$, $6$, $10$ are required?
     68 
     69 **Solution**
     70 
     71 **Fact**: You will never need more than $2$ ones, $1$ threes, $4$ sixes and $2$ tens.
     72 
     73 **Reason**:
     74 
     75 For $1$: Suppose if you used $k$ > $2$ ones, then you could have used one $3$ and $k$ — $3$ ones.
     76 
     77 For $3$: Suppose if you used $k$ > $1$ threes, then you could have used one $6$ and $k$ — $2$ threes.
     78 
     79 For $6$: Suppose if you used $k$ > $4$ sixes, then you could have used two $15$'s and $k$ — $5$ sixes.
     80 
     81 For $10$: Suppose if you used $k$ > $2$ tens, then you could have used two $15$'s and $k$ — $3$ tens.
     82 
     83 now since bound on their count is less, we can bruteforce on these count.
     84 
     85 **Code (C++)**
     86 
     87 ```
     88 #include <bits/stdc++.h>
     89 
     90 using namespace std;
     91 
     92 int main()
     93 {
     94     ios::sync_with_stdio(false);
     95     cin.tie(nullptr);
     96     int testcases;
     97     cin >> testcases;
     98     for (int t = 1; t <= testcases; t++)
     99     {
    100         int n;
    101         cin >> n;
    102         int ans = 1e9;
    103         for(int ones = 0; ones <= 2; ones++){
    104             for(int threes = 0; threes <= 1; threes++){
    105                 for(int sixes = 0; sixes <= 4; sixes++){
    106                     for(int tens = 0; tens <= 2; tens++){
    107                         int brute_sum = 1*ones + 3*threes + 6*sixes + 10*tens;
    108                         if(brute_sum <= n && (n-brute_sum)%15 == 0){
    109                             ans = min(ans, ones + threes + sixes + tens + (n-brute_sum)/15);
    110                         }
    111                     }
    112                 }
    113             }
    114         }
    115         cout << ans << endl;
    116     }
    117 }
    118 ```
    119 
    120 **Solution 2**
    121 
    122 **Hint**
    123 
    124 When will the greedy logic of choosing the higher-valued coin first work?
    125 
    126 **Solution**
    127 
    128 **Fact $1$**: If coins of value $1$, $3$, $6$ and $15$ were only present the greedy logic of selecting the higher valued first would work.
    129 
    130 **Reason**: We use coins of value one at most $2$ times, coins of value three at most $1$ time, coins of value six at most $2$ times (if it was used $3$ times, it would be better to use two coins $15 + 3$) But we can't use the coin of value $3$ and both coins of value $6$ simultaneously, because we would prefer just using $15$.  
    131 It means that these coins may sum up to $1 + 1 + 3 + 6 = 11$ or $1 + 1 + 6 + 6 = 14$ at max. So, we may use the value $15$ greedily, because the remaining part is less than $15$. When we are left with only the values $1$, $3$, and $6$, greedily solving is obviously correct, because each coin is a divisor of the next coin.
    132 
    133 **Fact $2$**: We don't need more than $2$ ten coins.
    134 
    135 **Reason**: Better to use $2$ fifteen coins instead of $3$ ten coins.
    136 
    137 Using the above two facts it can be shown that the answer will have $k \lt 3$ ten coin, therefore, answer = $\min$($\text{answer}(n-10*k)+k$ assuming $1$, $3$, $6$ and $15$ coins are only present).
    138 
    139 **Code (C++)**
    140 
    141 ```
    142 #include<bits/stdc++.h>
    143  
    144 using namespace std;
    145  
    146 int getAns(int n){
    147     int ans=0;
    148     ans+=n/15;
    149     n%=15;
    150     ans+=n/6;
    151     n%=6;
    152     ans+=n/3;
    153     n%=3;
    154     ans+=n;
    155     return ans;
    156 }
    157  
    158 int main(){
    159     ios::sync_with_stdio(false), cin.tie(nullptr);
    160  
    161     int testcases;
    162     cin>>testcases;
    163     for(int i=1;i<=testcases;i++){
    164         int n;cin>>n;
    165         if(n<10){
    166             cout<<getAns(n)<<endl;
    167         }else if(n<20){
    168             cout<<min(getAns(n),getAns(n-10)+1)<<endl;
    169         }else{
    170             cout<<min({getAns(n),getAns(n-10)+1,getAns(n-20)+2})<<endl;
    171         }
    172     }
    173 }
    174 ```
    175 
    176 [1934C — Find a Mine](https://codeforces.com/contest/1934/problem/C)
    177 
    178 **Hint 1**
    179 
    180 After querying "$?$ $1$ $1$" What do we know about the location of mines?
    181 
    182 **Answer**
    183 
    184 If the answer is $a_1$ the location of one of the mines is $(x, y)$ such that $x+y = a_1+2$.
    185 
    186 **Solution 1**
    187 
    188 **Solution**
    189 
    190 First, we query "$?$ $1$ $1$" then you get a value $a_1$ and you know that at least one of the mine is on the line $x+y=a_1+2$.
    191 
    192 Now we make two more queries on both ends of this line where it touches the grid. After these two queries, we get two possible locations of the mine. We query one of these positions if we receive $0$ as the answer then this location otherwise the other location is the answer.
    193 
    194 **Reason**: One of that two locations contains a mine. The other mine could spoil the result of the query only from one end. If it was closer from the other mine to both of the ends, it would mean that going from one end to the other is shorter through that mine, than through the diagonal. That's impossible.
    195 
    196 **Code (C++)**
    197 
    198 ```
    199 #include <bits/stdc++.h>
    200 using namespace std;
    201 
    202 int main(){
    203     ios_base::sync_with_stdio(0);
    204     cin.tie(0);
    205     int T;
    206     cin >> T;
    207     while (T--){
    208         int n, m;
    209         cin >> n >> m;
    210         auto query = [&](int x, int y){
    211             if (x < 1 || x > n || y < 1 || y > m)
    212                 return -1;
    213             cout << "? " << x << ' ' << y << endl;
    214             int z;
    215             cin >> z;
    216             return z;
    217         };
    218         int d = query(1, 1);
    219         int lx = max(1, 2 + d - m);
    220         int p = query(lx, 2 + d - lx);
    221         int rx = max(1, 2 + d - n);
    222         int q = query(2 + d - rx, rx);
    223         if (query(lx + p / 2, 2 + d - lx - p / 2) == 0){
    224             cout << "! " << lx + p / 2 << " " <<  2 + d - lx - p / 2<<endl;
    225         }else{
    226             cout << "! " << 2 + d - rx - q / 2 << " " << rx + q / 2 << endl;
    227         }
    228     }
    229 }
    230 ```
    231 
    232 **Solution 2**
    233 
    234 **Hint 2**
    235 
    236 What if we made the second query as "$?$ $n$ $m$"?
    237 
    238 **Answer**
    239 
    240 If the answer is $a_2$ the location of one of the mines is $(x, y)$ such that $x+y = n+m-a_2$.
    241 
    242 **Solution**
    243 
    244 Using Hint $1$ and Hint $2$ if we get the same line equation i.e. $n+m-a_2=a_1-2$ we can just query one of the endpoints of this line and get the answer.
    245 
    246 Otherwise, we can query "$?$ $1$ $m$" and we will get one more line perpendicular to the earlier two. One of the mines has to be on this line therefore there will be a mine either on the intersection of line we got from query $1$ and query $3$ or on the intersection of line we got from query $2$ and query $3$.
    247 
    248 We can make our next query on any of these intersections if we get the answer as $0$, then this point is the answer otherwise the other point is the answer.
    249 
    250 **Code (C++)**
    251 
    252 ```
    253 #include <bits/stdc++.h>
    254 
    255 using namespace std;
    256  
    257 using ll = long long;
    258  
    259 ll query(ll x, ll y) {
    260     cout << "? " << x << ' ' << y << endl;
    261     ll d;
    262     cin >> d;
    263     return d;
    264 }
    265  
    266 int main() {
    267     ios::sync_with_stdio(false), cin.tie(nullptr);
    268     
    269     ll t;
    270     cin >> t;
    271     
    272     while (t--) {
    273         ll n, m;
    274         cin >> n >> m;
    275         
    276         ll sum1 = query(1, 1) + 2;
    277         ll sum2 = n + m - query(n, m);
    278         ll dif1 = query(1, m) + 1 - m;
    279         
    280         auto simplify = [&](ll num, ll lim)->ll{
    281             return max(min(num, lim), 1LL);
    282         };
    283         ll x1 = simplify((sum1+dif1)/2, n), y1 = simplify((sum1-dif1)/2, m);
    284         ll x2 = simplify((sum2+dif1)/2, n), y2 = simplify((sum2-dif1)/2, m);
    285         
    286         if (query(x1, y1)) cout << "! " << x2 << ' ' << y2 << endl;
    287         else cout << "! " << x1 << ' ' << y1 << endl;
    288     }
    289     return 0;
    290 }
    291 ```
    292 
    293 [1934D1 — XOR Break — Solo Version](https://codeforces.com/contest/1934/problem/D1)
    294 
    295 **Hint**
    296 
    297 To generate any possible $m$, it takes at most two operations.
    298 
    299 **Solution**
    300 
    301 Let's determine the achievable values of $m$ for a given $n$.
    302 
    303 If $n$ is a perfect power of $2$, then it cannot be broken down further, and no $m \lt n$ is achievable. Otherwise, if $n$ has at least two set bits, let's denote the most significant bit as $a$ and the second most significant bit as $b$.
    304 
    305 **Fact 1**: All $m$ values less than $n$ are achievable if their most significant bit does not lie between $b+1$ and $a-1$.
    306 
    307 **Reason**: For instance, $1001????$ can be decomposed into $1000????$ and $0001????$, or $1001????$ and $0000????$. In either case, we can never flip the $6^{th}$ or $7^{th}$ bit.
    308 
    309 Using the above fact, we can break the problem into two cases:
    310 
    311 **Case 1**: If the most significant bit of $m$ is at position $\leq b$.
    312 
    313 Perform the first operation as $2^{b+1} - 1$ and $n \oplus (2^{b+1} - 1)$ ($10001????$ -> $10000????$ and $000011111$ in binary form). Then, any submask of $2^{b+1} - 1$ can be created in the next operation.
    314 
    315 **Case 2**: If the most significant bit of $m$ is at position $a$.
    316 
    317 If the most significant bit of $m$ is at position $a$, then $m$ can be obtained in one operation as $m$ and $m \oplus n$, since $m \lt n$ as given in the question, and $n \oplus m$ has its most significant bit $ \lt a$.
    318 
    319 **Code**
    320 
    321 ```
    322 #include<bits/stdc++.h>
    323 
    324 using namespace std;
    325  
    326 using ll = long long;
    327  
    328 int main() {
    329     ios::sync_with_stdio(false), cin.tie(nullptr);
    330     
    331     ll t;
    332     cin >> t;
    333     
    334     while (t--) {
    335         ll n, m;
    336         cin >> n >> m;
    337         
    338         ll hi = 0, sec_hi = 0;
    339         for (ll p = (1LL<<62); p > 0; p >>= 1) {
    340             if (p & n) {
    341                 if (!hi) hi = p;
    342                 else if (!sec_hi) sec_hi = p;
    343             }
    344         }
    345         bool flag = (sec_hi && ((m & hi) || (m < sec_hi*2)));
    346         if (!flag) {
    347             cout << -1 << '\n';
    348             continue;
    349         }
    350         vector<ll> ans = {n, m};
    351         if (!(m & hi) && !(m & sec_hi)) ans = {n, m^sec_hi, m};
    352         
    353         cout << (ll)ans.size()-1 << '\n';
    354         for (auto &x: ans) cout << x << ' ';
    355         cout << '\n';
    356     }
    357     return 0;
    358 }
    359 ```
    360 
    361 [1934D2 — XOR Break — Game Version](https://codeforces.com/contest/1934/problem/D2)
    362 
    363 **Hint 1**
    364 
    365 If both $p_1$ and $p_2$ are perfect powers of $2$, it is a losing state since you cannot perform a break operation on either of those.
    366 
    367 **Hint 2**
    368 
    369 If either $p_1$ or $p_2$ has a bit count of $2$, then this is a winning state.
    370 
    371 **Reason**
    372 
    373 You can force your opponent into the state described in Hint $1$ using the number which has $2$ bitcount.
    374 
    375 **Solution**
    376 
    377 **Fact 1**: If $p_1$ has an odd bit count, then it can only be broken into two numbers such that one has an odd bit count and the other has an even bit count.
    378 
    379 **Fact 2**: If either $p_1$ or $p_2$ has an even bit count, then this is a winning state.
    380 
    381 **Reason** : If either $p_1$ or $p_2$ has an even bit count, without loss of generality, assume it's $p_1$. Then break it into $2^{msb \text{ of } p_1}$ and $p_1 \oplus 2^{msb \text{ of } p_1}$, where $msb$ is the most significant bit.
    382 
    383 If the opponent chooses $2^{msb \text{ of } p_1}$, they instantly lose (using Hint $1$), so they are forced to choose the other number with an odd bit count. From Fact $1$, we can conclude that in the next turn, the state will remain conserved for the current player.
    384 
    385 Because we eliminate the most significant bit in every query, this game will go on for at most $60$ turns for the player who reached this position first. At one point, the player who is at this state will have a number with two set bits.
    386 
    387 Hence, from Hint $2$, we can say this player will win. So, as Alice, you will start first if $n$ has an even number of bits and start second if it has an odd number of bits. Proceed using the strategy discussed above. So as Alice you have will start first if $n$ has even number of bits and start second if it has odd number of bits. Any proceed using the strategy discussed above.
    388 
    389 **Code**
    390 
    391 ```
    392 #include<bits/stdc++.h>
    393  
    394 using namespace std;
    395  
    396 int main(){
    397     ios::sync_with_stdio(false);
    398     cin.tie(nullptr);
    399  
    400     int testcases;cin>>testcases;
    401  
    402     for(int testcase=1;testcase<=testcases;testcase++){
    403         long long n;cin>>n;
    404         long long curr=n;
    405         int parity=0;
    406         if(__builtin_popcountll(n)%2){
    407             cout<<"secoNd"<<endl;
    408         }else{
    409             cout<<"firSt"<<endl;
    410             parity=1;
    411         }
    412         int turn=0;
    413         while(1){
    414             if(turn%2==parity){
    415                 long long p1,p2;cin>>p1>>p2;
    416                 if (p1 == 0 && p2 == 0)
    417                     break;
    418                 if(__builtin_popcountll(p1)%2==0){
    419                     curr=p1;
    420                 }else{
    421                     curr=p2;
    422                 }
    423             }else{
    424                 int pos=0;
    425                 for(int i=0;(1ll<<i)<curr;i++){
    426                     if(curr&(1ll<<i)){
    427                         pos=i;
    428                     }
    429                 }
    430                 long long p1=(1ll<<pos);
    431                 long long p2=curr^p1;
    432                 cout<<p1<<" "<<p2<<endl;
    433                 curr = p1;
    434             }
    435             turn++;
    436         }
    437     }
    438 }
    439 ```
    440 
    441 [1934E — Weird LCM Operations](https://codeforces.com/contest/1934/problem/E)
    442 
    443 **Solution**
    444 
    445 **Fact 1**: If for $(x, y, z)$ their pairwise GCDs are equal to their common GCD (this means that $(x, y, z)$ = $(g * X, g * Y, g * Z)$ where $(X, Y, Z)$ are pairwise coprime), then making an operation on them (gives $(g * X * Y, g * X * Z,g * Y * Z)$) and looking at the subsequences of size EXACTLY 2, we find all three GCD: $x$, $y$, $z$. Let's call such tuple NICE.
    446 
    447 **Result**: If we can split all values in the array into independent NICE tuples, then we can just perform an operation on each of them and the problem is solved.
    448 
    449 **Fact 2**: We don't touch any value $\leq$ $\frac{n}{2}$. If there is $x$ $\leq$ $\frac{n}{2}$, then $2 * x \leq n$. If we don't touch $x$, then we will always have another value that is divisible by $x$ (it's easy to see that performing an operation on a multiple of $x$ leaves us with another multiple of $x$), so we will always have GCD equal to $x$ taking a subsequence $(x, x * A)$.
    450 
    451 **Fact 3**: A sequence of consecutive integers $(x, x+1, x+2, ..., x+11)$ can be partitioned into $4$ disjoint sets of size $3$, each forming a NICE tuple, if $(x+11) \% 4$ equals $2$ or $1$.
    452 
    453 **For $(x+11) \% 4 = 2$**: The sets $(x, x+1, x+2)$, $(x+4, x+5, x+6)$ and $(x+8, x+9, x+10)$ are NICE because, the first and third terms are always odd, and the second term is always even. The set $(x+3, x+7, x+11)$ is NICE because it has the form of $2*(2*n-1)$, $2*(2*n)$, $2*(2*n+1)$, ensuring that the pairwise GCDs are equal to the common GCD.
    454 
    455 **For $(x+11) \% 4 = 1$**: The sets $(x, x+4, x+8)$, $(x+1, x+2, x+3)$, $(x+5, x+6, x+7)$ and $(x+9, x+10, x+11)$ are NICE, the same logic like $(x+11) \% 4 = 2$ follows,
    456 
    457 If $n \% 4 = 3$ we can do one operation as $(1, 2, n)$, and if $n \% 4 = 0$ we can do one operation as $(1, n-1, n)$. Let's group the remaining elements into the groups of size $12$, starting from the end, and continuing until we reach the number $\frac{n}{2}$.
    458 
    459 Eventually, we can count that we used no more than $\lfloor \frac{n}{6} \rfloor + 5$ operations.
    460 
    461 Solutions for $n \leq 13$ should be found manually.
    462 
    463 **Code**
    464 
    465 ```
    466 #include<bits/stdc++.h>
    467  
    468 using namespace std;
    469 vector<vector<vector<int>>> pans(14);
    470 int main(){
    471  
    472     ios::sync_with_stdio(false), cin.tie(nullptr);
    473  
    474     int t;cin>>t;
    475  
    476     pans[3]={{1,2,3}};
    477     pans[4]={{1,3,4}};
    478     pans[5]={{3,4,5}};
    479     pans[6]={{1,3,5},{2,4,6}};
    480     pans[7]={{2,4,6},{3,5,7}};
    481     pans[8]={{2,6,8},{3,5,7}};
    482     pans[9]={{1,3,5},{2,4,6},{7,8,9}};
    483     pans[10]={{3,4,5},{2,6,8},{7,9,10}};
    484     pans[11]={{2,6,8},{3,5,7},{9,10,11}};
    485     pans[12]={{1,11,12},{6,8,10},{5,7,9}};
    486     pans[13]={{1,12,13},{7,9,11},{6,8,10}};
    487     for(int tt=0;tt<t;tt++){
    488         int n;cin>>n;
    489         if(n<=2){
    490             cout<<-1<<endl;
    491         }else if(n<14){
    492             cout<<pans[n].size()<<endl;
    493             for(auto w: pans[n]){
    494                 cout<<w[0]<<" "<<w[1]<<" "<<w[2]<<endl;
    495             }
    496         }else{
    497             vector<int> v(n);
    498             for(int i=0;i<n;i++){
    499                 v[i]=i+1;
    500             }
    501             vector<vector<int>> ans;
    502             while (2*v.size()>n){
    503                 if(v.size()%4==2){
    504                     vector<int> buf;
    505                     for(int i=0;i<12;i++){
    506                         buf.push_back(v.back());
    507                         v.pop_back();
    508                     }
    509                     reverse(buf.begin(),buf.end());
    510                     ans.push_back({buf[0],buf[1],buf[2]});
    511                     ans.push_back({buf[4],buf[5],buf[6]});
    512                     ans.push_back({buf[8],buf[9],buf[10]});
    513                     ans.push_back({buf[3],buf[7],buf[11]});
    514                 }else if(v.size()%4==1){
    515                     vector<int> buf;
    516                     for(int i=0;i<12;i++){
    517                         buf.push_back(v.back());
    518                         v.pop_back();
    519                     }
    520                     reverse(buf.begin(),buf.end());
    521                     ans.push_back({buf[1],buf[2],buf[3]});
    522                     ans.push_back({buf[5],buf[6],buf[7]});
    523                     ans.push_back({buf[9],buf[10],buf[11]});
    524                     ans.push_back({buf[0],buf[4],buf[8]});
    525                 }else if(v.size()%4==3){
    526                     vector<int> buf;
    527                     buf.push_back(v.back());
    528                     v.pop_back();
    529                     buf.push_back(2);
    530                     buf.push_back(1);
    531                     reverse(buf.begin(),buf.end());
    532                     ans.push_back({buf[0],buf[1],buf[2]});
    533                 }else{
    534                     vector<int> buf;
    535                     buf.push_back(v.back());
    536                     v.pop_back();
    537                     buf.push_back(v.back());
    538                     v.pop_back();
    539                     buf.push_back(1);
    540                     reverse(buf.begin(),buf.end());
    541                     ans.push_back({buf[0],buf[1],buf[2]});
    542                 }
    543             }
    544             cout<<ans.size()<<endl;
    545             for(auto w: ans){
    546                 cout<<w[0]<<" "<<w[1]<<" "<<w[2]<<endl;
    547             }
    548         }
    549     }
    550 }
    551 ```