2135.md (33319B)
1 Source: https://codeforces.com/blog/entry/145796 2 3 **Rate the Contest!** 4 5 * Amazing round: 6 * Good round: 7 * Average round: 8 * Bad round: 9 * Horrible round: 10 11 [2136A - In the Dream](/contest/2136/problem/A "Codeforces Round 1046 (Div. 2)") 12 13 Idea: [Alan_dong](/profile/Alan_dong "Candidate Master Alan_dong") 14 Preparation: [Register](/profile/Register "Master Register") 15 16 **Hint** 17 18 If one team got a score of $x$ in the first half, what is the maximum score the other team could get? 19 20 **Solution** 21 22 We can consider the first half and the second half separately. The dream might come true if and only if the scores in both halves are possible. In the second half, the RiOI team scored $(c - a)$ goals, while the KDOI team scored $(d - b)$ goals. 23 24 Suppose the RiOI team scored $x$ goals in some half. Denoting the score of the KDOI team as $y$, one can see that the maximal value of $y$ is $2\cdot x + 2$, under the goal order $\tt{\color{red}K\color{red}K\color{black}RK\color{red}K\color{black}R...RK\color{red}K\color{black}RK\color{red}K}$. When $y \geq x$, all scores in the range $[x, 2\cdot x+2]$ can be achieved by deleting several $\tt K$-s colored red. 25 26 Therefore, the scores $x: y$ in a single half are possible, if and only if $\max(x, y) \leq 2\cdot \min(x, y) + 2$. 27 28 **Code (C++)** 29 30 ``` 31 #include <bits/stdc++.h> 32 33 using namespace std; 34 35 typedef long long ll; 36 37 int T, a, b, c, d; 38 39 int main() { 40 for (scanf("%d", &T); T--; ) { 41 scanf("%d%d%d%d", &a, &b, &c, &d), c -= a, d -= b; 42 if (a > b) swap(a, b); if (c > d) swap(c, d); 43 puts((a + 1 << 1) >= b && (c + 1 << 1) >= d ? "YES" : "NO"); 44 } 45 } 46 ``` 47 48 **Code (Python)** 49 50 ``` 51 import sys 52 input=sys.stdin.readline 53 54 t=int(input()) 55 for _ in range(t): 56 a,b,c,d=map(int,input().split()) 57 if(max(a,b)>2*min(a,b)+2): 58 print("NO") 59 elif(max(c-a,d-b)>2*min(c-a,d-b)+2): 60 print("NO") 61 else: 62 print("YES") 63 ``` 64 65 **Rate the Problem!** 66 67 * Amazing problem: 68 * Good problem: 69 * Average problem: 70 * Bad problem: 71 * Horrible problem: 72 73 [2136B - Like the Bitset](/contest/2136/problem/B "Codeforces Round 1046 (Div. 2)") 74 75 Idea & Preparation: [_istil](/profile/_istil "International Grandmaster _istil") 76 77 **Hint 1** 78 79 When shall we output $\tt{NO}$? 80 81 **Hint 2** 82 83 We can put larger numbers on indices with $s_i = \tt{0}$, and smaller numbers on indices with $s_i = \tt{1}$. 84 85 **Solution** 86 87 Note that if there is an interval $p_l, \ldots, p_r$ such that $r - l + 1 \geq k$, and $s_l = s_{l+1} = \ldots = s_r = \tt{1}$, then it's impossible to satisfy all the requirements, since by iterating $i$ over $l$ to $r$, there must be some $i$ such that $p_i = \max(p_l, \ldots, p_r)$. 88 89 Otherwise, denote $c$ as the number of occurrences of $\tt{1}$ in the string $s$. We can always construct the permutation by filling the indices $i$ of $s_i = \tt{1}$ with $1$ to $c$ respectively, and indices of $s_i = \tt{0}$ with $(c + 1)$ to $n$ respectively. It works because for every interval $[l, r]$ such that $r - l + 1 \geq k$, there is at least one index $l \leq i \leq r$ such that $s_i = \tt{0}$, and it will be greater than all the indices of $s_i = \tt{1}$. 90 91 Time complexity: $\mathcal O(n)$ per test case. 92 93 **Code (C++)** 94 95 ``` 96 #include <bits/stdc++.h> 97 98 void solve() { 99 int n, k; std::cin >> n >> k; 100 std::string s; std::cin >> s, s = " " + s; 101 for (int i = 1, j = 1; i <= n; i = ++j) if (s[i] == '1') { 102 while (j < n && s[j + 1] == '1') j++; 103 if (j - i + 1 >= k) return (void)puts("NO"); 104 } 105 puts("YES"); 106 int c1 = 0, c2 = std::count_if(s.begin(), s.end(), [&](char ch) -> bool { return ch == '1'; }); 107 for (int i = 1; i <= n; ++i) 108 std::cout << (s[i] == '1' ? ++c1 : ++c2) << " \n"[i == n]; 109 } 110 111 int main() { int t; std::cin >> t; while (t--) solve(); return 0; } 112 ``` 113 114 **Code (Python)** 115 116 ``` 117 import sys 118 input=lambda:sys.stdin.readline().rstrip() 119 for _ in range(int(input())): 120 n,k=map(int,input().split()) 121 s=input() 122 if "1"*k in s: # YES YOU WILL NOT BELIEVE THAT THIS IS O(N) 123 print("No") 124 else: 125 print("Yes") 126 a=sorted(range(0,n),key=lambda i:s[i],reverse=True) 127 ans=[0]*n 128 for i in range(n): 129 ans[a[i]]=i+1 130 print(*ans) 131 ``` 132 133 **Rate the Problem!** 134 135 * Amazing problem: 136 * Good problem: 137 * Average problem: 138 * Bad problem: 139 * Horrible problem: 140 141 [2135A - Against the Difference](/contest/2135/problem/A "Codeforces Round 1046 (Div. 1)") 142 143 Idea: [Error_Yuan](/profile/Error_Yuan "Grandmaster Error_Yuan") 144 Preparation: [__baozii__](/profile/__baozii__ "Grandmaster __baozii__") 145 146 **Hint 1** 147 148 DP is needed for this problem. 149 150 **Hint 2** 151 152 If you force some index to be in the subsequence, there is only one optimal transition. 153 154 **Solution** 155 156 Let's go for DP. Denote $dp(i)$ as the length of the longest *neat* subsequence of prefix $[a_1, a_2, \ldots, a_i]$. It's obvious that $dp(0) \leq dp(1) \leq \ldots \leq dp(n)$. 157 158 Suppose we have calculated $dp(0), \ldots, dp(i-1)$. Let's try to calculate $dp(i)$: 159 160 1. If $a_i$ is not selected in the *neat* subsequence, we simply use $dp(i-1)$ to update $dp(i)$; 161 2. If $a_i$ is selected in the *neat* subsequence, the subsequence must end with $a_i$ elements equal to $a_i$. Since the $dp$ array is monotone, we should greedily find the $a_i$-th largest index $x$ in $[a_1, \ldots, a_i]$ where $a_x = a_i$, and use $dp(x-1) + a_i$ to update $dp(i)$. 162 163 The resulting $dp(i)$ is $\max(dp(i-1), dp(x-1) + a_i)$. Finding $x$ can be done efficiently by storing the occurrences of each different value. 164 165 Time complexity: $\mathcal O(n)$ per test case. 166 167 **Code (C++)** 168 169 ``` 170 #include <bits/stdc++.h> 171 172 using namespace std; 173 174 typedef long long ll; 175 176 const int MAXN = 2e5 + 10; 177 178 int T, n, a[MAXN], dp[MAXN]; deque<int> q[MAXN]; 179 180 int main() { 181 for (scanf("%d", &T); T--; ) { 182 scanf("%d", &n); 183 for (int i = 1; i <= n; i++) q[i].clear(); 184 for (int i = 1; i <= n; i++) scanf("%d", &a[i]); 185 for (int i = 1; i <= n; i++) { 186 dp[i] = dp[i - 1], q[a[i]].emplace_back(i); 187 if (q[a[i]].size() > a[i]) q[a[i]].pop_front(); 188 if (q[a[i]].size() == a[i]) dp[i] = max(dp[i], dp[q[a[i]].front() - 1] + a[i]); 189 } 190 printf("%d\n", dp[n]); 191 } 192 } 193 ``` 194 195 **Rate the Problem!** 196 197 * Amazing problem: 198 * Good problem: 199 * Average problem: 200 * Bad problem: 201 * Horrible problem: 202 203 [2135B - For the Champion](/contest/2135/problem/B "Codeforces Round 1046 (Div. 1)") 204 205 Idea & Preparation: [Error_Yuan](/profile/Error_Yuan "Grandmaster Error_Yuan") 206 207 **Hint 1** 208 209 You may not know the given Manhattan distance is between you and which anchor point. Can you make some moves so that you can determine it? 210 211 **Hint 2** 212 213 The absolute value in $\lvert x_i-c \rvert + \lvert y_i-d \rvert$ is somehow annoying, because you don't know whether it's $(x_i - c)$ or $(c - x_i)$. Find a way to fix the sign of $(x_i - c)$ and $(y_i - d)$. 214 215 **Extra Hint** 216 217 Try to move the robot to the top-left corner. 218 219 **Solution** 220 221 Read the hints. 222 223 Denote $V$ as $10^9$. Let's first use four operations $(\texttt{L}, V)$, $(\texttt{L}, V)$, $(\texttt{U}, V)$, and $(\texttt{U}, V)$. Since initially $-V \leq X, Y \leq V$, after the four operations, it's guaranteed that $X', Y' \leq -V$. 224 225 Thus, one can note that the current value received from the jury is exactly $\min\limits_{1 \leq i \leq n}(\lvert x_i - X'\rvert + \lvert y_i - Y'\rvert) = \min\limits_{1 \leq i \leq n}(X' - x_i + y_i - Y')$, which equals $\min\limits_{1 \leq i \leq n}(x_i - y_i) - X + Y + 4V$. This gives us the value of $X + Y$. 226 227 Similarly, if we move to the top-right corner (or the bottom-left one), we can know the value of $X - Y$. It would take $4$ extra steps of moving down or moving right (instead of $4 + 4$). By knowing $X + Y$ and $X - Y$, $X$ and $Y$ can be solved out. 228 229 Hence, we use only $8$ operations for each test case, which is sufficient to pass. 230 231 **Code (C++)** 232 233 ``` 234 #include <bits/stdc++.h> 235 #define all(s) s.begin(), s.end() 236 using namespace std; 237 using ll = long long; 238 using ull = unsigned long long; 239 240 const int _N = 1e5 + 5; 241 242 int T; 243 244 void solve() { 245 int n; cin >> n; 246 ll mn1 = LLONG_MAX, mx2 = -LLONG_MAX; 247 for (int i = 1; i <= n; i++) { 248 ll x, y; cin >> x >> y; 249 mn1 = min(mn1, y - x); 250 mx2 = max(mx2, x + y); 251 } 252 ll res; 253 cout << "? R 1000000000" << endl; 254 cin >> res; 255 cout << "? R 1000000000" << endl; 256 cin >> res; 257 cout << "? D 1000000000" << endl; 258 cin >> res; 259 cout << "? D 1000000000" << endl; 260 cin >> res; 261 ll res1 = mn1 - res + 4000000000ll; 262 cout << "? U 1000000000" << endl; 263 cin >> res; 264 cout << "? U 1000000000" << endl; 265 cin >> res; 266 cout << "? U 1000000000" << endl; 267 cin >> res; 268 cout << "? U 1000000000" << endl; 269 cin >> res; 270 ll res2 = mx2 + res - 4000000000ll; 271 cout << "! " << (res2 - res1) / 2 << ' ' << (res2 + res1) / 2 << endl; 272 return; 273 } 274 275 int main() { 276 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); 277 cin >> T; 278 while (T--) { 279 solve(); 280 } 281 } 282 ``` 283 284 **Rate the Problem!** 285 286 * Amazing problem: 287 * Good problem: 288 * Average problem: 289 * Bad problem: 290 * Horrible problem: 291 292 [2135C - By the Assignment](/contest/2135/problem/C "Codeforces Round 1046 (Div. 1)") 293 294 Idea & Preparation: [Register](/profile/Register "Master Register") 295 296 **Hint 1** 297 298 Consider the value of nodes on a cycle. 299 300 **Hint 2** 301 302 Consider the parity of the cycle's length. 303 304 **Hint 3** 305 306 The following are equivalent statements: 307 308 * "There is a cycle containing nodes $u, v$"; 309 * "Nodes $u, v$ are in the same two-edge-connected component". 310 311 **Hint 4** 312 313 Two two-edge-connected components don't affect each other. 314 315 **Solution** 316 317 Read the hints. 318 319 First, focus on a simple cycle only. Denote its length as $l$. We can choose two arbitrary nodes $u$ and $v$ on the cycle, obtaining two different simple paths. The two paths have equal values for all pairs of $(u, v)$. This implies that, for each set of size $l-2$ containing only nodes on the cycle, the bitwise XOR of the weight of the nodes in the set should equal $0$. 320 321 Thus, all nodes on the cycle have equal weight, since when sets $S_0 \cup {v}$ and $S_0 \cup {u}$ have equal bitwise XOR of node weights, this leads to nodes $u$ and $v$ having equal weights. Additionally, if $l$ is odd, one can verify that the weight of nodes on the cycle must be equal to $0$ (otherwise, it can be an arbitrary integer in $[0, V)$). 322 323 By decomposing the graph into two-edge-connected components, one can easily determine whether two nodes share a cycle —— by checking whether they belong to the same component. The answer is independent in each component, so we can simply multiply them together. 324 325 How to calculate the answer for a two-edge-connected component? First of all, the weight of all nodes must be equal. Then, if there exists an odd cycle (which can be detected with 2-coloring), it should equal $0$. There are only three different possible answers: $0$, $1$, and $V$. 326 327 Thus, one can calculate the answer to the original problem efficiently. 328 329 Time Complexity: $\mathcal O(n + m)$ per test case. 330 331 **Code (C++)** 332 333 ``` 334 #include <bits/stdc++.h> 335 336 using namespace std; 337 338 typedef long long ll; 339 340 const int MAXN = 2e5 + 10; 341 const int mod = 998244353; 342 343 vector<int> g[MAXN], dcc[MAXN]; 344 345 int dfn[MAXN], low[MAXN], id; 346 347 int s[MAXN], tp, p[MAXN], cnt; 348 349 void tarjan(int u, int f = 0) { 350 dfn[u] = low[u] = ++id, s[++tp] = u; 351 for (int v : g[u]) { 352 if (!dfn[v]) tarjan(v, u), low[u] = min(low[u], low[v]); 353 else if (v != f) low[u] = min(low[u], dfn[v]); 354 } 355 if (dfn[u] == low[u]) { 356 cnt++; 357 for (int x = 0; x != u; ) { 358 x = s[tp--], p[x] = cnt; 359 dcc[cnt].emplace_back(x); 360 } 361 } 362 } 363 364 int col[MAXN]; 365 366 bool check(int u, int f = 0) { 367 if (~col[u]) return col[u] == f; col[u] = f; 368 for (int v : g[u]) if (p[u] == p[v] && !check(v, f ^ 1)) return 0; 369 return 1; 370 } 371 372 int T, n, m, V, a[MAXN], ans; 373 374 int main() { 375 for (scanf("%d", &T); T--; ) { 376 scanf("%d%d%d", &n, &m, &V), id = cnt = 0, ans = 1; 377 for (int i = 1; i <= n; i++) dfn[i] = low[i] = p[i] = 0, col[i] = -1; 378 for (int i = 1; i <= n; i++) g[i].clear(), dcc[i].clear(); 379 for (int i = 1; i <= n; i++) scanf("%d", &a[i]); 380 for (int i = 1, u, v; i <= m; i++) { 381 scanf("%d%d", &u, &v); 382 g[u].emplace_back(v), g[v].emplace_back(u); 383 } 384 for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i); 385 for (int i = 1; i <= cnt; i++) { 386 int x = -1; 387 for (int u : dcc[i]) { 388 if (a[u] < 0) continue; 389 if (x < 0) x = a[u]; 390 else if (x != a[u]) { ans = 0; break; } 391 } 392 if (!ans) break; 393 bool f = check(dcc[i][0]); 394 if (f) { if (x < 0) ans = (ll)ans * V % mod; } 395 else if (x > 0) ans = 0; 396 if (!ans) break; 397 } 398 printf("%d\n", ans); 399 } 400 } 401 ``` 402 403 **Rate the Problem!** 404 405 * Amazing problem: 406 * Good problem: 407 * Average problem: 408 * Bad problem: 409 * Horrible problem: 410 411 [2135D1 - From the Unknown (Easy Version)](/contest/2135/problem/D1 "Codeforces Round 1046 (Div. 1)") 412 413 [2135D2 - From the Unknown (Hard Version)](/contest/2135/problem/D2 "Codeforces Round 1046 (Div. 1)") 414 415 Idea & Preparation: [Error_Yuan](/profile/Error_Yuan "Grandmaster Error_Yuan") 416 417 **Hint 1** 418 419 Try to input $10^5$ copies of $1$ in the first query. What can you get then? 420 421 **Hint 2** 422 423 After the first query, you can get $W\in [L, R]$. And $2\cdot L\ge R$ always holds. Now, can you construct the second query? 424 425 **Solution (Easy)** 426 427 In the first query, we will input $10^5$ copies of $1$. And the result will be equal to $r_1 = \left\lceil\frac{10^5}{W}\right\rceil$. By solving the equation $\left\lceil\frac{10^5}{x}\right\rceil = r_1$, we can get 428 429 $ \displaystyle{W\in \left [ \left\lceil\frac{10^5}{r_1}\right\rceil, \left\lceil \frac{10^5}{r_1 - 1} \right\rceil - 1 \right ]}. $ 430 431 For example, if: 432 433 * $r_1 = 1$, then $W=100\,000$; 434 * $r_1 = 2$, then $W\in [50\,000, 99\,999]$; 435 * $r_1 = 3$, then $W\in [33\,334, 49\,999]$; 436 * ... 437 438 For each interval $[L, R]$ above, $2\cdot L \gt R$ always holds, which is because $\lfloor \frac{n}{2L} \rfloor = \lfloor \frac{\lfloor \frac{n}{L} \rfloor}{2} \rfloor \neq \lfloor \frac{n}{L} \rfloor$. 439 440 Thus, we can input the following article in the second query: 441 442 $ [\underline{L, 1}, \underline{L, 2}, \ldots, \underline{L, R - L}]. $ 443 444 For each of the underlined group $(L, x)$: 445 446 * If $L + x \le W$, the two words in this group will be displayed in the same line; 447 * Otherwise, they will be displayed in different lines. 448 449 Note that $L + x + L \gt 2\cdot L \gt R \ge W$, so for each $1\le x \le W - L$, the group $(L, x)$ takes a single line, and for each $W - L \lt x \le R - L$, the group $(L, x)$ always take two lines. So the result of the query is $r_2 = (W - L) + 2\cdot (R - W)$. Hence, we get $W = 2\cdot R - L - r_2$. And we need to use $n = 2\cdot (R - L)\le 10^5$ words in this query. 450 451 Thus, we solved the problem in at most $2$ queries, which fits the constraints of the Easy Version. 452 453 **Code (Easy, C++)** 454 455 ``` 456 #include <bits/stdc++.h> 457 #include <ext/pb_ds/assoc_container.hpp> 458 #include <ext/pb_ds/tree_policy.hpp> 459 using namespace __gnu_pbds; 460 using namespace std; 461 template <class T> 462 using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; 463 #define all(v) v.begin(), v.end() 464 #define logg(x) (31 - __builtin_clz(x)) 465 #define llogg(x) (63 - __builtin_clzll(x)) 466 #define mini(v) min_element(v.begin(), v.end()) 467 #define maxi(v) max_element(v.begin(), v.end()) 468 #define TIME cerr << double(clock() - st) / (double)CLOCKS_PER_SEC 469 #define sq(a) ((a)*(a)) 470 #ifdef hocln 471 #include "deb.h" 472 #else 473 #define imie(...) "" 474 #define debug() cerr 475 #endif 476 typedef long long ll; 477 typedef pair<ll, ll> pll; 478 typedef pair<int, int> pii; 479 typedef long double ld; 480 typedef tuple<ll, ll, ll> triple; 481 typedef tuple<ll, ll, ll, ll, ll> five; 482 typedef unsigned long long ull; 483 const long long INF = 4e18; 484 const int inf = 2e9; 485 const int MN = 3e5 + 15; 486 const int MX = 2e6 + 15; 487 //const long long MOD = 1e9 + 7; 488 //const long long MOD = 998244353; 489 const long double PI = 3.141592653589793238462643383279502884197; 490 template<typename T, typename T2> bool chmax(T& a, const T2& b) { return a < b ? a = b, 1 : 0; } 491 template<typename T, typename T2> bool chmin(T& a, const T2& b) { return a > b ? a = b, 1 : 0; } 492 template<typename T> using vector2 = vector<vector<T>>; 493 const int dx[] = { 0, 0, 1, -1, 1, 1, -1, -1 }; 494 const int dy[] = { 1, -1, 0, 0 , 1, -1, 1, -1}; 495 std::random_device rd; 496 std::mt19937 gen(rd()); 497 ll random(ll low, ll high) { uniform_int_distribution<> dist(low, high); return dist(gen); } 498 template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p) { 499 is >> p.first; 500 return is >> p.second; 501 } 502 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) { 503 for (auto &i: v) os << i << ' '; 504 return os; 505 } 506 int tc = 0; 507 508 inline void get(int l, int r) { 509 int len = r-l+1; 510 cout << "? " << len * 2 << ' '; 511 for(int i = 1;i <= len;i++) { 512 cout << l << ' ' << i << ' '; 513 } 514 cout << endl; 515 int x; 516 cin >> x; 517 cout << "! " << len * 2 - x + l << endl; 518 } 519 520 inline void solve_test() { 521 int n=1e5; 522 cout << "? "; 523 cout << n << ' '; 524 for(int i = 1;i <= n;i++) cout << "1 "; 525 cout << endl; 526 int x; 527 cin >> x; 528 if(x == 1) { 529 cout << "! " << n << endl; 530 return; 531 } 532 int l = -1, r = -1; 533 for(int i = 1;i <= n;i++) { 534 if((n + i - 1) / i == x && l == -1) l = i; 535 if((n + i - 1) / i == x) r = i; 536 } 537 get(l,r); 538 } 539 540 int main() 541 { 542 ios::sync_with_stdio(0); 543 cin.tie(0);cout.tie(0); 544 int tt = 1; 545 cin >> tt; 546 while(tt--) { 547 ++tc; 548 solve_test(); 549 } 550 } 551 ``` 552 553 **Hint 3** 554 555 Can you do something better than $10^5~1~1~\ldots~1$ in the first query, so that the interval length will be reduced for the second query? 556 557 **Hint 4** 558 559 Change the first query to $N$ copies of $B$, where $N$ and $B$ are both undetermined constants. 560 561 **Hint 5** 562 563 Brute force to find the optimal value of $N$ and $B$. 564 565 **Solution (Hard)** 566 567 We want to cut down the total length of *articles*. So here comes a new strategy for the first query: $N$ copies of $B$, where $N$ and $B$ are both undetermined constants. 568 569 Now, the result for the first query is $r_1 = \displaystyle\left\lceil \frac{N}{\left \lfloor\frac{W}{B}\right\rfloor} \right\rceil$. 570 571 If $W\in [1, B - 1]$, the editor will be unable to display the *article*, and unfortunately our original strategy for the second query will not work in this case. But we can still use the strategy in the first query! Now we can query $B^2$ copies of $1$, and it's easy to show that the results for each $W=1,2,\ldots,B - 1$ will be distinct. 572 573 Otherwise, $W\in [B, 10^5]$, similar to the easy version, we will get an interval $[L, R]$, where $2\cdot L\ge R$ always holds. Then, we can use the same strategy as the second query in the easy version and get a solution with $2\cdot(R - L)$ queries. To calculate $L$ and $R$, you can simply use binary search, or do some math work to get 574 575 $ W\in \displaystyle \left[B\cdot \left(\left\lfloor\frac{N - 1}{r} + 1\right\rfloor \right), B\cdot \left(\left\lfloor\frac{N - 1}{r - 1} + 1\right\rfloor \right) - 1\right]. $ 576 577 There is also a fact that the rightmost interval will be cut off by the upper bound of $10^5$. 578 579 We can use brute force to find suitable values for $N$ and $B$. In the main correct solution, we choose $N = 11\,343$ and $B = 116$, and the maximal interval length is $6\,263$. Thus, the total length of *articles* won't exceed $11\,343 + \max(2\cdot 6\,263, 116^2) = 24\,799\le 25\,000$. 580 581 By some further optimization we can reduce $116^2$ a little to $\le 12\, 526$, so the total length of *articles* can be reduced to $23\,869$, but that's not needed. 582 583 **Code (Hard, C++)** 584 585 ``` 586 #include <bits/stdc++.h> 587 using namespace std; 588 589 const int MAXW = 100'000; 590 const int MAXSUM = 25'000; 591 const int B = 116; 592 const int K = 11343; 593 594 int t; 595 596 inline int ask(vector<int> v) { 597 cout << "? " << v.size(); 598 for (int i : v) { 599 cout << ' ' << i; 600 } 601 cout << endl; 602 int x; 603 cin >> x; 604 if (x == -1) { 605 exit(0); 606 } 607 return x; 608 } 609 inline void answer(int x) { cout << "! " << x << endl; } 610 611 int main() { 612 cin >> t; 613 while (t--) { 614 vector<int> v_qry1(K, B); 615 int res_qry1 = ask(v_qry1); 616 if (res_qry1 == 0) { 617 // W < B 618 vector<int> v_qry2(B * B, 1); 619 int res_qry2 = ask(v_qry2); 620 int w = (B * B - 1) / (res_qry2 - 1); 621 answer(w); 622 } else { 623 // W >= B 624 int min_w = ((K - 1) / res_qry1 + 1) * B, 625 max_w = ((K - 1) / (res_qry1 - 1) + 1) * B - 1; 626 max_w = min(max_w, MAXW); 627 for (int w = B; w <= MAXW; w++) { 628 int h = (K - 1) / (w / B) + 1; 629 if (h == res_qry1) { 630 assert(min_w <= w); 631 assert(w <= max_w); 632 } else { 633 assert(w < min_w || w > max_w); 634 } 635 } 636 637 if (min_w == max_w) { 638 answer(min_w); 639 } else { 640 vector<int> v_qry2; 641 for (int i = min_w + 2; i <= max_w; i++) { 642 v_qry2.push_back(min_w + 1); 643 v_qry2.push_back(i - min_w - 1); 644 } 645 if (v_qry2.empty()) { 646 v_qry2.push_back(min_w + 1); 647 } 648 int res_qry2 = ask(v_qry2); 649 650 if (res_qry2 == 0) { 651 answer(min_w); 652 } else { 653 answer(min_w + 1 + ((int)v_qry2.size() - res_qry2)); 654 } 655 } 656 } 657 } 658 } 659 ``` 660 661 **Rate the Problem! (Easy)** 662 663 * Amazing problem: 664 * Good problem: 665 * Average problem: 666 * Bad problem: 667 * Horrible problem: 668 669 **Rate the Problem! (Hard)** 670 671 * Amazing problem: 672 * Good problem: 673 * Average problem: 674 * Bad problem: 675 * Horrible problem: 676 677 [2135E1 - Beyond the Palindrome (Easy Version)](/contest/2135/problem/E1 "Codeforces Round 1046 (Div. 1)") 678 679 [2135E2 - Beyond the Palindrome (Hard Version)](/contest/2135/problem/E2 "Codeforces Round 1046 (Div. 1)") 680 681 Idea & Preparation: [Register](/profile/Register "Master Register") 682 Full Solution: [STUDENT0](/profile/STUDENT0 "Grandmaster STUDENT0") 683 684 **Hint 1** 685 686 Replace $\tt 0$ with $1$ and $\tt 1$ with $-1$. Try to find a sufficient and necessary condition of $s$ *almost-palindrome*. 687 688 **Hint 2** 689 690 Denote the $\pm 1$-s you get in **Hint 1** as array $a$, and $b_i = \sum_{j=1}^n a_j$. ($s$ is *almost-palindrome*) $\Longleftrightarrow$ ($\min b_i + \max b_i = b_n$), 691 692 **Hint 3** 693 694 You will need to solve the following subproblem: 695 696 You are on an infinite 2D plane, initially at $(0, 0)$. You can only move up/right by $1$ unit in one step. Also, you cannot touch the line $y=x + l$ or $y = x+ r$ during your move. Count the number of ways to travel to $(n, m)$. 697 698 We can solve the subproblem by a technique called "reflection inclusion-exclusion" in $\mathcal{O}\left(\frac{n}{|l - r|}\right)$ time complexity. You can view more details in problem E1 part of this blog: <https://codeforces.com/blog/entry/129027> 699 700 Or here is a detailed explanation in Chinese: <https://www.cnblogs.com/Hanghang007/p/18159154> 701 702 **Hint 4** 703 704 Try to compress sums by processing all $\max b_i - \min b_i = k$ together. 705 706 **Solution (Easy)** 707 708 Read the hints first. 709 710 Recall the answer for the subproblem in **Hint 3** as $f(n, m, l, r)$, we have 711 712 $ f(n, m, l, r) = \displaystyle \sum_{k\in \mathbb Z} {n + m\choose n - k\cdot (r - l)} - {n + m\choose n -k\cdot (r - l) + r}. $ 713 714 Suppose $\min b_i = l$ and $\max b_i = r$, the number of $b$-s is the number of ways to travel from $(0, 0)$ to $(n, m)$, "exactly" touching $y=x+l$ and $y=x+r$, that is, 715 716 $f\left(\frac{n-(l+r)}{2},\frac{n+(l+r)}{2},l,r\right) - f\left(\frac{n-(l+r)}{2},\frac{n+(l+r)}{2},l-1,r\right) \\ -f\left(\frac{n-(l+r)}{2},\frac{n+(l+r)}{2},l,r+1\right)+f\left(\frac{n-(l+r)}{2},\frac{n+(l+r)}{2},l-1,r+1\right). $ 717 718 Now we can compress the sums by processing all $\max b_i - \min b_i = k$ together. Let's enumerate on $k$, and note that the upper index of binomials is always $\frac{n-(l+r)}{2}+\frac{n+(l+r)}{2}=n$, and the lower index moves contiguously with the same $k$. 719 720 Thus, we have solved the problem in $\mathcal{O}(n\log n)$. 721 722 **Code (Easy, C++)** 723 724 ``` 725 #include <bits/stdc++.h> 726 727 using namespace std; 728 729 typedef long long ll; 730 731 const int MAXN = 1e6 + 10; 732 const int mod = 998244353; 733 734 inline int add(int x, int y) { return x += y, x < mod ? x : x - mod; } 735 inline int sub(int x, int y) { return x -= y, x < 0 ? x + mod : x; } 736 inline void cadd(int &x, int y) { x += y, x < mod || (x -= mod); } 737 inline void csub(int &x, int y) { x -= y, x < 0 && (x += mod); } 738 739 int inv[MAXN], a[MAXN], s[MAXN]; 740 741 inline 742 void init(int n) { 743 inv[1] = 1; 744 for (int i = 2; i <= n; i++) inv[i] = (ll)(mod - mod / i) * inv[mod % i] % mod; 745 } 746 747 int n; 748 749 inline 750 int ask(int l, int r) { 751 l = max(l, 0), r = min(r, n); 752 return l ? sub(s[r], s[l - 1]) : s[r]; 753 } 754 755 inline 756 int calc(int k, int t) { 757 int sum = 0; 758 for (int p = 0; (n + k >> 1) - p * (k + 2 - t) >= 0; p++) { 759 cadd(sum, ask((n - k >> 1) - p * (k + 2 - t), (n + k >> 1) - t - p * (k + 2 - t))); 760 } 761 for (int p = 0; (n - k >> 1) - 1 - p * (k + 2 - t) >= 0; p++) { 762 csub(sum, (ll)(k + 1 - t) * a[(n - k >> 1) - 1 - p * (k + 2 - t)] % mod); 763 } 764 for (int p = 1; (n - k >> 1) + p * (k + 2 - t) <= n; p++) { 765 cadd(sum, ask((n - k >> 1) + p * (k + 2 - t), (n + k >> 1) - t + p * (k + 2 - t))); 766 } 767 for (int p = 0; (n + k >> 1) + 1 - t + p * (k + 2 - t) <= n; p++) { 768 csub(sum, (ll)(k + 1 - t) * a[(n + k >> 1) + 1 - t + p * (k + 2 - t)] % mod); 769 } 770 return sum; 771 } 772 773 int T, ans; 774 775 int main() { 776 for (scanf("%d", &T), init(1e6 + 1); T--; ) { 777 scanf("%d", &n), *a = *s = 1, ans = 0; 778 for (int i = 1, x = 1; i <= n; i++) { 779 a[i] = (ll)a[i - 1] * inv[i] % mod * (n - i + 1) % mod; 780 s[i] = add(s[i - 1], a[i]); 781 } 782 for (int i = 1, x = 0, y = 0; i <= n; i++) { 783 if (n + i & 1) continue; 784 cadd(ans, x), cadd(ans, x = calc(i, 0)); 785 y = calc(i, 1), csub(ans, add(y, y)); 786 } 787 printf("%d\n", ans); 788 } 789 } 790 ``` 791 792 **Hint 5** 793 794 List out the coefficients of all ${n\choose m}$. 795 796 **Hint 6** 797 798 Try linear sieve. 799 800 **Solution (Hard)** 801 802 Read the hints and E1 editorial first. We'll try to speed up in a different way. 803 804 Let's consider $f\left(\frac{n-(l+r)}{2},\frac{n+(l+r)}{2},l,r\right)$ first. Let $k=r-l$. For each $k=1,2,\ldots,n$, we have 805 806 $\displaystyle\sum_{-k\le l\le 0}f\left(\frac{n-(l+r)}{2},\frac{n+(l+r)}{2},l,r\right)$ 807 808 $=\displaystyle\sum_{-k\le l\le 0}\sum_{z\in\mathbb Z} {n\choose (n-(2z+1)\cdot k) / 2-l}-{n\choose (n-(2z-1)\cdot k) / 2}$ 809 810 $=\displaystyle\sum_{-k+1\le l\le 0}\sum_{z\in\mathbb Z} {\color{red}{n\choose (n-(2z+1)\cdot k) / 2-l}}-{\color{blue}{n\choose (n-(2z-1)\cdot k) / 2}}$ 811 812 $={\color{red}2^{\color{red}n}}-\displaystyle k\cdot { \sum_{z\in\mathbb Z}\color{blue}{n\choose (n-(2z-1)\cdot k) / 2}}$ 813 814 We will consider the coefficient of ${n\choose m}$ in the blue part. Note that $(n-(2z-1)\cdot k) / 2 = m\Longleftrightarrow k=(n-2m)/(2z-1)$. Define $g(n)=\sum_{d\mid n,2\nmid(n/d)} d$, then the coefficient of ${n\choose m}$ is $g(|n-2m|)$. 815 816 The other 3 parts are similar. 817 818 Summing all, we got the final answer is 819 820 $ \displaystyle{(-1)^{n+1}\cdot2^n+2\sum^n_{i=0}\binom ni(g(|n-2i-1|)-g(|n-2i|)).} $ 821 822 And we can use linear sieve to precalculate $g(n)$. Thus, the whole problem is solved in $\mathcal{O}(n)$. 823 824 **Code (Hard, C++)** 825 826 ``` 827 #include <bits/stdc++.h> 828 829 using namespace std; 830 831 typedef long long ll; 832 833 const int MAXN = 2e7 + 10; 834 const int mod = 998244353; 835 836 inline int add(int x, int y) { return x += y, x < mod ? x : x - mod; } 837 inline int sub(int x, int y) { return x -= y, x < 0 ? x + mod : x; } 838 inline void cadd(int &x, int y) { x += y, x < mod || (x -= mod); } 839 inline void csub(int &x, int y) { x -= y, x < 0 && (x += mod); } 840 841 inline 842 int qpow(int b, int p) { 843 int res = 1; 844 for (; p; b = (ll)b * b % mod, p >>= 1) if (p & 1) res = (ll)res * b % mod; 845 return res; 846 } 847 848 int f[MAXN], g[MAXN], p[MAXN], tot; 849 850 int fac[MAXN], ifac[MAXN]; 851 852 inline 853 void init(int n) { 854 f[1] = 1; 855 for (int i = 2; i <= n; i++) { 856 if (!f[i]) p[++tot] = i, f[i] = g[i] = i + (i > 2); 857 for (int j = 1; j <= tot; j++) { 858 if (i * p[j] > n) break; 859 if (i % p[j] == 0) { 860 g[i * p[j]] = g[i] * p[j] + (j > 1); 861 f[i * p[j]] = f[i] / g[i] * g[i * p[j]]; 862 break; 863 } 864 f[i * p[j]] = f[i] * (p[j] + (j > 1)); 865 g[i * p[j]] = p[j] + (j > 1); 866 } 867 } 868 *fac = 1; 869 for (int i = 1; i <= n; i++) fac[i] = (ll)fac[i - 1] * i % mod; 870 ifac[n] = qpow(fac[n], mod - 2); 871 for (int i = n; i; i--) ifac[i - 1] = (ll)ifac[i] * i % mod; 872 } 873 874 int T, n, ans; 875 876 int main() { 877 for (scanf("%d", &T), init(2e7 + 1); T--; ) { 878 scanf("%d", &n), ans = 0; 879 for (int i = 0; i <= n; i++) { 880 ans = (ans + (ll)ifac[i] * ifac[n - i] % mod * sub(f[abs(n - i * 2 - 1)], f[abs(n - i * 2)])) % mod; 881 } 882 ans = (ll)ans * fac[n] % mod; 883 cadd(ans, ans), (n & 1 ? cadd : csub)(ans, qpow(2, n)); 884 printf("%d\n", ans); 885 } 886 } 887 ``` 888 889 **Rate the Problem! (Easy)** 890 891 * Amazing problem: 892 * Good problem: 893 * Average problem: 894 * Bad problem: 895 * Horrible problem: 896 897 **Rate the Problem! (Hard)** 898 899 * Amazing problem: 900 * Good problem: 901 * Average problem: 902 * Bad problem: 903 * Horrible problem: 904 905 [2135F - To the Infinity](/contest/2135/problem/F "Codeforces Round 1046 (Div. 1)") 906 907 Idea: [STUDENT0](/profile/STUDENT0 "Grandmaster STUDENT0") 908 Preparation: [Register](/profile/Register "Master Register") 909 910 **Hint 1** 911 912 How to compare two $f$ values? Since this function grows extremely fast, try to compare $\ln f$, $\ln \ln f$ and so on. 913 914 **Hint 2** 915 916 You only need to compare lexicographical order. 917 918 **Hint 3** 919 920 How to quickly compare lexicographical order? Try using hashing. 921 922 **Hint 4** 923 924 Use a data structure to maintain the hash value for each point. 925 926 **Hint 5** 927 928 Consider performing a topological sort on the tree from the bottom up. Then, when a node needs to be inserted into another tree, its ranking is already determined. A segment tree can be used instead of a balanced tree. 929 930 **Solution** 931 932 First, define the concept of a $\textbf{power tower}$. $X$ is a power tower if and only if one of the following holds: 933 934 * $X = x$. 935 * $X = x^{X_1X_2\cdots X_m}$, where $m$ is a constant independent of $x$, and $X_1, X_2, \cdots, X_m$ are all power towers. 936 937 Clearly, for power towers $X$ and $Y$, $X^Y$ is also a power tower. Therefore, in this problem, any $f_u(x)$ is a power tower. 938 939 First, consider how to compare two power towers $X$ and $Y$. The steps are as follows: 940 941 * If $X = x$ or $Y = x$, directly return their magnitudes. 942 * Otherwise, let $X = x^{X_1X_2\cdots X_p}$, $Y = x^{Y_1Y_2\cdots Y_q}$, where the quantities in the exponents are power towers. 943 + Sort $X_1, X_2, \cdots, X_p$ and $Y_1, Y_2, \cdots, Y_q$ in descending order. 944 + Compare their lexicographical order. If the lexicographical orders are equal, return that $X$ and $Y$ are equal; otherwise, return that the power tower with the larger lexicographical order is greater than the one with the smaller lexicographical order. 945 946 This gives a solution that can determine the relative sizes of two power towers in polynomial complexity. However, this is far from sufficient. 947 948 To optimize the complexity, when comparing $X$ and $Y$, we at least need to know the sorted order of $X_1, X_2, \cdots, X_p$ and $Y_1, Y_2, \cdots, Y_q$. This is equivalent to knowing the size relationships among them. 949 950 A key property of the tree can be easily observed: Let $fa_u$ be the father of $u$ in the tree. Then, it must hold that $f_u(x) \prec f_{fa_u}(x)$. Consider performing a topological sort on the original tree and using a heap to maintain the current queue. Each time, the smallest node is taken out to update the others. For any node $u$ in the queue, the corresponding power tower $X = f_u(x)$ already has known rankings for $X_1, X_2, \cdots, X_p$. A persistent segment tree can then be used to maintain prefix-sum hashes. When comparing two power towers, binary search can be performed on the segment tree to quickly find the first position where their exponent power towers differ, achieving a fast comparison in $\mathcal{O}(\log n)$ time per operation. 951 952 Time complexity: $\mathcal{O}(n\log^2 n)$ per test case. 953 954 **Code (C++)** 955 956 ``` 957 #include <bits/stdc++.h> 958 959 using namespace std; 960 961 typedef unsigned long long ull; 962 963 const int MAXN = 4e5 + 10; 964 965 ull A = mt19937_64(time(0))(); 966 967 inline ull shift(ull x) { 968 return x ^= A, x ^= x << 13, x ^= x >> 7, x ^= x << 11, x ^= A; 969 } 970 971 struct node { 972 int l, r, num; ull val; 973 } t[MAXN * 20]; int cnt, rt[MAXN]; 974 975 void add(int &p, int pre, int l, int r, int k, ull x) { 976 t[p = ++cnt] = t[pre], t[p].val += x, t[p].num++; 977 if (l == r) return ; int mid = l + r >> 1; 978 if (k <= mid) add(t[p].l, t[pre].l, l, mid, k, x); 979 else add(t[p].r, t[pre].r, mid + 1, r, k, x); 980 } 981 982 bool find(int p, int pre, int l, int r) { 983 if (l == r) return t[p].num > t[pre].num; int mid = l + r >> 1; 984 if (t[t[p].r].val == t[t[pre].r].val) return find(t[p].l, t[pre].l, l, mid); 985 else return find(t[p].r, t[pre].r, mid + 1, r); 986 } 987 988 int n, l[MAXN], r[MAXN], fa[MAXN], d[MAXN]; 989 990 int rk[MAXN], tot, lst; ull h[MAXN]; 991 992 struct cmp { 993 bool operator () (int x, int y) { 994 return h[x] == h[y] ? x > y : find(rt[x], rt[y], 1, n); 995 } 996 }; priority_queue<int, vector<int>, cmp> q; 997 998 999 inline 1000 void upd(int u) { 1001 h[u] = h[l[u]] + shift(h[r[u]]); 1002 add(rt[u], rt[l[u]], 1, n, rk[r[u]], shift(h[r[u]])); 1003 } 1004 1005 int T; 1006 1007 int main() { 1008 for (scanf("%d", &T); T--; ) { 1009 scanf("%d", &n), cnt = lst = tot = 0; 1010 for (int i = 1; i <= n; i++) rt[i] = 0; 1011 for (int i = 1; i <= n; i++) { 1012 scanf("%d%d", &l[i], &r[i]); 1013 d[i] = (l[i] && r[i] ? 2 : 0), fa[l[i]] = fa[r[i]] = i; 1014 } 1015 for (int i = 1; i <= n; i++) if (!d[i]) h[i] = 1, q.emplace(i); 1016 for (int u; !q.empty(); ) { 1017 printf("%d ", u = q.top()), q.pop(); 1018 if (h[u] != h[lst]) tot++; lst = u, rk[u] = tot; 1019 if (!--d[fa[u]]) upd(fa[u]), q.push(fa[u]); 1020 } 1021 puts(""); 1022 } 1023 } 1024 ``` 1025 1026 **Rate the Problem!** 1027 1028 * Amazing problem: 1029 * Good problem: 1030 * Average problem: 1031 * Bad problem: 1032 * Horrible problem: