codeforces-scrape

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

1798.md (10572B)


      1 Source: https://codeforces.com/blog/entry/114208
      2 
      3 Thank you all for participating, I hope you enjoyed the problems! You can rate the problems of the round in the corresponding spoilers.
      4 
      5 [1798A - Showstopper](/contest/1798/problem/A "Codeforces Round 860 (Div. 2)")
      6 
      7 **Hint 1**
      8 
      9 For each index $i$, it makes no sense to perform the operation $\ge 2$ once, since applying the operation with the same index twice does not change anything.
     10 
     11 **Hint 2**
     12 
     13 Condition $a_n = \max(a_1, a_2, \ldots, a_n)$ is equivalent to $a_i \leq a_n$ for all $i$. So for each index $i$ there are only 2 conditions: $a_i \leq a_n$ and $b_i \leq b_n$.
     14 
     15 **Tutorial**
     16 
     17 Tutorial is loading...
     18 
     19 **Solution**
     20 
     21 ```
     22 for _ in range(int(input())):
     23     n = int(input())
     24     a = list(map(int, input().split()))
     25     b = list(map(int, input().split()))
     26     for i in range(n):
     27         if a[i] > b[i]:
     28             a[i], b[i] = b[i], a[i]
     29     if a[-1] == max(a) and b[-1] == max(b):
     30         print("YES")
     31     else:
     32         print("NO")
     33 ```
     34 
     35 **Rate the problem**
     36 
     37 * Didnt solve
     38 * Good problem
     39 * Average problem
     40 * Bad problem
     41 
     42 [1798B - Three Sevens](/contest/1798/problem/B "Codeforces Round 860 (Div. 2)")
     43 
     44 **Hint 1**
     45 
     46 Let the participant with the number $X$ participate in the lottery in days $i_1 \lt i_2 \lt \ldots \lt i_k$. On what days could the participant $X$ be chosen as the winner so as not to break the conditions?
     47 
     48 **Hint 2**
     49 
     50 If there are several candidates for the lottery winner on the day of $i$ (who did not participate in the days from $i+1$ to $m$), does it matter which of them we choose as a winner?
     51 
     52 **Tutorial**
     53 
     54 Tutorial is loading...
     55 
     56 **Solution**
     57 
     58 ```
     59 MAX = 50000
     60 last = [0] * (MAX + 777)
     61 for _ in range(int(input())):
     62     m = int(input())
     63     a_ = []
     64     for day in range(m):
     65         n = int(input())
     66         a = list(map(int, input().split()))
     67         for x in a:
     68             last[x] = day
     69         a_.append(a)
     70     ans = [-1] * m
     71     for day in range(m):
     72         for x in a_[day]:
     73             if last[x] == day:
     74                 ans[day] = x
     75         if ans[day] == -1:
     76             print(-1)
     77             break
     78     else:
     79         print(*ans)
     80 ```
     81 
     82 **Rate the problem**
     83 
     84 * Didnt solve
     85 * Good problem
     86 * Average problem
     87 * Bad problem
     88 
     89 [1798C - Candy Store](/contest/1798/problem/C "Codeforces Round 860 (Div. 2)")
     90 
     91 **Hint 1**
     92 
     93 In which case 1 price tag is enough?
     94 
     95 **Hint 1.1**
     96 
     97 For any positive integers $x, y, z$, the statement ``$x$ is divisible by $y$'' equivalent to the statement ``$xz$ is divisible by $yz$'
     98 
     99 **Hint 1.2**
    100 
    101 Let's denote the total cost of all packs of candies for $cost$. Rewrite all the conditions given in the problem so that they become conditions only for the number $cost$. Hint1.1 will help in this.
    102 
    103 **Hint 2**
    104 
    105 If one price tag is enough for a set of candies, then if you remove any type of candy from this set, one price tag will still be enough. This is a reason to think about greedy.
    106 
    107 **Tutorial**
    108 
    109 Tutorial is loading...
    110 
    111 **Solution**
    112 
    113 ```
    114 from math import gcd
    115  
    116 def lcm(a, b):
    117   return a * b // gcd(a, b)
    118  
    119 for _ in range(int(input())):
    120     n = int(input())
    121     a = []
    122     b = []
    123     for i in range(n):
    124        ai, bi = map(int, input().split())
    125        a.append(ai)
    126        b.append(bi)
    127     g = 0
    128     l = 1
    129     ans = 1
    130     for i in range(n):
    131         g = gcd(g, a[i] * b[i])
    132         l = lcm(l, b[i])
    133         if g % l:
    134             ans += 1
    135             g = a[i] * b[i]
    136             l = b[i]
    137     print(ans)
    138 ```
    139 
    140 **Rate the problem**
    141 
    142 * Didnt solve
    143 * Good problem
    144 * Average problem
    145 * Bad problem
    146 
    147 [1798D - Shocking Arrangement](/contest/1798/problem/D "Codeforces Round 860 (Div. 2)")
    148 
    149 **Hint 1**
    150 
    151 Express $\max\limits_{1 \leq l \leq r \leq n} \lvert a_l+a_{l+1}+\ldots+a_r\rvert$ in a simpler way.
    152 
    153 **Hint 1.1**
    154 
    155 Use the prefix sums of the array $a$.
    156 
    157 **Hint 2**
    158 
    159 Build the answer starting from an empty array. If you add numbers to the response so that the prefix sum is always in the half-interval $(\min(a), \max(a)]$, the resulting array will fit the condition. How to do it? Remember that the sum of the array is $0$.
    160 
    161 **Tutorial**
    162 
    163 Tutorial is loading...
    164 
    165 **Solution**
    166 
    167 ```
    168 for _ in range(int(input())):
    169     n = int(input())
    170     a = list(map(int, input().split()))
    171     if max(a) == 0:
    172         print("No")
    173     else:
    174         print("Yes")
    175         prefix_sum = 0
    176         pos = []
    177         neg = []
    178         for x in a:
    179             if x >= 0:
    180                 pos.append(x)
    181             else:
    182                 neg.append(x)
    183         ans = []
    184         for _ in range(n):
    185             if prefix_sum <= 0:
    186                 ans.append(pos[-1])
    187                 pos.pop()
    188             else:
    189                 ans.append(neg[-1])
    190                 neg.pop()
    191             prefix_sum += ans[-1]
    192         print(' '.join(list(map(str, ans))))
    193 ```
    194 
    195 **Rate the problem**
    196 
    197 * Didnt solve
    198 * Good problem
    199 * Average problem
    200 * Bad problem
    201 
    202 [1798E - Multitest Generator](/contest/1798/problem/E "Codeforces Round 860 (Div. 2)")
    203 
    204 **Hint 1**
    205 
    206 Estimate from above the number of changes for which you can make a multitest from an arbitrary array.
    207 
    208 **Hint 2**
    209 
    210 How to check for each suffix whether it is a multitest by itself (without changes)?
    211 
    212 **Hint 2.1**
    213 
    214 This is done using one-dimensional dynamic programming by suffixes.
    215 
    216 **Hint 3**
    217 
    218 Let's say you want to check if an array can turn into a multitest for $1$ change. Find all the elements that could potentially be changed (all the elements are such that changing them could lead to the array becoming a multitest without being it initially). For each of them, you need to determine whether it is possible to make a change that turns array into multitest. One-dimensional dynamic programming by suffixes will help to take into account all these variants of change.
    219 
    220 **Tutorial**
    221 
    222 Tutorial is loading...
    223 
    224 **Solution**
    225 
    226 ```
    227 N = 300777
    228 a = [0] * N
    229 go = [0] * N
    230 good_chain = [0] * N
    231 chain_depth = [0] * N
    232 suf_max_chain_depth = [0] * N
    233 
    234 ans = ""
    235 for _ in range(int(input())):
    236     n = int(input())
    237     a = [0] + list(map(int, input().split()))
    238     chain_depth[n + 1] = 0
    239     suf_max_chain_depth[n + 1] = 0
    240     curr_max_chain_depth = 0
    241     for i in range(n, 0, -1):
    242         go[i] = i + a[i] + 1
    243         if go[i] == n + 1 or (go[i] <= n and good_chain[go[i]]):
    244             good_chain[i] = True
    245         else:
    246             good_chain[i] = False
    247         chain_depth[i] = 1 + chain_depth[min(go[i], n + 1)]
    248         suf_max_chain_depth[i] = 1 + curr_max_chain_depth
    249         if go[i] <= n + 1:
    250             suf_max_chain_depth[i] = max(suf_max_chain_depth[i], 1 + suf_max_chain_depth[go[i]])
    251         if good_chain[i]:
    252             curr_max_chain_depth = max(curr_max_chain_depth, chain_depth[i])
    253     for i in range(1, n):
    254         if good_chain[i + 1] and chain_depth[i + 1] == a[i]:
    255             ans += "0 "
    256         elif good_chain[i + 1] or suf_max_chain_depth[i + 1] >= a[i]:
    257             ans += "1 "
    258         else:
    259             ans += "2 "
    260     ans += '\n'
    261 print(ans)
    262 ```
    263 
    264 **Rate the problem**
    265 
    266 * Didnt solve
    267 * Good problem
    268 * Average problem
    269 * Bad problem
    270 
    271 [1798F - Gifts from Grandfather Ahmed](/contest/1798/problem/F "Codeforces Round 860 (Div. 2)")
    272 
    273 **Hint 1**
    274 
    275 Let's say the box you selected will be sent to the largest class. Then if this class has a size of $s$, you can send any $s-1$ from the available boxes there. So you can not worry about this class, and pick boxes for the rest, always having as potential options $s-1$ additional boxes. Plenty of room for maneuver.
    276 
    277 **Hint 2**
    278 
    279 The solution exists for any valid input
    280 
    281 **Hint 3**
    282 
    283 After Hint2 think about some specific inputs. You know, they always have a solution. This should inspire you.
    284 
    285 **Hint 3.1**
    286 
    287 $k = 2, s_1 = s_2$.
    288 
    289 **Hint 4**
    290 
    291 Erdős--Ginzburg--Ziv theorem
    292 
    293 **Tutorial**
    294 
    295 Tutorial is loading...
    296 
    297 **Solution**
    298 
    299 ```
    300 #include <bits/stdc++.h>
    301  
    302 #define pb push_back
    303 // #define int long long
    304 #define all(x) x.begin(), x.end()
    305 #define ld long double
    306 using namespace std;
    307 const int N = 210;
    308 bool dp[N][N][N];
    309 bool take[N][N][N];
    310  
    311 signed main() {
    312     ios::sync_with_stdio(false);
    313     cin.tie(nullptr);
    314     cout.tie(nullptr);
    315     int n, k;
    316     cin >> n >> k;
    317     vector<int> a(n), s(k);
    318     for (int i = 0; i < n; i++) {
    319         cin >> a[i];
    320     }
    321     for (int i = 0; i < k; i++) {
    322         cin >> s[i];
    323     }
    324     vector<pair<int, int>> s2;
    325     for (int i = 0; i < k; i++) {
    326         s2.pb({s[i], i});
    327     }
    328     sort(all(s2));
    329     vector<vector<int>> ans(k);
    330     for (int i = 0; i < k - 1; i++) {
    331         int class_size = s2[i].first;
    332         vector<int> boxes;
    333         for (int _ = 0; _ < 2 * class_size - 1; _++) {
    334             boxes.pb(a.back());
    335             a.pop_back();
    336         }
    337         for (int sz = 0; sz <= class_size; sz++) {
    338             for (int r = 0; r < class_size; r++) {
    339                 dp[0][sz][r] = false;
    340                 take[0][sz][r] = false;
    341             }
    342         }
    343         dp[0][0][0] = true;
    344         dp[0][1][boxes[0] % class_size] = true;
    345         take[0][1][boxes[0] % class_size] = true;
    346         for (int j = 1; j < (int) boxes.size(); j++) {
    347             for (int sz = 0; sz <= class_size; sz++) {
    348                 for (int r = 0; r < class_size; r++) {
    349                     dp[j][sz][r] = dp[j - 1][sz][r];
    350                     if (sz > 0 && dp[j - 1][sz - 1][(class_size + r - boxes[j] % class_size) % class_size]) {
    351                         dp[j][sz][r] = true;
    352                         take[j][sz][r] = true;
    353                     } else {
    354                         take[j][sz][r] = false;
    355                     }
    356                 }
    357             }
    358         }
    359         vector<bool> used(2 * class_size - 1);
    360         int sz = class_size, r = 0;
    361         for (int j = (int) boxes.size() - 1; j >= 0; j--) {
    362             if (take[j][sz][r]) {
    363                 used[j] = true;
    364                 sz--;
    365                 r += (class_size - boxes[j] % class_size);
    366                 r %= class_size;
    367             } else {
    368                 used[j] = false;
    369             }
    370         }
    371         vector<int> to_class;
    372         for (int j = 0; j < (int) boxes.size(); j++) {
    373             if (!used[j]) {
    374                 a.pb(boxes[j]);
    375             } else {
    376                 to_class.pb(boxes[j]);
    377             }
    378         }
    379         ans[s2[i].second] = to_class;
    380     }
    381  
    382     int sum = 0;
    383     for (auto x : a) {
    384         sum += x;
    385         sum %= (int) (a.size() + 1);
    386     }
    387     int add = (int) (a.size() + 1) - sum;
    388     ans[s2[k - 1].second] = a;
    389     ans[s2[k - 1].second].pb(add);
    390  
    391     cout << add << '\n';
    392     for (auto arr : ans) {
    393         for (auto x : arr) {
    394             cout << x << ' ';
    395         }
    396         cout << '\n';
    397     }
    398 }
    399 ```
    400 
    401 **Rate the problem**
    402 
    403 * Didnt solve
    404 * Good problem
    405 * Average problem
    406 * Bad problem