codeforces-scrape

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

2220.md (6165B)


      1 Source: https://codeforces.com/blog/entry/152936
      2 
      3 Thanks everybody for participating in the round!
      4 
      5 ### [Div2A. Blocked](https://codeforces.com/contest/2220/problem/A)
      6 
      7 Author: [misteg168](/profile/misteg168 "International Master misteg168") Preparation: [misteg168](/profile/misteg168 "International Master misteg168")
      8 
      9 **Hint1**
     10 
     11 What happens when there are two equal elements?
     12 
     13 **Solution**
     14 
     15 Tutorial is loading...
     16 
     17 **Code**
     18 
     19 ```
     20 #include <bits/stdc++.h>
     21 using namespace std;
     22  
     23 void solve() {
     24 	int n;
     25 	cin >> n;
     26 	vector<int> a(n);
     27 	for (auto &x : a)
     28 		cin >> x;
     29 		
     30 	sort(a.rbegin(), a.rend());
     31 	
     32 	for (int i = 0; i < n-1; i++)
     33 		if (a[i] == a[i+1]) {
     34 			cout << "-1\n";
     35 			return;
     36 		}
     37 	
     38 	for (auto x : a)
     39 		cout << x << " ";
     40 	cout << "\n";
     41 }
     42  
     43 int main() {
     44 	int T;
     45 	cin >> T;
     46 	while (T--)
     47 		solve();
     48 }
     49 ```
     50 
     51 ### [Div2B. OIE excursion](https://codeforces.com/contest/2220/problem/B)
     52 
     53 Author: [danx](/profile/danx "Master danx") Preparation: [danx](/profile/danx "Master danx")
     54 
     55 **Solution**
     56 
     57 Tutorial is loading...
     58 
     59 **Code**
     60 
     61 ```
     62 #pragma GCC optimize ("O3")
     63 #include <bits/stdc++.h>
     64 using namespace std;
     65  
     66 int t, n, m;
     67  
     68 int main() {
     69     
     70     int t; cin >> t;
     71     while(t--) {
     72         int n, m; cin >> n >> m;
     73         
     74         int c, cnt, mx = 1;
     75         
     76         for(int i = 0; i < n; i++) {
     77             int a; cin >> a;
     78             
     79             if (!i) {
     80                 c = a;
     81                 cnt = 1;
     82             }
     83             else if (a != c) {
     84                 c = a;
     85                 mx = max(mx, cnt);
     86                 cnt = 1;
     87             }
     88             else {
     89                 cnt++;
     90             }
     91         }
     92         
     93         mx = max(mx, cnt);
     94         
     95         if(mx < m) cout << "YES" << "\n";
     96         else cout << "NO" << "\n";
     97     }
     98     
     99     return 0;
    100 }
    101 ```
    102 
    103 ### [Div1A Grid-L](https://codeforces.com/contest/2219/problem/A)
    104 
    105 Author: [rlidon2006](/profile/rlidon2006 "Master rlidon2006") Preparation: [misteg168](/profile/misteg168 "Master misteg168")
    106 
    107 **Hint1**
    108 
    109 We want an easy to check condition on $m$, $n$, $p$, $q$ that is equivalent to being able to fill the grid.
    110 
    111 **Hint2 (strong spoiler)**
    112 
    113 You can fill the $m\times n$ grid if and only if $p+2q = m(n+1)+n(m+1)$ and $p\ge \vert m-n\vert$. (See tutorial for proof)
    114 
    115 **Hint3**
    116 
    117 $p+2q = m(n+1) + n(m+1)$ is quadratic on $m$ and $n$. If you assume $m\ge n$, can you say anything on the size of $n$?
    118 
    119 **Solution**
    120 
    121 Tutorial is loading...
    122 
    123 **Code**
    124 
    125 [370969986](/contest/2219/submission/370969986 "Submission 370969986 by NanYan")
    126 
    127 ### [Div1B Unique values](https://codeforces.com/contest/2219/problem/B1)
    128 
    129 Author: [misteg168](/profile/misteg168 "International Master misteg168") Preparation: [misteg168](/profile/misteg168 "International Master misteg168")
    130 
    131 **Solution B1**
    132 
    133 Tutorial is loading...
    134 
    135 **Code**
    136 
    137 [371019251](/contest/2219/submission/371019251 "Submission 371019251 by tourist")
    138 
    139 **Solution B2**
    140 
    141 Tutorial is loading...
    142 
    143 **Code**
    144 
    145 [371035963](/contest/2219/submission/371035963 "Submission 371035963 by Baskot")
    146 
    147 ### [Div1C](https://codeforces.com/contest/2219/problem/C)
    148 
    149 Author: [misteg168](/profile/misteg168 "Master misteg168") Preparation: [misteg168](/profile/misteg168 "Master misteg168")
    150 
    151 **Hint1**
    152 
    153 Think of some kind of subtree DP.
    154 
    155 **Solution**
    156 
    157 Tutorial is loading...
    158 
    159 **Code**
    160 
    161 [370987541](/contest/2219/submission/370987541 "Submission 370987541 by NanYan")
    162 
    163 ### [Div1D. MEX Replacement on Tree](https://codeforces.com/contest/2219/problem/D)
    164 
    165 Author: [Misuki](/profile/Misuki "Grandmaster Misuki") Preparation: [Misuki](/profile/Misuki "Grandmaster Misuki")
    166 
    167 **Hint1**
    168 
    169 Having a good visual image of the problem in mind may help. That is, for each vertex, thinking there is an array of infinite slot, and some of them are occupied by token, and the operation correspond to moving certain token to the first hole.
    170 
    171 **Hint2**
    172 
    173 Draw some small cases! What would these infinite arrays change when doing operation on root?
    174 
    175 **Hint3**
    176 
    177 Doing operation on vertex with $p_v \lt f(v)$ is useless. Consider the rest situations.
    178 
    179 **Hint4**
    180 
    181 when doing operation on $v$, how would $f(x)$ change if $x$ is in subtree of $v$?
    182 
    183 **Hint5**
    184 
    185 There are two cases, $f(x) = f(v)$ and $f(x) \gt f(v)$.
    186 
    187 **Hint6**
    188 
    189 Solve <https://judge.yosupo.jp/problem/vertex_add_subtree_sum>
    190 
    191 **Solution**
    192 
    193 Tutorial is loading...
    194 
    195 **Code**
    196 
    197 [371007707](/contest/2219/submission/371007707 "Submission 371007707 by NanYan")
    198 
    199 ### [DivE. Weird Chessboard](https://codeforces.com/contest/2219/problem/E)
    200 
    201 Author: [rlidon2006](/profile/rlidon2006 "Master rlidon2006") Preparation: [misteg168](/profile/misteg168 "Master misteg168"), [rlidon2006](/profile/rlidon2006 "Master rlidon2006")
    202 
    203 **Hint1**
    204 
    205 Can you rewrite the condition on the board to something simpler?
    206 
    207 **Hint2**
    208 
    209 Label the board $v_{i,j}$ where $v_{0,0}$ is the top left cell. We work mod $2$. A board $v_{i,j}$ is valid if and only if $v_{i,j}+v_{i+1,j}+v_{i,j+1}=0$ and all entries above the secondary diagonal are zero.
    210 
    211 **Hint3**
    212 
    213 Warm up: try to get a construction of density $1/4$.
    214 
    215 **Hint4**
    216 
    217 The next few hints get quite spoilery. If you don't want to see them yet but are stuck, consider coding some kind of heuristic (say, simulated annealing or A*) and running it on small values of $n$ to see what the result looks like.
    218 
    219 **Hint5**
    220 
    221 Prove that the density is at most $1/3$.
    222 
    223 **Hint6**
    224 
    225 Consider the grid $w_{i,j}$ with $w_{i,j}=1$ when $i+j\ge n-1$ and $i\not\equiv j\pmod 3$, and $w_{i,j}=0$ otherwise.
    226 
    227 **Hint7**
    228 
    229 This grid is almost valid: $v_{i,j}+v_{i+1,j}+v_{i,j+1}=1$ only for very few concrete positions $(i,j)$. Try to fix the issues at those positions in a way that does not disturb much of the grid.
    230 
    231 **Hint8**
    232 
    233 For each position $(i_0, j_0)$ on the diagonal where $w_{i_0,j_0} = 0$, we want to add a pattern to the grid that fixes the issues there.
    234 
    235 **Hint9**
    236 
    237 For each such $(i_0,j_0)$, flip $w_{i_0,j_0}$ and add a Pascal triangle mod $2$ to the grid.
    238 
    239 **Hint10**
    240 
    241 To implement this in $O(n^2)$, instead of adding each pascal independently, try to compute the sum of all of the pascals directly.
    242 
    243 **Solution**
    244 
    245 Tutorial is loading...
    246 
    247 **Code**
    248 
    249 [371015865](/contest/2219/submission/371015865 "Submission 371015865 by tourist")