1617.md (20523B)
1 Source: https://codeforces.com/blog/entry/97920 2 3 Thanks for participating, hope you enjoyed the problems! Implementations for the problems are chosen randomly among testers, and I made some changes to their codes (for example, deleted meaningless comment lines). Please do not hesitate to provide feedback in the comments, so I can improve in setting problems next time. 4 5 **UPD**: Sorry but there is a checker bug in problem E. All submissions of problem E will be rejudged soon. 6 7 **UPD2:** Rejudge done, the round remains rated. 8 9 **Statistics** 10 11 Number of FST for rated participants: 12 13 * Problem A: $29$ 14 * Problem B: $90$ 15 * Problem C: $12$ 16 * Problem D1: $4$ 17 * Problem D2: $0$ 18 * Problem E: $6$ 19 20 Number of AK: $22$ 21 22 Number of clarifications: $85$ 23 24 [1617A - Forbidden Subsequence](/contest/1617/problem/A "Codeforces Round 761 (Div. 2)") 25 26 **Hint** 27 28 When is the lexicographically smallest permutation of $S$ (i.e. the sorted string) not the answer? 29 30 **Solution** 31 32 If there are no occurrences of `a`, `b` or `c` in $S$, sort $S$ and output it. 33 34 Else, if $T \ne$ `abc`, sort $S$ and output it. 35 36 Else, output all `a`, then all `c`, then all `b`, then the rest of the string sorted. 37 38 **Implementation (C++, I_Love_YrNameCouldBeHere)** 39 40 ``` 41 #include <bits/stdc++.h> 42 using namespace std; 43 #define all(x) x.begin(), x.end() 44 int main() { 45 int T; 46 cin >> T; 47 while(T--) { 48 string s, t; 49 cin >> s >> t; 50 sort(all(s)); 51 vector<int> cnt(26, 0); 52 for(auto x: s)cnt[x - 'a']++; 53 if(t != "abc" || !cnt[0] || !cnt[1] || !cnt[2])cout << s << "\n"; 54 else{ 55 while(cnt[0]--)cout<<"a"; 56 while(cnt[2]--)cout<<"c"; 57 while(cnt[1]--)cout<<"b"; 58 for(int i = 3;i < 26; ++i){ 59 while(cnt[i]--)cout<<char('a' + i); 60 } 61 cout << "\n"; 62 } 63 } 64 } 65 ``` 66 67 **Fun fact** 68 69 Originally, the author and two testers' solutions are all wrong, but we didn't notice until the third tester submitted the real correct solution. 70 71 [1617B - GCD Problem](/contest/1617/problem/B "Codeforces Round 761 (Div. 2)") 72 73 **Hint** 74 75 There must exist a solution for $c=1$ under the given constraints. 76 77 **Solution** 78 79 Key observation: there always exists a solution with $c = 1$ under the given constraints. We set $n \ge 10$ because there is no solution when $1 \le n \le 5$ or $n = 7$. 80 81 Solution 1: Brute force from $a = 2, 3, 4, \dots$ and calculate the value of $b$ ($b = n - a - 1$), then check whether $gcd(a, b) = 1$. It works, because you will find a prime number $p \le 29$ such that $n-1$ does not divide $p$. 82 83 Solution 2: Randomly choose $a$ and calculate $b$ ($b = n - a - 1$). Repeating that for enough times will eventually get you a pair of ($a, b$) such that $gcd(a, b) = 1$. 84 85 Solution 3: Constructive solution. 86 87 * When $n \equiv 0 \pmod 2$, output ($n-3, 2, 1$). 88 * When $n \equiv 1 \pmod 4$, output ($\left \lfloor \frac{n}{2} \right \rfloor -1, \left \lfloor \frac{n}{2} \right \rfloor +1, 1$). 89 * When $n \equiv 3 \pmod 4$, output ($\left \lfloor \frac{n}{2} \right \rfloor -2, \left \lfloor \frac{n}{2} \right \rfloor +2, 1$). 90 91 **Implementation (Solution 1, Java, SecondThread)** 92 93 ``` 94 import java.io.BufferedReader; 95 import java.io.IOException; 96 import java.io.InputStreamReader; 97 import java.util.ArrayList; 98 import java.util.Collections; 99 import java.util.StringTokenizer; 100 import java.util.Scanner; 101 102 public class B { 103 104 public static void main(String[] args) { 105 Scanner fs = new Scanner(System.in); 106 int T=fs.nextInt(); 107 for (int tt=0; tt<T; tt++) { 108 int n=fs.nextInt(); 109 for (int target=2; true; target++) { 110 if (gcd(n-1-target, target)!=1) 111 continue; 112 System.out.println(n-1-target+" "+target+" "+1); 113 if (n-1-target<=1) throw null; 114 break; 115 } 116 } 117 } 118 119 static int gcd(int a, int b) { 120 return b==0?a:gcd(b, a%b); 121 } 122 123 static void sort(int[] a) { 124 ArrayList<Integer> l=new ArrayList<>(); 125 for (int i:a) l.add(i); 126 Collections.sort(l); 127 for (int i=0; i<a.length; i++) a[i]=l.get(i); 128 } 129 130 } 131 ``` 132 133 **Implementation (Solution 2, C++, dbsic211)** 134 135 ``` 136 #include <bits/stdc++.h> 137 using namespace std; 138 mt19937 rng((int)std::chrono::steady_clock::now().time_since_epoch().count()); 139 void solve(int tc) { 140 int n; 141 cin >> n; 142 while(1) { 143 int k = uniform_int_distribution<int>(2, n-2)(rng); 144 int l = n-k-1; 145 if(k != l && k != 1 && l != 1 && gcd(k, l) == 1) { 146 cout << k << ' ' << l << ' ' << 1 << endl; 147 break; 148 } 149 } 150 } 151 152 int main() { 153 int t; 154 cin >> t; 155 for(int i=1; i<=t; i++) { 156 solve(i); 157 } 158 } 159 ``` 160 161 **Implementation (Solution 3, C++, anthony123)** 162 163 ``` 164 #include <bits/stdc++.h> 165 using namespace std; 166 void solve(){ 167 int n; 168 cin>>n; 169 if (n%2==0) cout<<"2 "<<(n-1)-2<<" 1\n"; 170 else { 171 int cur=(n-1)/2; 172 if (cur%2==0) cout<<cur-1<<" "<<cur+1<<" "<<1<<endl; 173 else cout<<cur-2<<" "<<cur+2<<" "<<1<<endl; 174 } 175 } 176 signed main(){ 177 int t; 178 cin>>t; 179 while (t--) solve(); 180 } 181 ``` 182 183 [1617C - Paprika and Permutation](/contest/1617/problem/C "Codeforces Round 761 (Div. 2)") 184 185 **Hint 1** 186 187 For any two positive integers $x$, $y$ that satisfy $x \ge y$, what is the maximum value of $x \bmod y$? 188 189 **Hint 2** 190 191 Consider the following input: $n = 4$, $a = [3, 3, 10, 10]$. Sometimes, we don't need to do anything to some $a_i$. When do we have to make operations, and when do we not have to? 192 193 **Solution** 194 195 Key observation: $x \bmod y \lt \frac{x}{2}$ if $x \ge y$, and $x \bmod y = x$ if $x \lt y$. 196 197 Notice that the bigger the $x$, the bigger the range of values that can be obtained after one $\bmod$ operation. So, intuitively, we want to assign smaller $a_i$ to smaller numbers in the resulting permutation. 198 199 However, if $a_i$ satisfies $1 \le a_i \le n$, we can just leave it there and use it in the resulting permutation (if multiple $a_i$ satisfy $1 \le a_i \le n$ and have the same value, just choose one). Let's suppose in the optimal solution, we change $x$ to $y$ and change $z$ to $x$ for some $z \gt x \gt y$ ($x$, $y$, $z$ are values, not indices). Then changing $x$ to $x$ (i.e. doing nothing) and changing $z$ to $y$ uses $1$ less operation. And, if it is possible to change $z$ to $x$, then it must be possible to change $z$ to $y$. However, if it is not possible to change $z$ to $x$, it might still be possible to change $z$ to $y$. 200 201 Therefore, the solution is as follows: Sort the array. For each element $i$ in the sorted array: 202 203 * If $1 \le a_i \le n$ and it is the first occurrence of element with value $a_i$, leave it there. 204 * Else, let the current least unassigned value in the resulting permutation be $m$, if $m \lt \frac{a_i}{2}$, we can assign the current element to value $m$ and add the number of operations by $1$. Else, output $-1$ directly. 205 206 The solution works in $O(n \log n)$. 207 208 **Implementation (C++, physics0523)** 209 210 ``` 211 #include<bits/stdc++.h> 212 using namespace std; 213 int main(){ 214 ios::sync_with_stdio(false); 215 cin.tie(nullptr); 216 int t; 217 cin >> t; 218 while(t>0){ 219 t--; 220 int n; 221 cin >> n; 222 set<int> st; 223 for(int i=1;i<=n;i++){st.insert(i);} 224 vector<int> rem; 225 for(int i=0;i<n;i++){ 226 int v; 227 cin >> v; 228 if(st.find(v)!=st.end()){st.erase(v);} 229 else{rem.push_back(v);} 230 } 231 sort(rem.begin(),rem.end()); 232 reverse(rem.begin(),rem.end()); 233 int pt=0; 234 bool err=false; 235 for(auto &nx : rem){ 236 auto it=st.end(); 237 it--; 238 int ctg=(*it); 239 if(ctg>(nx-1)/2){err=true;break;} 240 st.erase(it); 241 } 242 if(err){cout << "-1\n";} 243 else{cout << rem.size() << '\n';} 244 } 245 return 0; 246 } 247 ``` 248 249 [1617D1 - Too Many Impostors (easy version)](/contest/1617/problem/D1 "Codeforces Round 761 (Div. 2)") 250 251 **Hint 1** 252 253 The weird constraint, $\frac{n}{3} \lt k \lt \frac{2n}{3}$, is crucial. 254 255 **Hint 2** 256 257 If you know the index of one crewmate and one impostor, how to find the roles of other $n-2$ players in exactly $n-2$ queries? 258 259 **Hint 3** 260 261 Query players ($1, 2, 3$), ($2, 3, 4$), $\dots$, ($n-1, n, 1$), ($n, 1, 2$). After that, you can surely find out the index of one crewmate and one impostor. Try to find out how. 262 263 **Solution** 264 265 Key observation: if result of query ($a, b, c$) $\ne$ result of query ($b, c, d$), since $b$ and $c$ are common, players $a$ and $d$ have different roles. Additionally, if result of query ($a, b, c$) = $1$ then player $a$ is a crewmate (and player $d$ is an impostor), vice versa. 266 267 The first step is to query players ($1, 2, 3$), ($2, 3, 4$), $\dots$, ($n-1, n, 1$), ($n, 1, 2$). 268 269 If the results of any two adjacent queries (or queries ($1, 2, 3$) and ($n, 1, 2$)) are different, we instantly know the roles of the two players that are only included in one query — one is a crewmate, one is an impostor. Since the number of impostors $k$ and crewmates $n-k$ satisfy $k \gt \frac{n}{3}$ and $n - k \gt \frac{n}{3}$, there must be one pair of adjacent queries that are different. 270 271 After we know one crewmate and one impostor (let's call them $a$, $d$), we can query these two players with each one of the rest of the players. If a query ($a, d, x$) ($1 \le x \le n$, $x \ne a$ and $x \ne d$) returns $0$, player $x$ is an impostor, else player $x$ is a crewmate. 272 273 In total, $2n-2$ queries are used. 274 275 **Implementation (C++, dbsic211)** 276 277 ``` 278 #include <bits/stdc++.h> 279 using namespace std; 280 void solve() { 281 int N; 282 cin >> N; 283 int res[N]; 284 for(int i=0; i<N; i++) { 285 cout << "? " << i + 1 << " " << (i+1) % N + 1 << " " << (i+2) % N + 1 << endl; 286 cin >> res[i]; 287 } 288 vector<int> imp; 289 for(int i=0; i<N; i++) { 290 if(res[i] != res[(i+1) % N]) { 291 if(res[i] == 0) imp.push_back(i + 1); 292 else imp.push_back((i+3) % N + 1); 293 for(int j=0; j<N; j++) { 294 if(j != i && j != (i+3) % N) { 295 cout << "? " << i + 1 << " " << (i+3) % N + 1 << " " << j + 1 << endl; 296 int r; 297 cin >> r; 298 if(r == 0) imp.push_back(j + 1); 299 } 300 } 301 break; 302 } 303 } 304 cout << "! " << imp.size(); 305 for(int x : imp) cout << " " << x; 306 cout << endl; 307 } 308 int main() { 309 int T; 310 cin >> T; 311 for(int i=1; i<=T; i++) { 312 solve(); 313 } 314 } 315 ``` 316 317 [1617D2 - Too Many Impostors (hard version)](/contest/1617/problem/D2 "Codeforces Round 761 (Div. 2)") 318 319 Thanks must be given to [arvindf232](/profile/arvindf232 "Grandmaster arvindf232") and [generic_placeholder_name](/profile/generic_placeholder_name "Master generic_placeholder_name") for the solution. 320 321 **Hint 1** 322 323 Aim to find an impostor and a crewmate's index in $\frac{n}{3} + c$ queries, with $c$ being a small constant. 324 325 **Hint 2** 326 327 Consider splitting the $n$ players into groups of $3$ (and query each group) in order to reach the goal in Hint 1. What is special about the results of the $\frac{n}{3}$ queries? 328 329 **Solution (Step 1)** 330 331 Firstly query ($1, 2, 3$), ($4, 5, 6$), $\dots$, ($n-2, n-1, n$). Due to the constraint $\frac{n}{3} \lt k \lt \frac{2n}{3}$, among the results of these $\frac{n}{3}$ queries, there must be at least one $0$ and one $1$. Now, let's call a tuple ($a, b, c$) that returns $0$ a $0$-majority tuple, and vice versa. 332 333 From the easy version, notice that finding one crewmate and one impostor is very helpful in determining the roles of the remaining players. Let's make use of the above observation, and pick one adjacent $0$-majority tuple and $1$-majority tuple. 334 335 Let's say we picked ($i, i+1, i+2$) and ($i+3, i+4, i+5$). Then, we query ($i+1, i+2, i+3$) and ($i+2, i+3, i+4$). Among the four queries ($i, i+1, i+2$), ($i+1, i+2, i+3$), ($i+2, i+3, i+4$), ($i+3, i+4, i+5$), there must be a pair of adjacent queries with different results. From the easy version, we can directly find the index of an impostor and a crewmate. 336 337 In all the above cases, we end up knowing an impostor and a crewmate using $\frac{n}{3} + 2$ queries, including the first step. 338 339 **Hint 3** 340 341 You have the index of an impostor and a crewmate now, and around $\frac{2n}{3}$ queries left. 342 343 Consider using at most $2$ queries to find out roles of each player in each group of $3$ from Step 1, which should add up to $\frac{2n}{3}$ queries. 344 345 Make use of the information you know about each group (whether it is $0$-majority or $1$-majority). 346 347 **Hint 4** 348 349 Assume a tuple (group of $3$) is $0$-majority. There are $4$ possibilities of roles of the $3$ players in the tuple, which are: 350 351 * impostor, impostor, impostor 352 * crewmate, impostor, impostor (and its permutations) 353 354 In each query, reduce half of the possibilities. 355 356 **Solution (Step 2)** 357 358 It remains to figure out how we can find the roles of the remaining players using $\frac{2n}{3}$ queries. For each tuple ($i, i+1, i+2$) queried in the first step, let's assume the tuple is $0$-majority (because the other case can be solved similarly). Then, there are only four possibilities: 359 360 * All players $i$, $i+1$, $i+2$ are impostors. 361 * Player $i$ is a crewmate, players $i+1$, $i+2$ are impostors. 362 * Player $i+1$ is a crewmate, players $i$, $i+2$ are impostors. 363 * Player $i+2$ is a crewmate, players $i$, $i+1$ are impostors. 364 365 Earlier, we found the index of a crewmate and an impostor, let the index of the crewmate be $a$ and the impostor be $b$. 366 367 If the tuple ($i, i+1, a$) is $1$-majority, either player $i$ or player $i+1$ is a crewmate. So, we reduced the number of possibilities to $2$. To check which player is the crewmate, query it with $a$ and $b$ like we did in the easy version. 368 369 Else, either there are no crewmates or player $i+2$ is a crewmate. So, we reduced the number of possibilities to $2$. To check the role of player $i+2$, query it with $a$ and $b$ like we did in the easy version. 370 371 In both cases, we use $2$ queries for each initial tuple ($i, i+1, i+2$). So, we used $n + 2$ queries in total, but we gave you a bit more, in case you used some more queries to find a crewmate and an impostor. 372 373 There is one corner case we should handle: if the tuple ($i, i+1, i+2$) contains $a$ or $b$, we can just naively query for each unknown role in the tuple, since we won't use more than $2$ queries anyway. 374 375 **Implementation (C++, dbsic211)** 376 377 ``` 378 #include <bits/stdc++.h> 379 using namespace std; 380 int query(int a, int b, int c) { 381 cout << "? " << a << ' ' << b << ' ' << c << endl; 382 int r; cin >> r; 383 return r; 384 } 385 void solve(int tc) { 386 int n; cin >> n; 387 int a[n+1], role[n+1]; 388 for(int i=1; i+2<=n; i+=3) a[i] = query(i, i+1, i+2); 389 int imp, crew; 390 for(int i=1; i<=n; i++) role[i] = -1; 391 for(int i=1; i+5<=n; i+=3) { 392 if(a[i] != a[i+3]) { 393 a[i+1] = query(i+1, i+2, i+3), a[i+2] = query(i+2, i+3, i+4); 394 for(int j=i; j<i+3; j++) { 395 if(a[j] != a[j+1]) { 396 if(a[j] == 0) { 397 imp = j, crew = j+3; 398 role[j] = 0, role[j+3] = 1; 399 } 400 else { 401 imp = j+3, crew = j; 402 role[j+3] = 0, role[j] = 1; 403 } 404 } 405 } 406 break; 407 } 408 } 409 for(int i=1; i+2<=n; i+=3) { 410 if(i == imp || i+1 == imp || i+2 == imp || i == crew || i+1 == crew || i+2 == crew) { 411 for(int j=i; j<i+3; j++) { 412 if(role[j] == -1) { 413 role[j] = query(imp, crew, j); 414 } 415 } 416 } 417 else if(a[i] == 0) { 418 if(query(i, i+1, crew) == 1) { 419 if(query(i, imp, crew) == 0) role[i] = 0, role[i+1] = 1; 420 else role[i] = 1, role[i+1] = 0; 421 role[i+2] = 0; 422 } 423 else { 424 role[i] = role[i+1] = 0; 425 role[i+2] = query(i+2, imp, crew); 426 } 427 } 428 else { 429 if(query(i, i+1, imp) == 0) { 430 if(query(i, imp, crew) == 0) role[i] = 0, role[i+1] = 1; 431 else role[i] = 1, role[i+1] = 0; 432 role[i+2] = 1; 433 } 434 else { 435 role[i] = role[i+1] = 1; 436 role[i+2] = query(i+2, imp, crew); 437 } 438 } 439 } 440 cout << "! "; 441 queue<int> q; 442 for(int i=1; i<=n; i++) if(role[i] == 0) q.push(i); 443 cout << q.size(); 444 while(q.size()) { 445 cout << " " << q.front(); 446 q.pop(); 447 } 448 cout << endl; 449 } 450 int main() { 451 int T; cin >> T; 452 for(int i=1; i<=T; i++) solve(i); 453 } 454 ``` 455 456 [1617E - Christmas Chocolates](/contest/1617/problem/E "Codeforces Round 761 (Div. 2)") 457 458 **Hint 1** 459 460 Translate the problem into a graph problem. What feature of the graph is it asking about? 461 462 **Hint 2** 463 464 Draw out the graph, for $a_i \le 10$. What special property does the graph have? 465 466 **Hint 3** 467 468 Any specific algorithm to solve the problem (in Hint 1)? 469 470 **Solution (Step 1)** 471 472 In graph terms, the problem is as follows: in a graph with infinite nodes, two nodes $x$ and $y$ are connected if $x + y = 2^k$ for some $k \ge 0$. Among $n$ special nodes, find the pair of nodes ($i, j$) with maximum shortest distance. 473 474 Here comes the key observation: For any $i \ge 1$, there exists only one $j$ ($0 \le j \lt i$) such that $i + j = 2^k$ for some $k \ge 0$. 475 476 The proof is as follows: let's say that $0 \le j_1, j_2 \lt i$, $j_1 \ge j_2$, $i + j_1 = 2^{k_1}$, $i + j_2 = 2^{k_2}$. Then, $j_1 - j_2 = 2^{k_2} \cdot (2^{k_1-k_2} - 1)$. So, $j_1 \equiv j_2 \pmod {2^{k_2}}$. Since $i \le 2^{k_2}$, $j_1 = j_2$. 477 478 Then, we realize we can build a graph as follows: add an edge between $x$ and $y$ ($x, y \ge 0$) if $x + y = 2^k$ for some $k \ge 0$. Because of the first key observation, the graph must be **a tree**. We can root the tree at node $0$. 479 480 Our problem is equivalent to finding the pair of nodes which have maximum distance in a tree, which can be solved using the diameter of tree algorithm. 481 482 **Hint 4** 483 484 We can't build the entire tree as it has $10^9 + 1$ nodes. Try to notice something about the depth of the tree, then think of how this could help us solve the problem (by building the tree, or otherwise). 485 486 **Solution (Step 2)** 487 488 Since $0 \le a_i \le 10^9$, it is impossible to build the entire tree. A final observation is that: Consider any node $v$ with degree $\ge 2$ in the tree, then $v \gt p_v$ and $p_v \gt p_{p_v}$, therefore $v + p_v \gt p_v + p_{p_v}$ ($p_x$ denotes the parent of node $x$ in the tree). 489 490 Hence the depth of the tree is $\lceil \log(max(a_i)) \rceil = 30$, since there are only $\lceil \log(max(a_i)) \rceil$ possible $k$ ($0 \le k \lt 30$) for the sum of two nodes connected by an edge. 491 492 So, there are two ways to do it: the first way is to build parts of the tree: only the $n$ given nodes and the ancestors of the $n$ nodes. There will be at most $O(n \log max(a_i))$ nodes, which should fit into the memory limit. The second way is to not build the tree at all, and calculate the LCA (Lowest Common Ancestor) of two nodes to find their distance. Since the depth of the tree is $30$, LCA of two nodes can be computed by simply checking every ancestor of both nodes. 493 494 In both ways, the time complexity is $O(n \log max(a_i))$. 495 496 **Implementation (C++, physics0523)** 497 498 ``` 499 #include<bits/stdc++.h> 500 using namespace std; 501 502 int f(int x){ 503 for(int i=0;;i++){ 504 if((1<<i)>=x){ 505 return (1<<i)-x; 506 } 507 } 508 } 509 510 using pi=pair<int,int>; 511 int main(){ 512 ios::sync_with_stdio(false); 513 cin.tie(nullptr); 514 int n; 515 cin >> n; 516 map<int,pair<pi,pi>> mp; 517 priority_queue<int> pq; 518 for(int i=0;i<n;i++){ 519 int v; 520 cin >> v; 521 pq.push(v); 522 mp[v].first=make_pair(0,i+1); 523 } 524 while(!pq.empty()){ 525 int od=pq.top();pq.pop(); 526 if((!pq.empty()) && od==pq.top()){continue;} 527 if(od!=1){ 528 int nx=f(od); 529 pq.push(nx); 530 pi send=mp[od].first; 531 send.first++; 532 if(mp[nx].first<send){ 533 mp[nx].second=mp[nx].first; 534 mp[nx].first=send; 535 } 536 else if(mp[nx].second<send){mp[nx].second=send;} 537 } 538 } 539 int ra=0,rb=0,rc=-1; 540 for(auto &nx : mp){ 541 pair<pi,pi> tg=nx.second; 542 if(tg.first.second==0 || tg.second.second==0){continue;} 543 if(rc<tg.first.first+tg.second.first){ 544 rc=tg.first.first+tg.second.first; 545 ra=tg.first.second; 546 rb=tg.second.second; 547 } 548 } 549 cout << ra << ' ' << rb << ' ' << rc << '\n'; 550 return 0; 551 } 552 ```