codeforces-scrape

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

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: