codeforces-scrape

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

1358.md (13953B)


      1 Source: https://codeforces.com/blog/entry/77869
      2 
      3 This is our first contest for the three of us ([Alexdat2000](/profile/Alexdat2000 "Candidate Master Alexdat2000"), [crazyilian](/profile/crazyilian "Candidate Master crazyilian"), [sevlll777](/profile/sevlll777 "Master sevlll777")), so we would like to share our impressions of creating this contest. Check it if you want to!
      4 
      5 **ROUND LOG**
      6 
      7 First problem — task rejections. [300iq](/profile/300iq "Legendary Grandmaster 300iq") rejected about 13 problems, 6 of which were supposed to be problem D. In the end, we came up with E, and the old E moved to D.
      8 
      9 These are the verdicts with which the problems were rejected:
     10 
     11 1. The idea is very simple here and the implementation is very simple too, this problem is definitely not D1C-D and definitely not interesting.
     12 2. Not an interesting problem, too standard, without new ideas.
     13 3. This is a known problem which is solved quite simply by a compressed tree.
     14 4. Unfortunately, it seems to me that this problem does not fit D1B. It is a funny construct but it is too technical (not interesting enough) for this position and too simple for the next ones.
     15 5. This problem is solved very simply by taking a close look at the sequence, so it is not very interesting.
     16 6. It seems to me that this problem is too standard. It is as if in the condition it is written, which dp should be written.
     17 7. The idea of 4 consecutive numbers is known.
     18 8. It's a known problem.
     19 9. It's a known problem.
     20 10. It's too standard.
     21 11. There's some greed in there. Is that the right thing to do?
     22 12. Well, first of all, it's doubtful you have any proof. Second of all, isn't that on oeis?
     23 13. It doesn't make her any better, it's a known problem.
     24 
     25 When the problems were already formed, their creation began. In some problems, it was necessary to lower the constraints, which made it impossible to cut off some non-deterministic or not optimal solutions.
     26 
     27 Otherwise, everything was fine until the last 18 hours before the contest began...
     28 
     29 * Mike [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") Mirzayanov sent 7 issues to problem A. It was necessary to redo all the tests in the problem and much more.
     30 * While we were correcting them, coordinator Ildar [300iq](/profile/300iq "Legendary Grandmaster 300iq") Gainullin told us to remove all the illustrations for the problem (memes and just cool pictures at the bottom of the notes). We did not like it *very* much, we wanted the pictures to be included in the contest.
     31 * We finished fixing problem A, and went to bed. At that time Ildar (thank him very much) was polishing the conditions of all the other problems. Unfortunately, at that moment he removed the pictures. He also suddenly renamed problem F and city in the English version of problem D.
     32 * 4 hours before the beginning. Mikhail Mirzayanov started sending issues to other problems.
     33 * We had to redo almost all the tests for problems B, C and D.
     34 * Heroically won the limits in E 2 hours before the contest start.
     35 
     36 A total of 475 commits to the Polygon were made.
     37 
     38 During the round there were many of the same type, but also some funny clares. For example:
     39 
     40 * Problem C. *i cant solve it*
     41 * Problem E. *When will a COVID 19 vaccine come out???*
     42 
     43 Thanks to everyone who upvotes this editorial!
     44 
     45 And, of course, here's the tutorial of the round.
     46 
     47 [1358A - Park Lighting](/contest/1358/problem/A "Codeforces Round 645 (Div. 2)")  
     48  Idea: [Alexdat2000](/profile/Alexdat2000 "Candidate Master Alexdat2000")
     49 
     50 **Picture**
     51 
     52 ![ ](/predownloaded/69/d6/69d651bc92d4f674451c6d0e4b7011d1eeca305f.jpg)
     53 
     54 **Tutorial**
     55 
     56 Tutorial is loading...
     57 
     58 **Solution**
     59 
     60 ```
     61 #include <iostream>
     62 
     63 using namespace std;
     64 
     65 int main() {
     66     int t, n, m;
     67     cin >> t;
     68     while (t--) {
     69         cin >> n >> m;
     70         cout << (n * m + 1) / 2 << '\n';
     71     }
     72 }
     73 ```
     74 
     75 [1358B - Maria Breaks the Self-isolation](/contest/1358/problem/B "Codeforces Round 645 (Div. 2)")  
     76  Idea: [crazyilian](/profile/crazyilian "Candidate Master crazyilian")
     77 
     78 **Picture**
     79 
     80 ![ ](/predownloaded/d9/1e/d91ef9cc01603a027fed1c3cd35d1f9794acd20e.jpg)
     81 
     82 **Tutorial**
     83 
     84 Tutorial is loading...
     85 
     86 **Solution**
     87 
     88 ```
     89 #include <iostream>
     90 #include <vector>
     91 #include <algorithm>
     92 
     93 using namespace std;
     94 
     95 void solve() {
     96     int n;
     97     cin >> n;
     98     vector<int> arr(n);
     99     for (int &el : arr)
    100         cin >> el;
    101     sort(arr.begin(), arr.end());
    102     for (int i = n - 1; i >= 0; i--) {
    103         if (arr[i] <= i + 1) {
    104             cout << i + 2 << '\n';
    105             return;
    106         }
    107     }
    108     cout << 1 << '\n';
    109 }
    110 
    111 int main() {
    112     int t;
    113     cin >> t;
    114     while (t--)
    115         solve();
    116 }
    117 ```
    118 
    119 [1358C - Celex Update](/contest/1358/problem/C "Codeforces Round 645 (Div. 2)")  
    120  Idea: [crazyilian](/profile/crazyilian "Candidate Master crazyilian")
    121 
    122 **Picture**
    123 
    124 ![ ](/predownloaded/5d/46/5d460b7002fcd0b7aed544370e3c4656aa9cb629.jpg)
    125 
    126 **Tutorial**
    127 
    128 Tutorial is loading...
    129 
    130 **Solution**
    131 
    132 ```
    133 #include <iostream>
    134 
    135 using namespace std;
    136 
    137 int main() {
    138     int t;
    139     cin >> t;
    140     while (t--) {
    141         long long a, b, c, d;
    142         cin >> a >> b >> c >> d;
    143         cout << (c - a) * (d - b) + 1 << '\n';
    144     }
    145 }
    146 ```
    147 
    148 [1358D - The Best Vacation](/contest/1358/problem/D "Codeforces Round 645 (Div. 2)")  
    149  Idea: [sevlll777](/profile/sevlll777 "Master sevlll777")
    150 
    151 **Picture**
    152 
    153 ![ ](/predownloaded/c3/12/c312001b49041d00dabd8cc8cc848e751d639681.jpg)
    154 
    155 **Tutorial**
    156 
    157 Tutorial is loading...
    158 
    159 **Solution**
    160 
    161 ```
    162 #include <iostream>
    163 #include <algorithm>
    164 #include <vector>
    165 
    166 #define int long long
    167 
    168 using namespace std;
    169 
    170 signed main() {
    171   int n, len;
    172   cin >> n >> len;
    173   vector<int> A(2 * n);
    174   for (int i = 0; i < n; i++) {
    175     cin >> A[i];
    176     A[n + i] = A[i];
    177   }
    178   n *= 2;
    179   
    180   vector<int> B = {0}, C = {0};
    181   for (int i = 0; i < n; i++) 
    182     B.push_back(B.back() + A[i]);
    183   for (int i = 0; i < n; i++) 
    184     C.push_back(C.back() + (A[i] * (A[i] + 1)) / 2);
    185   int ans = 0;
    186   for (int i = 0; i < n; i++) {
    187     if (B[i + 1] >= len) {
    188       int z = upper_bound(B.begin(), B.end(), B[i + 1] - len) - B.begin();
    189       int cnt = C[i + 1] - C[z];
    190       int days = B[i + 1] - B[z];
    191       int too = len - days;
    192       cnt += ((A[z - 1] * (A[z - 1] + 1)) / 2);
    193       cnt -= (((A[z - 1] - too) * (A[z - 1] - too + 1)) / 2);
    194       ans = max(ans, cnt);
    195     }
    196   }
    197   cout << ans;
    198 }
    199 ```
    200 
    201 [1358E - Are You Fired?](/contest/1358/problem/E "Codeforces Round 645 (Div. 2)")  
    202  Idea: [sevlll777](/profile/sevlll777 "Master sevlll777") и [crazyilian](/profile/crazyilian "Candidate Master crazyilian")
    203 
    204 **Picture**
    205 
    206 ![ ](/predownloaded/a1/8a/a18a531b5df3fbc2a96cb409029bd543d7e75510.jpg)
    207 
    208 **Tutorial**
    209 
    210 Tutorial is loading...
    211 
    212 **Solution**
    213 
    214 ```
    215 #include <iostream>
    216 #include <vector>
    217 
    218 using namespace std;
    219 
    220 #define int long long
    221 
    222 signed main() {
    223   int n;
    224   cin >> n;
    225   int N = (n + 1) / 2;
    226   vector<int> a(N);
    227   for (int &el : a)
    228     cin >> el;
    229   int Ax;
    230   cin >> Ax;
    231   vector<int> m(N + 1, 0);
    232   int Pprefsm = 0;
    233   for (int i = 1; i < N + 1; ++i) {
    234     Pprefsm += Ax - a[i - 1];
    235     m[i] = min(m[i - 1], Pprefsm);
    236   }
    237   int Aprefsm = 0;
    238   for (int k = 1; k <= N; ++k)
    239     Aprefsm += a[k - 1];
    240   for (int k = N; k <= n; ++k) {
    241     if (Aprefsm + m[n - k] > 0)
    242       return cout << k, 0;
    243     Aprefsm += Ax;
    244   }
    245   cout << -1;
    246 }
    247 ```
    248 
    249 [1358F - Tasty Cookie](/contest/1358/problem/F "Codeforces Round 645 (Div. 2)")  
    250  Idea: [sevlll777](/profile/sevlll777 "Master sevlll777") и [crazyilian](/profile/crazyilian "Candidate Master crazyilian")
    251 
    252 **Picture**
    253 
    254 ![ ](/predownloaded/78/c8/78c8d3fb09a90defb459a525252e89d6c9e9a9c5.jpg)
    255 
    256 **Tutorial**
    257 
    258 Tutorial is loading...
    259 
    260 **Solution by Alexdat2000**
    261 
    262 ```
    263 #include <bits/stdc++.h>
    264 
    265 using namespace std;
    266 
    267 #define int long long
    268 const int LIM = 2e5;
    269 
    270 bool is_increasing(const vector<int> &vec) {
    271   for (int i = 0; i < vec.size() - 1; i++) {
    272     if (vec[i] >= vec[i + 1])
    273       return false;
    274   }
    275   return true;
    276 }
    277 
    278 bool is_decreasing(const vector<int> &vec) {
    279   for (int i = 0; i < vec.size() - 1; i++) {
    280     if (vec[i] <= vec[i + 1])
    281       return false;
    282   }
    283   return true;
    284 }
    285 
    286 vector<int> rollback(const vector<int> &vec) {
    287   vector<int> ans(vec.size());
    288   ans[0] = vec[0];
    289   for (int i = 1; i < vec.size(); i++)
    290     ans[i] = vec[i] - vec[i - 1];
    291   return ans;
    292 }
    293 
    294 signed main() {
    295   int n;
    296   cin >> n;
    297   vector<int> a(n), b(n);
    298   for (int &i : a)
    299     cin >> i;
    300   for (int &i : b)
    301     cin >> i;
    302   vector<int> a_rev = a;
    303   reverse(a_rev.begin(), a_rev.end());
    304 
    305   if (n == 1) {
    306     if (a == b)
    307       cout << "SMALL" << '\n' << 0 << '\n';
    308     else
    309       cout << "IMPOSSIBLE" << '\n';
    310     return 0;
    311   }
    312 
    313   int sum_a = accumulate(a.begin(), a.end(), 0LL);
    314   int sum_b = accumulate(b.begin(), b.end(), 0LL);
    315   int rollback_cnt = 0;
    316 
    317   if (n == 2) {
    318     vector<int> ans; // -1 = R, X = PPP..PP (x times)
    319     int move_cnt = 0, roll_cnt = 0;  // both types
    320 
    321     bool rev = a[0] > a[1];
    322     if (rev)
    323       swap(a[0], a[1]);
    324 
    325     if (b[0] > b[1]) {
    326       swap(b[0], b[1]);
    327       ans.push_back(-1);
    328       move_cnt++;
    329     }
    330     while (true) {
    331       if (sum_a > sum_b) {
    332         cout << "IMPOSSIBLE" << '\n';
    333         return 0;
    334       }
    335 
    336       if (sum_a == sum_b) {
    337         if (a != b) {
    338           cout << "IMPOSSIBLE" << '\n';
    339           return 0;
    340         }
    341 
    342         if (rev) {
    343           ans.push_back(-1);
    344           move_cnt++;
    345         }
    346 
    347         if (rollback_cnt > LIM) {
    348           cout << "BIG" << '\n' << rollback_cnt << '\n';
    349           return 0;
    350         } else {
    351           cout << "SMALL" << '\n' << move_cnt << '\n';
    352           reverse(ans.begin(), ans.end());
    353           for (auto i : ans) {
    354             if (i == -1)
    355               cout << "R";
    356             else {
    357               for (int _ = 0; _ < i; _++)
    358                 cout << "P";
    359             }
    360           }
    361           cout << '\n';
    362           return 0;
    363         }
    364       }
    365 
    366       if (a[0] == b[0]) {
    367         if ((b[1] - a[1]) % b[0] == 0) {
    368           roll_cnt = (b[1] - a[1]) / b[0];
    369           ans.push_back(roll_cnt);
    370           move_cnt += roll_cnt, rollback_cnt += roll_cnt;
    371           b = a;
    372           sum_b = b[0] + b[1];
    373         } else {
    374           cout << "IMPOSSIBLE" << '\n';
    375           return 0;
    376         }
    377       } else {
    378         roll_cnt = b[1] / b[0];
    379         ans.push_back(roll_cnt);
    380         move_cnt += roll_cnt, rollback_cnt += roll_cnt;
    381 
    382         ans.push_back(-1);
    383         move_cnt++;
    384         swap(b[0], b[1]);
    385         b[0] %= b[1];
    386         sum_b = b[0] + b[1];
    387       }
    388     }
    389   }
    390 
    391   string ans;
    392 
    393   while (true) {
    394     if (sum_a == sum_b) {
    395       if (a_rev == b) {
    396         ans.push_back('R');
    397         reverse(b.begin(), b.end());
    398       }
    399       if (a == b) {
    400         reverse(ans.begin(), ans.end());
    401         if (rollback_cnt > LIM)
    402           cout << "BIG" << '\n' << rollback_cnt << '\n';
    403         else
    404           cout << "SMALL" << '\n' << ans.size() << '\n' << ans << '\n';
    405       } else
    406         cout << "IMPOSSIBLE" << '\n';
    407       return 0;
    408     } else if (is_increasing(b)) {
    409       b = rollback(b);
    410       sum_b = accumulate(b.begin(), b.end(), 0LL);
    411       ans += 'P';
    412       rollback_cnt++;
    413     } else if (is_decreasing(b)) {
    414       reverse(b.begin(), b.end());
    415       ans += 'R';
    416     } else {
    417       cout << "IMPOSSIBLE" << '\n';
    418       return 0;
    419     }
    420   }
    421 }
    422 ```
    423 
    424 **Solution by Alivk06 (much shorter)**
    425 
    426 ```
    427 #include <bits/stdc++.h>
    428 
    429 using namespace std;
    430 #define int long long
    431 
    432 signed main() {
    433   int n;
    434   cin >> n;
    435   vector<int> a(n), b(n);
    436   for (int i = 0; i < n; ++i) cin >> a[i];
    437   for (int i = 0; i < n; ++i) cin >> b[i];
    438   if (n == 1) {
    439     if (a[0] == b[0]) cout << "SMALL\n" << 0;
    440     else cout << "IMPOSSIBLE";
    441     return 0;
    442   }
    443   if (n == 2) {
    444     vector<pair<int, bool>> res;
    445     int kol = 0;
    446     while (true) {
    447       if (b[0] == 0 || b[1] == 0) {
    448         cout << "IMPOSSIBLE";
    449         return 0;
    450       }
    451       if (a == b) break;
    452       if (a[0] == b[1] && a[1] == b[0]) {
    453         res.emplace_back(1, false);
    454         break;
    455       }
    456       if (b[0] == b[1]) {
    457         cout << "IMPOSSIBLE";
    458         return 0;
    459       }
    460       if (b[0] > b[1]) {
    461         res.emplace_back(1, false);
    462         swap(b[0], b[1]);
    463       }
    464       if (a[0] == b[0] && a[1] < b[1] && a[1] % b[0] == b[1] % b[0]) {
    465         res.emplace_back((b[1] - a[1]) / b[0], true);
    466         kol += res.back().first;
    467         break;
    468       }
    469       if (a[1] == b[0] && a[0] < b[1] && a[0] % b[0] == b[1] % b[0]) {
    470         res.emplace_back((b[1] - a[0]) / b[0], true);
    471         kol += res.back().first;
    472         res.emplace_back(1, false);
    473         break;
    474       }
    475       kol += b[1] / b[0];
    476       res.emplace_back(b[1] / b[0], true);
    477       b[1] %= b[0];
    478     }
    479     if (kol > 2e5) {
    480       cout << "BIG\n";
    481       cout << kol;
    482     } else {
    483       cout << "SMALL\n";
    484       int flex = 0;
    485       for (auto i : res) flex += i.first;
    486       cout << flex << "\n";
    487       for (int i = res.size() - 1; i >= 0; --i) {
    488         for (int j = 0; j < res[i].first; ++j) {
    489           if (res[i].second) cout << "P";
    490           else cout << "R";
    491         }
    492       }
    493     }
    494     return 0;
    495   }
    496   vector<bool> ans;
    497   int kol = 0;
    498   while (true) {
    499     if (a == b) break;
    500     reverse(b.begin(), b.end());
    501     if (a == b) {
    502       ans.push_back(false);
    503       break;
    504     }
    505     reverse(b.begin(), b.end());
    506     bool vozr = false, ub = false, r = false;
    507     for (int i = 1; i < n; ++i) {
    508       if (b[i] > b[i - 1]) vozr = true;
    509       else if (b[i] < b[i - 1]) ub = true;
    510       else r = true;
    511     }
    512     if (r || (vozr && ub)) {
    513       cout << "IMPOSSIBLE";
    514       return 0;
    515     }
    516     vector<int> c(n);
    517     if (ub) {
    518       ans.push_back(false);
    519       reverse(b.begin(), b.end());
    520     }
    521     c[0] = b[0];
    522     for (int i = 1; i < n; ++i) {
    523       c[i] = b[i] - b[i - 1];
    524     }
    525     ans.push_back(true);
    526     b = c;
    527     ++kol;
    528   }
    529   if (kol > 2e5) {
    530     cout << "BIG\n" << kol;
    531   } else {
    532     cout << "SMALL\n" << ans.size() << "\n";
    533     for (int i = ans.size() - 1; i >= 0; --i) {
    534       if (ans[i]) cout << "P";
    535       else cout << "R";
    536     }
    537   }
    538 }
    539 ```
    540 
    541 Thank you, everyone, for participating in the round! We hope you've raised your rating! And if you haven't, don't be sad, you'll do it!