codeforces-scrape

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

1793.md (15087B)


      1 Source: https://codeforces.com/blog/entry/112723
      2 
      3 [1793A - Yet Another Promotion](/contest/1793/problem/A "Codeforces Round 852 (Div. 2)") was authored and prepared by [Ormlis](/profile/Ormlis "Legendary Grandmaster Ormlis")
      4 
      5 [1793B - Fedya and Array](/contest/1793/problem/B "Codeforces Round 852 (Div. 2)") was authored and prepared by [TheEvilBird](/profile/TheEvilBird "Expert TheEvilBird")
      6 
      7 [1793C - Dora and Search](/contest/1793/problem/C "Codeforces Round 852 (Div. 2)") was authored by [dyrbulshchyl](/profile/dyrbulshchyl "International Grandmaster dyrbulshchyl") and prepared by [vaaven](/profile/vaaven "Candidate Master vaaven")
      8 
      9 [1793D - Moscow Gorillas](/contest/1793/problem/D "Codeforces Round 852 (Div. 2)") was authored and prepared by [Gornak40](/profile/Gornak40 "Expert Gornak40")
     10 
     11 [1793E - Velepin and Marketing](/contest/1793/problem/E "Codeforces Round 852 (Div. 2)") was authored and prepared by [Tikhon228](/profile/Tikhon228 "Master Tikhon228")
     12 
     13 [1793F - Rebrending](/contest/1793/problem/F "Codeforces Round 852 (Div. 2)") was authored by [Tikhon228](/profile/Tikhon228 "Master Tikhon228") and prepared by [vaaven](/profile/vaaven "Candidate Master vaaven")
     14 
     15 ## [1793A - Yet Another Promotion](/contest/1793/problem/A "Codeforces Round 852 (Div. 2)")
     16 
     17 Let $n = (m + 1) \cdot q + r$.
     18 
     19 Note that you need to use a promotion if $a \cdot m \leq b \cdot (m + 1)$. In this case, we will buy potatoes $q$ times for the promotion. The remaining potatoes (or all if the promotion is unprofitable) can be bought at $\min(a, b)$ per kilogram.
     20 
     21 Then the answer is:
     22 
     23 $q \cdot \min(a \cdot m, b \cdot (m + 1)) + r \cdot \min(a, b)$
     24 
     25 Thus this solution works in $\mathcal{O}(1)$
     26 
     27 **Code**
     28 
     29 ```
     30 t = int(input())
     31 
     32 for i in range(t):
     33     a, b = map(int, input().split(" "))
     34     n, m = map(int, input().split(" "))
     35 
     36     q = n // (m + 1)
     37     r = n - q * (m + 1)
     38     print(q * min(a * m, b * (m + 1))+ r*min(a,b))
     39 ```
     40 
     41 ## [1793B - Fedya and Array](/contest/1793/problem/B "Codeforces Round 852 (Div. 2)")
     42 
     43 Note that the local minimums and maximums will alternate, and there will be the same number of them $k$. Let's call the $i$-th local maximum by $a_i$, the $i$-th local minimum by $b_i$. Without loss of generality, consider that $a_i$ goes before $b_i$. To get $b_i$ from $a_i$ we need to write out $a_i - b_i$ numbers, to get $a_{(i + 1) \bmod k}$ from $b_i$ we need to write out $a_{(i + 1) \bmod k} - b_i$ numbers.
     44 
     45 Thus, $(a_1 - b_1) + (a_2 - b_1) + (a_2 - b_2) + \ldots + (a_k - b_k) + (a_1 - b_k) =$
     46 
     47 $= 2 \cdot (a_1 + a_2 + \ldots + a_k) - 2 \cdot (b_1 + b_2 + \ldots + b_k) = 2 \cdot (A - B) = n$
     48 
     49 The array $[y, y + 1, y + 2, \ldots, x - 1, x, x - 1, x - 2, \ldots, y + 1]$ will satisfy the condition.
     50 
     51 **Code**
     52 
     53 ```
     54 #include <bits/stdc++.h>
     55 
     56 using namespace std;
     57 
     58 typedef long long ll;
     59 
     60 void solve() {
     61     ll a, b;
     62     cin >> a >> b;
     63     ll n = 2 * (a - b);
     64     cout << n << '\n';
     65     vector<ll> arr(n);
     66     int ptr = 0;
     67     for (ll c = b; c <= a; ++c) {
     68         arr[ptr++] = c;
     69     }
     70     for (ll c = a - 1; c > b; --c) {
     71         arr[ptr++] = c;
     72     }
     73     for (int i = 0; i < n; ++i) {
     74         cout << arr[i] << " \n"[i == n - 1];
     75     }
     76 }
     77 
     78 int main() {
     79     int t;
     80     cin >> t;
     81     while (t--) {
     82         solve();
     83     }
     84     return 0;
     85 }
     86 ```
     87 
     88 ## [1793C - Dora and Search](/contest/1793/problem/C "Codeforces Round 852 (Div. 2)")
     89 
     90 Suppose we want to check whether the entire array satisfies the claim. If this is the case, then we can output the entire array as an answer. Otherwise, one of the two extreme elements does not meet our requirements. From this we can conclude that all segments containing an element that does not meet our requirements will also be incorrect, because this extreme element will remain the minimum/maximum.
     91 
     92 The algorithm follows from the fact above: let's look at the sub-section $[l; r]$, which is initially equal to $[1; n]$. If $a_l = \min(a_{l}, a_{l+1}, \ldots, a_{r})$ or $a_l = \max(a_l, a_{l +1}, \ldots, a_r)$, then we proceed to the segment $[l+1; r]$. A similar reasoning is also needed for $a_r$. Thus, either after some iterations we will get the required sub-section, or we will get $l == r$ and the answer will be $-1$.
     93 
     94 Final asymptotics: $\mathcal{O}(n\log n)$ or $\mathcal{O}(n)$ depending on the implementation.
     95 
     96 **Code**
     97 
     98 ```
     99 #include <bits/stdc++.h>
    100 
    101 using namespace std;
    102 
    103 typedef vector<int> vi;
    104 
    105 void solve() {
    106     int n;
    107     cin >> n;
    108     vi a(n);
    109     for (int &i: a)
    110         cin >> i;
    111     int l = 0, r = n - 1;
    112     int mn = 1, mx = n;
    113     while (l <= r) {
    114         if (a[l] == mn) {
    115             l++;
    116             mn++;
    117         } else if (a[l] == mx) {
    118             l++;
    119             mx--;
    120         } else if (a[r] == mn) {
    121             r--;
    122             mn++;
    123         } else if (a[r] == mx) {
    124             r--;
    125             mx--;
    126         } else {
    127             break;
    128         }
    129     }
    130     if(l <= r){
    131         cout << l + 1 << " " << r + 1 << endl;
    132     } else{
    133         cout << -1 << endl;
    134     }
    135 }
    136 
    137 signed main() {
    138     int q = 1;
    139     cin >> q;
    140     while (q--)
    141         solve();
    142     return 0;
    143 }
    144 ```
    145 
    146 ## [1793D - Moscow Gorillas](/contest/1793/problem/D "Codeforces Round 852 (Div. 2)")
    147 
    148 Denote by $pos_x$ the index of the number $x$ in the permutation. Subsegments with $\operatorname{MEX} \gt 1$ are as follows $1 \le l \le pos_1 \le r \le n$.
    149 
    150 Denote by: $l_x = \min{[pos_1, pos_2, \ldots, pos_x]}$, $r_x=\max{[pos_1, pos_2, \ldots, os_x]}$.
    151 
    152 Subsegments with $\operatorname{MEX} \gt x$ are as follows $1 \le l \le l_x \le r_x \le r \le n$. Let's find all subsegments with $\operatorname{MEX}=x$.
    153 
    154 If $pos_{x + 1} \lt l_x$, then the subsegments with $\operatorname{MEX}=x+1$ are as follows $pos_{x+1} \lt l \le l_x \le r_x \le r \le n$
    155 
    156 If $l_x \le pos_{x + 1} \le r_x$, then there is no subsegment with $\operatorname{MEX}=x+1$
    157 
    158 If $r_x \lt pos_{x+1}$, then the subsegments with $\operatorname{MEX}=x+1$ are as follows $1 \le l \le l_x \le r_x \le r \lt pos_{x+1}$
    159 
    160 It remains only to intersect the sets of such subsegments for $p$ and $q$, which is done trivially.
    161 
    162 **Code**
    163 
    164 ```
    165 #include <bits/stdc++.h>
    166 #define int long long
    167 
    168 using namespace std;
    169 
    170 void solve() {
    171     int n;
    172     cin >> n;
    173     vector<int> pos_a(n + 1);
    174     vector<int> pos_b(n + 1);
    175     for (int i = 0; i < n; i++) {
    176         int a;
    177         cin >> a;
    178         pos_a[a] = i + 1;
    179     }
    180     for (int i = 0; i < n; i++) {
    181         int b;
    182         cin >> b;
    183         pos_b[b] = i + 1;
    184     }
    185     int la = n, ra = 1, lb = n, rb = 1, ans = 0;
    186     for (int i = 1; i + 1 <= n; i++) {
    187         la = min(la, pos_a[i]);
    188         ra = max(ra, pos_a[i]);
    189         lb = min(lb, pos_b[i]);
    190         rb = max(rb, pos_b[i]);
    191         int min_la, max_ra, min_lb, max_rb;
    192         if (pos_a[i + 1] < la) {
    193             min_la = pos_a[i + 1] + 1;
    194             max_ra = n;
    195         } else {
    196             min_la = 1;
    197             max_ra = pos_a[i + 1] - 1;
    198         }
    199         if (pos_b[i + 1] < lb) {
    200             min_lb = pos_b[i + 1] + 1;
    201             max_rb = n;
    202         } else {
    203             min_lb = 1;
    204             max_rb = pos_b[i + 1] - 1;
    205         }
    206         ans += max(min(la, lb) - max(min_la, min_lb) + 1, 0ll) * max(min(max_ra, max_rb) - max(ra, rb) + 1, 0ll);
    207     }
    208     ans += min(pos_a[1], pos_b[1]) * (min(pos_a[1], pos_b[1]) - 1) / 2;
    209     ans += (n - max(pos_a[1], pos_b[1])) * (n - max(pos_a[1], pos_b[1]) + 1) / 2;
    210     ans += abs(pos_a[1] - pos_b[1]) * (abs(pos_a[1] - pos_b[1]) - 1) / 2;
    211     ans++;
    212     cout << ans << endl;
    213 }
    214 
    215 signed main() {
    216     int q = 1;
    217     while (q--)
    218         solve();
    219     return 0;
    220 }
    221 ```
    222 
    223 ## [1793E - Velepin and Marketing](/contest/1793/problem/E "Codeforces Round 852 (Div. 2)")
    224 
    225 Let's sort people by their group size requirement. Suppose we have such a person $i$ that he is not satisfied, and we have a person $j \gt i$ who is satisfied. Then we can replace person $j$ in his group with $i$ and the answer for us will not be worse. It follows that for a particular $k$ the answer is some prefix of the people we can make satisfied.
    226 
    227 Let us also prove that there exists some arrangement of groups that covers the same prefix, and that each group is a continuous segment. Let's take some correct partitioning into groups. Then each group will be a set of unconnected segments. Let's take the leftmost such segment. Note that we can swap it to the nearest segment of the same group to the right without breaking anything.
    228 
    229 Thus we obtained that we can look for a solution in the form of partitioning each prefix into valid groups, which are segments. We will solve this problem using dynamic programming.
    230 
    231 Let $dp[i]$ -- the maximum number of groups into which $i$th prefix can be partitioned, so that everyone is satisfied (and no elements beyond the prefix can be used). Dynamics base: $dp[0] = 0$ (empty prefix maximum can be divided into 0 groups). Transition: for $i$th person his group must have size at least $a[i]$, so the transition looks like this $dp[i] = \underset{0 \leqslant j \leqslant i - a[i]}{\max} dp[j] + 1$. But what if $a[i] \gt i$? Then we can't dial the $i$th prefix. Then we put $dp[i] = -\infty$. This dynamics can be calculated using prefix maximums. This part of the solution works for $\mathcal{O}(n)$.
    232 
    233 Earlier we said that the answer would be some prefix of people who would be satisfied. If we can partition the prefix into some number of groups, then that answer can be the prefix for all $k \leqslant dp[i] + n - i$. (we partition our prefix into $dp$, and the rest of the people one by one into the group)
    234 
    235 If we can't make the whole prefix satisfied ($dp[i] = -\infty$), then we need to add people from outside. Thus, the maximum number of groups we can split into if $i$th prefix is completely satisfied is $n - a[i] + 1$.
    236 
    237 Note that if by some prefix we can score $k$, then we can also score $k - 1$ (combining two groups into one). Then we need to find the largest prefix that fits the given $k$ in the query. This can be done by an array of suffix maximums over $\mathcal{O}(q)$ total. The final asymptotic of the solution is $\mathcal{O}(n \log n + q)$.
    238 
    239 **Code**
    240 
    241 ```
    242 #include<bits/stdc++.h>
    243 
    244 using namespace std;
    245 #define ll long long
    246 #define pii pair<int, int>
    247 #define ld long double
    248 #define all(a) (a).begin(), (a).end()
    249 
    250 const int inf = 1e9 + 7;
    251 
    252 signed main() {
    253     ios_base::sync_with_stdio(0);
    254     cin.tie(0);
    255     cout.tie(0);
    256 
    257     int n;
    258     cin >> n;
    259     vector<int> c(n);
    260     for (int i = 0; i < n; ++i) cin >> c[i];
    261     sort(all(c));
    262     vector<int> ans(n + 1); 
    263     vector<int> dp(n + 1, -inf);
    264     dp[0] = 0;
    265 
    266     for (int i = 1; i <= n; ++i) {
    267         if (c[i-1] <= i) {
    268             dp[i] = dp[i - c[i-1]] + 1;
    269             ans[dp[i] + n - i] = max(ans[dp[i] + n - i], i);
    270         } else {
    271             if (c[i-1] <= n) {
    272                 ans[1 + n - c[i-1]] = max(ans[1 + n - c[i-1]], i);
    273             }
    274         }
    275         dp[i] = max(dp[i], dp[i-1]);
    276     }
    277 
    278     for (int i = n - 1; i >= 0; i--) {
    279         ans[i] = max(ans[i], ans[i + 1]);
    280     }
    281 
    282     int q;
    283     cin >> q;
    284     for (int i = 0; i < q; ++i) {
    285         int x;
    286         cin >> x;
    287         cout << ans[x] << '\n';
    288     }
    289 
    290     return 0;
    291 }
    292 ```
    293 
    294 ## [1793F - Rebrending](/contest/1793/problem/F "Codeforces Round 852 (Div. 2)")
    295 
    296 Let's go through all the elements from left to right. The main task will be to support the current version of $dp[i]$ -- the minimum difference of $a_i$ with the elements to the right of it that we managed to consider. Let us correctly calculate $dp$ for the first $r$ elements. Let's move on to $r + 1$. Let's show how to update the answer for all $j \lt i$, such that $a[j] \gt a[i]$. For $j \lt i$, such that $a[j] \lt a[i]$ is solved similarly.
    297 
    298 Let's take the first element $a[j]$ to the left of $i$, such that $a[j] \gt a[i]$. Note that if there is $l \lt j \lt i$ such that $a[l] \gt a[j] \gt a[i]$, then we will not update $dp[l]$ for it, because $|a[l] - a[j]| \lt |a[l] - a[i]|$. Also, we will not update the answer for $l$ such that $|a[l] - a[j]| \lt |a[l] - a[i]|$, that is, if $a[l] \gt a[i] + \frac{a[j] - a[i]}{2}$. Therefore, further we will be interested only in the numbers from the segment $\left[a[i], a[i] + \frac{a[j] - a[i]}{2}\right]$.
    299 
    300 Let's note that we have reduced the length of the segment by $2$ times. That is, there will be no more such iterations than $\mathcal{O}(\log n)$. You can find the rightmost number belonging to a segment using the segment tree. The answer for the segment $l_i, r_i$ will be $\underset{l_i\leqslant j \lt r}{\min} dp[l]$ at the moment $r_i$. This can also be efficiently found using the segment tree. The final asymptotics of the solution is $\mathcal{O}(n\log^2 n + q\log n)$.
    301 
    302 There is also a solution for $\mathcal{O}(n\sqrt{n} + q\log q)$ that passes all the tests.
    303 
    304 **Code**
    305 
    306 ```
    307 #include <bits/stdc++.h>
    308 
    309 using namespace std;
    310 
    311 const int inf = 1e9 + 228;
    312 
    313 template<class T, class Fun = function<T(const T &, const T &)>>
    314 struct SegTree {
    315     Fun f;
    316     vector<T> t;
    317     int n;
    318 
    319     SegTree(int sz, const Fun &g, T default_value = T()) : f(g) {
    320         n = 1;
    321         while (n < sz) n <<= 1;
    322         t.resize(n * 2, default_value);
    323     }
    324 
    325     SegTree(vector<T> &a, const Fun &g, T default_value = T()) : SegTree(a.size(), g, default_value) {
    326         for (int i = 0; i < n; ++i) t[i + n] = a[i];
    327         for (int i = n - 1; i >= 1; --i) t[i] = f(t[i << 1], t[i << 1 | 1]);
    328     }
    329 
    330     void upd(int i, T x) {
    331         i += n;
    332         t[i] = f(t[i], x);
    333         for (i >>= 1; i > 1; i >>= 1) t[i] = f(t[i << 1], t[i << 1 | 1]);
    334     }
    335 
    336     T get(int l, int r) {
    337         T resL = t[0], resR = t[0];
    338         for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    339             if (l & 1) resL = f(resL, t[l++]);
    340             if (r & 1) resR = f(t[--r], resR);
    341         }
    342         return f(resL, resR);
    343     }
    344 };
    345 
    346 signed main() {
    347     ios_base::sync_with_stdio(0);
    348     cin.tie(0);
    349 
    350     int n, q;
    351     cin >> n >> q;
    352     vector<int> a(n);
    353     for (int i = 0; i < n; i++) {
    354         cin >> a[i];
    355     }
    356     vector<vector<pair<int, int>>> posts(n);
    357     for (int i = 0; i < q; i++) {
    358         int l, r;
    359         cin >> l >> r;
    360         l--, r--;
    361         posts[r].push_back({l, i});
    362     }
    363     SegTree<int> ind(n + 1, [](int x, int y) { return max(x, y); }, -1);
    364     SegTree<int> dp(n + 1, [](int x, int y) { return min(x, y); }, inf);
    365     vector<int> answer(q);
    366     for (int i = 0; i < n; i++) {
    367         {
    368             int limit = n + 1;
    369             while (true) {
    370                 int j = ind.get(a[i], limit);
    371                 if (j == -1)
    372                     break;
    373                 dp.upd(j, abs(a[j] - a[i]));
    374                 limit = a[i] + (a[j] - a[i] + 1) / 2;
    375             }
    376         }
    377         {
    378             int limit = 0;
    379             while (true) {
    380                 int j = ind.get(limit, a[i]);
    381                 if (j == -1)
    382                     break;
    383                 dp.upd(j, abs(a[j] - a[i]));
    384                 limit = a[i] - (a[i] - a[j] + 1) / 2 + 1;
    385             }
    386         }
    387         ind.upd(a[i], i);
    388         for (pair<int, int> j: posts[i]) {
    389             answer[j.second] = dp.get(j.first, i);
    390         }
    391     }
    392     for (int i: answer) {
    393         cout << i << "\n";
    394     }
    395 
    396     return 0;
    397 }
    398 ```