2139.md (52044B)
1 Source: https://codeforces.com/blog/entry/146172 2 3 [2139A — Maple and Multiplication](https://codeforces.com/contest/2139/problem/A) 4 5 Idea: [installb](/profile/installb "Grandmaster installb") Preparation: [installb](/profile/installb "Grandmaster installb"),[2014CAIS01](/profile/2014CAIS01 "International Master 2014CAIS01") 6 7 **Solution** 8 9 If $a=b$ we need $0$ steps. 10 11 If $a$ can be divided by $b$, we only need $1$ step, which is to multiply $b$ by $\frac{a}{b}$. Same for the case when $b$ can be divided by $a$. 12 13 Otherwise, we need at most $2$ steps. As both $a$ and $b$ are positive integers, we can first multiply $a$ by $b$ and then multiply $b$ by the original value of $a$. Both number will be equal to $a\times b$. 14 15 **Code (C++)** 16 17 ``` 18 #include <bits/stdc++.h> 19 using namespace std; 20 typedef long long ll; 21 22 int solve(){ 23 int a,b; 24 cin >> a >> b; 25 if(a == b) return 0; 26 if(a % b == 0 || b % a == 0) return 1; 27 return 2; 28 } 29 30 int main(){ 31 ios::sync_with_stdio(false); 32 int TC; 33 cin >> TC; 34 while(TC --){ 35 cout << solve() << '\n'; 36 } 37 return 0; 38 } 39 ``` 40 41 **Rate this problem** 42 43 * Amazing problem: 44 * Good problem: 45 * Average problem: 46 * Bad problem: 47 * Horrible problem: 48 49 [2139B — Cake Collection](https://codeforces.com/contest/2139/problem/B) 50 51 Idea: [installb](/profile/installb "Grandmaster installb") Preparation: [installb](/profile/installb "Grandmaster installb") 52 53 **Solution** 54 55 The number of cakes collected from an oven depends only on the last time Maple visits it. Therefore, in the optimal strategy, she should visit distinct ovens in the last $\min(m,n)$ seconds. 56 57 Let's think in reverse: suppose we fix an order $p_1,\dots,p_n$ of the ovens. Then at second $m$ we visit oven $p_1$, at second $m-1$ we visit oven $p_2$, and so on. For the $i$-th oven in this order, we collect $a_{p_i}\cdot \max(0, m-i+1)$ cakes. 58 59 To maximize the total number of cakes collected, ovens with larger $a_i$ should be visited later (i.e., assigned larger multipliers). Thus we sort $a$ in non-increasing order first. 60 61 The final answer is $\sum_{i=1}^n a_i \cdot \max(0, m-i+1)$. 62 63 **Code (C++)** 64 65 ``` 66 #include <bits/stdc++.h> 67 using namespace std; 68 typedef long long ll; 69 const int INF = 0x3f3f3f3f; 70 71 void solve(){ 72 int n,t; 73 cin >> n >> t; 74 ll ans = 0; 75 vector <int> a(n); 76 for(int i = 0;i < n;i ++) cin >> a[i]; 77 sort(a.begin(),a.begin() + n,greater <int>()); 78 for(int i = 0;i < n;i ++) ans += 1ll * a[i] * max(0,t - i); 79 cout << ans << '\n'; 80 } 81 82 int main(){ 83 ios::sync_with_stdio(false); 84 int TC; 85 cin >> TC; 86 while(TC --){ 87 solve(); 88 } 89 return 0; 90 } 91 ``` 92 93 **Rate this problem** 94 95 * Amazing problem: 96 * Good problem: 97 * Average problem: 98 * Bad problem: 99 * Horrible problem: 100 101 [2138A — Cake Assignment](https://codeforces.com/contest/2138/problem/A) 102 103 Idea: [wjy666](/profile/wjy666 "Master wjy666") Preparation: [wjy666](/profile/wjy666 "Master wjy666") 104 105 **Hint** 106 107 You can backtrack from the final state. 108 109 **Solution** 110 111 Denote the state $(a,b)$ that indicates Chocola has $a$ cakes and Vanilla has $b$ cakes. 112 113 After one operation of type $1$, Vanilla's number of cakes will definitely be at least half of the total, and similarly for operation $2$. If $0 \lt a \lt 2^{k}$, then $2^{k} \lt b \lt 2^{k+1}$, meaning the previous operation must have been type $1$. Similarly, if $0 \lt b \lt 2^{k}$, the previous operation must have been type $2$. 114 115 Therefore, you can backtrack from the final state $(x,2^{k+1}-x)$, until it reaches the initial state $(2^k,2^k)$. 116 117 Now let's analyze how many steps we need to do during the process. 118 119 For the state $(a, b)$, where $a, b \neq 0$, assume $a = i \cdot 2^{p_a}$ and $b = j \cdot 2^{p_b}$, $i$ and $j$ are positive odd integers. 120 121 Since $a + b = 2^{k+1}$, it must be true that $ 0 \le p_a = p_b \le k$ , and after one operation $1$ or $2$, both $p_a$ and $p_b$ decrease by exactly $1$. 122 123 Therefore, the whole process takes at most $k$ steps, so we solve the problem with $O(tk)$ time complexity. 124 125 **Code (C++)** 126 127 ``` 128 #include <bits/stdc++.h> 129 using namespace std; 130 int main(){ 131 int t; cin>>t; 132 while(t--){ 133 long long k,x,kk; cin>>k>>x; kk=1ll<<k; 134 if (!x||x==kk*2) {cout<<"-1\n"; continue;} 135 long long y=kk*2-x; 136 vector<int> ans; ans.clear(); 137 while(x!=kk){ 138 if (x>y) ans.push_back(2),x-=y,y*=2; 139 else ans.push_back(1),y-=x,x*=2; 140 } 141 cout<<ans.size()<<"\n"; 142 while(!ans.empty()) cout<<ans.back()<<' ',ans.pop_back(); 143 cout<<"\n"; 144 } 145 return 0; 146 } 147 ``` 148 149 **Rate this problem** 150 151 * Amazing problem: 152 * Good problem: 153 * Average problem: 154 * Bad problem: 155 * Horrible problem: 156 157 [2138B — Antiamuny Wants to Learn Swap](https://codeforces.com/contest/2138/problem/B) 158 159 Idea: [tarjen](/profile/tarjen "International Grandmaster tarjen") Preparation: [installb](/profile/installb "Grandmaster installb"),[tarjen](/profile/tarjen "International Grandmaster tarjen"),[2014CAIS01](/profile/2014CAIS01 "International Master 2014CAIS01") 160 161 **Solution** 162 163 For array $b$, we can prove that $f(b)\neq g(b)$ **if and only if** there exist indexes $1\le i \lt j \lt k\le m$ which satisfy $b_i \gt b_j \gt b_k$. 164 165 Since $a$ is a permutation, all elements in $b$ should be distinct. $g(b)$ is equal to the number of inversions in $b$. When there exists some index $i$ that satisfies $a_i \gt a_{i+1} \gt a_{i+2}$, we can reduce the number of inversions by $3$ by applying operation $2$, allowing $f(b)$ to become less than $g(b)$. This is the only case where you can reduce more than $1$ inversion with one operation. 166 167 If there exist indexes $1\le i \lt j \lt k\le m$ which satisfy $b_i \gt b_j \gt b_k$, we can first choose indexes $i,k$, then move all elements greater than $b_i$ to the right of $b_k$ and move all elements less than $b_k$ to the left of $b_i$ by swapping adjacent numbers (applying the first operation). Now all elements $b_p$ between $b_i,b_k$ satisfy $b_i \gt b_p \gt b_k$. We then swap them to the left of $b_i$ until there is only one element $b_j$ left. Now $b_i \gt b_j \gt b_k$ and they are adjacent, and we can apply operation $2$ on the current index of $b_i$. 168 169 If we only apply operation $1$ on indexes $i$ which satisfy $b_i \gt b_{i+1}$, there will never exist any index $i$ satisfying $b_i \gt b_{i+1} \gt b_{i+2}$ in $b$ during the process. If we apply an operation $1$ on some index $i$ where $b_i \lt b_{i+1}$, the number of inversions will be increased by $1$ instead of decreased by $1$, which makes it impossible to reach $f(b) \lt g(b)$ with one operation $2$, even if it decreases the number of inversions by $3$. Therefore, in this case $f(b)=g(b)$. 170 171 For each element $a_i$, we define: 172 173 * $l_i$: the maximum index $ \lt i$ such that $a_{l_i} \gt a_i$, 174 * $r_i$: the minimum index $ \gt i$ such that $a_{r_i} \lt a_i$. 175 176 Then the answer to a query $[l, r]$ is $\texttt{NO}$ if and only if some segment $[l_i, r_i]$ lies fully inside $[l, r]$. 177 178 To answer multiple queries, you can preprocess the smallest $r$ for every $l$ such that the answers for all $[l,x](x\ge r)$ should be $\texttt{NO}$. 179 180 The time complexity is $O(n)$ if you find $l_i,r_i$ with the Monotonic Stack trick. $O(n\log n)$ solutions can also pass. 181 182 **Code (C++)** 183 184 ``` 185 #include <bits/stdc++.h> 186 using namespace std; 187 void solve() 188 { 189 int n, q; 190 cin >> n >> q; 191 vector<int> a(n + 2); 192 for (int i = 1; i <= n; i++) 193 { 194 cin >> a[i]; 195 } 196 197 vector<int> mxl(n + 1), mir(n + 1); 198 for (int i = 1; i <= n; i++) 199 { 200 mxl[i] = i - 1; 201 while (mxl[i] > 0 && a[mxl[i]] < a[i]) 202 mxl[i] = mxl[mxl[i]]; 203 } 204 for (int i = n; i >= 1; i--) 205 { 206 mir[i] = i + 1; 207 while (mir[i] <= n && a[mir[i]] > a[i]) 208 mir[i] = mir[mir[i]]; 209 } 210 vector<int> L(n + 1, 0); 211 for (int i = 2; i < n; i++) 212 { 213 if (mxl[i] > 0 && mir[i] <= n) 214 { 215 L[mir[i]] = max(L[mir[i]], mxl[i]); 216 } 217 } 218 for (int i = 1; i <= n; i++) 219 { 220 L[i] = max(L[i], L[i - 1]); 221 } 222 223 for (int i = 0; i < q; i++) 224 { 225 int l, r; 226 cin >> l >> r; 227 if (l <= L[r]) 228 cout << "NO\n"; 229 else 230 cout << "YES\n"; 231 } 232 } 233 int main() 234 { 235 ios::sync_with_stdio(false); 236 cin.tie(0); 237 int T; 238 cin >> T; 239 while (T--) 240 { 241 solve(); 242 } 243 } 244 ``` 245 246 **Rate this problem** 247 248 * Amazing problem: 249 * Good problem: 250 * Average problem: 251 * Bad problem: 252 * Horrible problem: 253 254 [2138C1 — Maple and Tree Beauty (Easy Version)](https://codeforces.com/contest/2138/problem/C1) 255 256 Idea: [installb](/profile/installb "Grandmaster installb") Preparation: [installb](/profile/installb "Grandmaster installb"),[tarjen](/profile/tarjen "International Grandmaster tarjen"),[2014CAIS01](/profile/2014CAIS01 "International Master 2014CAIS01") 257 258 **Solution** 259 260 We can first find out that the maximum possible answer is the minimum depth among all leaves $d=\min{dep_u}$, as the LCS can't be greater than the minimum length of all names. 261 262 We consider a special case first where all leaves have the same depth. If we want to achieve the maximum answer $d$, the names of all leaves should be exactly the same. Which means, for any two vertices with the same depth, their labels has to be the same. 263 264 For each depth $i$, we group all vertices with depth $i$ together as the $i$-th group (suppose root has depth $1$). For each group, all vertices in the group should have the same label. Let the size of groups $1,\cdots,d$ be $c_1,\cdots,c_d$. Now the problem can be considered as a knapsack problem, where you have $d$ items with weight $c_1,\cdots,c_d$. We need to find out whether you can take several numbers from $c$ that have a sum equal to $k$. This can be solved in $O(n^2)$. 265 266 If the maximum answer $d$ is not achievable, we can show that you can always achieve $d-1$. For each group from the first to the $d$-th, we assign an arbitrary label $0$ or $1$ which still has at least $c_i$ numbers remaining to all vertices in the group. As all leaves have the same depth, $c_d$ should be the maximum element in the array, so you are always able to select a label for groups $1$ to $d-1$. Then arbitrarily distribute the remaining labels among vertices in the last groups (which are leaves). 267 268 Now consider the general case where not all leaves have the same depth. If we want to achieve answer $=d$, we need to select $d$ groups. For each leaf vertex $v$, there should exist a vertex in the $d$-th group which is an ancestor of $v$. And for every $2\le i\le d$, for each vertex $v$ in the $i$-th group, there should exist a vertex in the $i-1$-th group which is an ancestor of $v$. All vertices in the same group should have the same label. Suppose the $i$-th group has label $l_i$, then we can achieve $\text{LCS}=l_1l_2\ldots l_d$ which has length $d$. 269 270 We can still group all vertices with depth $1\le i\le d$ together as the $i$-th group. For all vertices with depth $ \gt d$, we can set their label arbitrarily. We can view them as items with weight $1$ in the knapsack problem. 271 272 And we can show this is the optimal way to select $d$ groups. If some vertex $u$ with depth $\le d$ is not selected, there must be some vertices selected in some group in the subtree of $u$, because the path from the root to $u$ consists of fewer than $d$ vertices. If the smallest group index that some vertex in the subtree of $u$ belongs to is $i$, we can instead let $u$ be inside the $i$-th group, and then the labels of all vertices in the subtree of $u$ that were previously in group $i$ can be selected arbitrarily. If we consider the knapsack problem, we have reduced some $c_i$ by $x$ and added $x$ items with weight $1$. All achievable values still remain achievable, while some previously unachievable values become achievable. 273 274 The time complexity is $O(n^2)$, the bottleneck is knapsack. 275 276 **Code (C++)** 277 278 ``` 279 // n^2/w 280 #include <bits/stdc++.h> 281 using namespace std; 282 int solve() { 283 int n, k; 284 cin >> n >> k; 285 vector<int> fa(n, -1), dep(n, 0); 286 vector<int> noson(n, 1), cnt(n + 1); 287 cnt[0]++; 288 for (int i = 1; i < n; i++) { 289 cin >> fa[i], fa[i]--; 290 dep[i] = dep[fa[i]] + 1; 291 cnt[dep[i]]++; 292 noson[fa[i]] = 0; 293 } 294 int mxdep = 1e9; 295 for (int i = 0; i < n; i++) 296 if (noson[i]) mxdep = min(mxdep, dep[i]); 297 298 int sum = 0; 299 300 vector<int> dp(n + 1); 301 dp[0] = 1; 302 for (int i = 0; i <= mxdep; i++) { 303 for (int j = sum; j >= 0; j--) dp[j + cnt[i]] |= dp[j]; 304 sum += cnt[i]; 305 } 306 if (sum <= k || sum <= n - k) return mxdep + 1; 307 for (int i = 0; i <= sum; i++) 308 if (dp[i]) { 309 if (i <= k && sum - i <= n - k) return mxdep + 1; 310 } 311 return mxdep; 312 } 313 int main() { 314 ios::sync_with_stdio(false); 315 cin.tie(0); 316 int T; 317 cin >> T; 318 while (T--) cout << solve() << "\n"; 319 return 0; 320 } 321 ``` 322 323 **Rate this problem** 324 325 * Amazing problem: 326 * Good problem: 327 * Average problem: 328 * Bad problem: 329 * Horrible problem: 330 331 [2138C2 — Maple and Tree Beauty (Hard Version)](https://codeforces.com/contest/2138/problem/C2) 332 333 Idea: [installb](/profile/installb "Grandmaster installb") Preparation: [installb](/profile/installb "Grandmaster installb"),[tarjen](/profile/tarjen "International Grandmaster tarjen"),[2014CAIS01](/profile/2014CAIS01 "International Master 2014CAIS01") 334 335 **Solution** 336 337 We focus on optimizing the knapsack problem. In the knapsack problem we only need to know $f_i=0/1$ which means whether you can achieve sum $i$, so we can optimize the knapsack with bitset. The time complexity is $O(\frac{n^2}{\omega})$ which is enough to pass E2. 338 339 But actually we can do better. For the knapsack problem, it has at most $n$ items, and the sum of weights of all items is also at most $n$. We can do a sqrt decomposition trick here. 340 341 * For items with weight $\ge\sqrt{n}$, there are at most $\sqrt{n}$ such items. 342 * For items with weight $ \lt \sqrt{n}$, we count the number of items for each different weight. If there are $c_w$ items for weight $w$, we decompose $x$ into $c_w=2^0+2^1+\cdots+2^k+y$ where $k$ is the largest integer satisfying $2^0+2^1+\ldots+2^k\le c_w$. Then we create new items with weights $2^0\cdot w,2^1\cdot w,\ldots,2^k\cdot w,y\cdot w$. The set of new items is the same as $c_w$ items with weight $w$ if we only consider the different sum of weights the set of items can achieve. Now we only have $\sum_{w=1}^{\sqrt{n}}\log(c_w)=\sqrt{n}$ items. 343 344 The total time complexity is $O(\sqrt{n}\cdot n+\sqrt{n}\cdot n)=O(n\sqrt{n})$. 345 346 And this can also be optimized with bitset, leading to an $O(\frac{n\sqrt{n}}{\omega})$ solution. 347 348 **Code (C++)** 349 350 ``` 351 // nsqrtn/w 352 #include <bits/stdc++.h> 353 using namespace std; 354 const int N = 2e5 + 10; 355 template <int maxn> 356 int solve(int n, int k) { 357 if (maxn <= n) { 358 return solve<min(N, maxn * 2)>(n, k); 359 } 360 bitset<maxn> dp; 361 vector<int> fa(n, -1), dep(n, 0); 362 vector<int> noson(n, 1), cnt(n + 1); 363 cnt[0]++; 364 for (int i = 1; i < n; i++) { 365 cin >> fa[i], fa[i]--; 366 dep[i] = dep[fa[i]] + 1; 367 cnt[dep[i]]++; 368 noson[fa[i]] = 0; 369 } 370 dp.reset(); 371 dp[0] = 1; 372 int mxdep = 1e9; 373 for (int i = 0; i < n; i++) 374 if (noson[i]) mxdep = min(mxdep, dep[i]); 375 376 int sum = 0; 377 vector<int> all(cnt.begin(), cnt.begin() + mxdep + 1); 378 sort(all.begin(), all.end()); 379 vector<int> v; 380 for (int i = 0; i < (int)all.size(); i++) { 381 int j = i; 382 while (j + 1 < (int)all.size() && all[i] == all[j + 1]) j++; 383 int t = j - i + 1; 384 for (int z = 1; z <= t; z *= 2) { 385 v.push_back(z * all[i]); 386 t -= z; 387 } 388 if (t > 0) v.push_back(t * all[i]); 389 i = j; 390 } 391 dp[0] = 1; 392 for (auto val : v) { 393 sum += val; 394 dp |= (dp << val); 395 } 396 if (sum <= k || sum <= n - k) return mxdep + 1; 397 for (int i = 0; i <= sum; i++) 398 if (dp[i]) { 399 if (i <= k && sum - i <= n - k) return mxdep + 1; 400 } 401 return mxdep; 402 } 403 int main() { 404 ios::sync_with_stdio(false); 405 cin.tie(0); 406 int T; 407 cin >> T; 408 while (T--) { 409 int n, k; 410 cin >> n >> k; 411 cout << solve<1>(n, k) << "\n"; 412 } 413 return 0; 414 } 415 ``` 416 417 **Rate this problem** 418 419 * Amazing problem: 420 * Good problem: 421 * Average problem: 422 * Bad problem: 423 * Horrible problem: 424 425 [2139D — Antiamuny and Slider Movement](https://codeforces.com/contest/2138/problem/D) 426 427 Idea: [tarjen](/profile/tarjen "International Grandmaster tarjen"),[StarSilk](/profile/StarSilk "International Grandmaster StarSilk") Preparation: [installb](/profile/installb "Grandmaster installb"),[tarjen](/profile/tarjen "International Grandmaster tarjen"),[StarSilk](/profile/StarSilk "International Grandmaster StarSilk") 428 429 **Solution** 430 431 Let’s define $b_i$ as the position of the $i$-th slider decreased by $i$. Every operation on the sliders can be interpreted as a modification of the array $b$. 432 433 * If we increase the position of slider $i$, then $b_i$ increases. At the same time, every suffix element $b_{i+1}, b_{i+2}, \dots, b_n$ gets updated to $b_j := \max(b_j, b_i)$. 434 * If we decrease the position of slider $i$, then $b_i$ decreases. At the same time, every prefix element $b_1, b_2, \dots, b_{i-1}$ gets updated to $b_j := \min(b_j, b_i)$. 435 436 Since the array $b$ always remains **non-decreasing**, we can reinterpret operations as follows: 437 438 * Every operation simultaneously applies a $\min$ operation to all elements on the left, and a $\max$ operation to all elements on the right. 439 440 For a fixed slider $b_i$, the effect of each operation on the slider should be one of the following: 441 442 1. $b_i := \max(b_i, x)$ 443 2. $b_i := \min(b_i, x)$ 444 3. $b_i := x$ (assignment) 445 446 Our task is to compute the sum of final values of $b_i$ after all possible sequences of operations. 447 448 We sort all operations by their parameter $x$. If multiple operations share the same $x$, we give them a consistent order and then assume all $x$ are distinct in the following part of the editorial. 449 450 We first suppose that the position of the slider is changed at least once. Suppose the final value for slider $i$ is $b_e$, let’s consider which operation sets $b_i = b_e$ at the very end. 451 452 At this point, we no longer care about the exact value of $b_i$ during the process — only whether it is less than, equal to, or greater than $b_e$. 453 454 All operations of type $\max$ with $x \lt b_e$ and type $\min$ with $x \gt b_e$ are irrelevant. We can insert them anywhere after deciding the order of other operations without affecting the result. We won't consider these operations in the following parts of the editorial. 455 456 All assignment operations $b_i := x$ can be reinterpreted: 457 458 * If $x \lt b_e$, treat it as $b_i := \min(b_i, x)$. 459 * If $x \gt b_e$, treat it as $b_i := \max(b_i, x)$. 460 461 The last operation, that makes $b_i = b_e$ must be the one with parameter $x = b_e$. 462 463 * If this operation is assignment, then all other operations can appear in any order. 464 * If this operation is $\max$ type, then immediately before it we must have $b_i \lt b_e$. 465 * + Either the last preceding valid operation is some $\min$ type operation making $b_i \lt b_e$; 466 * + Or no other effective operation occurs, and the initial value of $b_i$ was already smaller than $b_e$. 467 * If this operation is $\min$ type operation, it is symmetric: either the last preceding valid operation is a $\max$ type operation, or the initial value of $b_i$ was already larger than $b_e$. 468 469 Finally, don’t forget the case where a slider is never touched, where it simply keeps its initial value. 470 471 For each of the $n$ sliders, we need to check contributions over all $m$ operations. The overall time complexity is $O(nm)$. 472 473 **Code (C++)** 474 475 ``` 476 #include<bits/stdc++.h> 477 using namespace std; 478 const long long mod=1000000007; 479 long long a[5000],ans[5000],tt[5001],inv[5001]; 480 struct apos{ 481 long long id; 482 long long x; 483 friend bool operator<(apos a,apos b){ 484 return a.x<b.x; 485 } 486 }ap[5000]; 487 int main(){ 488 ios::sync_with_stdio(false),cin.tie(0); 489 int T,flag; 490 long long n,m,p,q,x,i,j,cl,cr; 491 tt[0]=1; 492 for(i=1;i<=5000;i++)tt[i]=tt[i-1]*i%mod; 493 inv[1]=1; 494 for(i=2;i<=5000;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod; 495 for(cin>>T;T>0;T--) 496 { 497 cin>>n>>m>>p; 498 for(i=0;i<n;i++) 499 { 500 cin>>a[i]; 501 a[i]-=i; 502 } 503 for(i=0;i<p;i++) 504 { 505 cin>>ap[i].id>>ap[i].x; 506 ap[i].id--; 507 ap[i].x-=ap[i].id; 508 } 509 sort(ap,ap+p); 510 for(i=0;i<n;i++) 511 { 512 flag=0; 513 for(j=0;j<p;j++) 514 { 515 if(ap[j].id<=i&&ap[j].x>=a[i])flag=1; 516 if(ap[j].id>=i&&ap[j].x<a[i])flag=1; 517 } 518 if(!flag) 519 { 520 ans[i]=a[i]+i; 521 continue; 522 } 523 ans[i]=0; 524 cl=0; 525 cr=0; 526 for(j=0;j<p;j++) 527 { 528 if(ap[j].id<=i)cr++; 529 } 530 for(j=0;j<p;j++) 531 { 532 if(ap[j].id<=i)cr--; 533 if(ap[j].id==i)ans[i]=(ans[i]+(ap[j].x+i)*inv[cl+cr+1])%mod; 534 if(ap[j].id<i) 535 { 536 if(cl==0&&cr==0&&a[i]<=ap[j].x)ans[i]=(ans[i]+ap[j].x+i)%mod; 537 else ans[i]=(ans[i]+(ap[j].x+i)*inv[cl+cr+1]%mod*inv[cl+cr]%mod*cl)%mod; 538 } 539 if(ap[j].id>i) 540 { 541 if(cl==0&&cr==0&&a[i]>ap[j].x)ans[i]=(ans[i]+ap[j].x+i)%mod; 542 else ans[i]=(ans[i]+(ap[j].x+i)*inv[cl+cr+1]%mod*inv[cl+cr]%mod*cr)%mod; 543 } 544 if(ap[j].id>=i)cl++; 545 } 546 } 547 for(int x = 0;x < n;x ++) 548 { 549 cout<<ans[x]*tt[p]%mod<<' '; 550 } 551 cout<<'\n'; 552 } 553 return 0; 554 } 555 ``` 556 557 **Rate this problem** 558 559 * Amazing problem: 560 * Good problem: 561 * Average problem: 562 * Bad problem: 563 * Horrible problem: 564 565 [2139E1 — Determinant Construction (Easy Version)](https://codeforces.com/contest/2138/problem/E1) 566 567 Idea: [wjy666](/profile/wjy666 "Master wjy666") Preparation: [wjy666](/profile/wjy666 "Master wjy666") 568 569 **Solution 1** 570 571 Thanks to [EvenImage](/profile/EvenImage "Legendary Grandmaster EvenImage") for his significant contribution to this solution. 572 573 **Step 1** 574 575 We can consider transforming the construction of a matrix into the construction of a directed graph, as the determinant and permutations are closely related to the cycle covers of a directed graph. 576 577 If we have a directed graph with $n$ vertices, a cycle cover is a set of $n$ edges such that each vertex has exactly one incoming edge and one outgoing edge in this set (self-loops are allowed). In other words, these $n$ edges form one or more cycles that together cover all vertices in the graph. 578 579 In a complete directed graph (with self-loops), every permutation of the vertices determines a cycle cover and vice versa. (The cycles of the permutation are precisely the cycles in the cover.) 580 581 We consider the definition of the determinant: 582 583 $ \det(M)=\sum_{\begin{subarray}{c}B=(b_{0},\ldots,b_{n-1})\\ B\in\mathcal{P}_{n}\end{subarray}}(-1)^{\mathrm{inv}(B)}\cdot\prod_{i=0}^{n-1}m_ {i,b_{i}} $ 584 585 This summation goes over all permutations $B$, in other words, over all cycle covers of the directed graph determined by the adjacency matrix $M$. We can also interpret $m_{i,j}=0$ as "the edge from $i$ to $j$ does not exist at all". Thus, the product term $\prod_{i=0}^{n-1}m_ {i,b_{i}}$ is non-zero only if all $m_ {i,b_{i}} \neq 0$, which corresponds to the existence of a cycle cover in the graph. 586 587 We want to construct a directed graph such that the sum of the weights of its cycle covers equals $x$. Since the current problem only allows the use of $-1, 0, 1$, the edge weights can only be $1$ or $-1$, and the contribution of a valid cycle cover to the answer can only be $1$ or $-1$. 588 589 PS: You can refer to pages 56-58 of <https://ipsc.ksp.sk/2012/real/solutions/booklet.pdf> for more information. 590 591 **Step 2** 592 593 There might be many ways to construct a legal directed graph. We will demonstrate a method that transforms the problem into constructing a DAG with exactly $x$ paths from source vertex $1$ to sink vertex $n$. 594 595 For a directed acyclic graph $G$ with source vertex $1$ and sink vertex $n$, we can construct the following adjacency matrix: 596 597 * $g_{i,j} = -1$ if there is an edge $i \rightarrow j$ in $G$. Set the weight of all original edges in $G$ to $-1$. 598 * $g_{i,i} = 1$ for all $1 \lt i \lt n$. Add a self-loop with weight $1$ to all vertices in $G$ except the source and sink. 599 * $g_{n,1} = 1$. Add an edge from the sink to the source with weight $1$. 600 * Everything else $= 0$. 601 602 We analyze all cycle covers of this new graph. Due to the presence of the edge $n \rightarrow 1$ , any cycle cover must contain a main cycle that includes nodes $1$ and $n$, formed by a path $P$ from $1$ to $n$ in $G$ and the edge $n \rightarrow 1$. For nodes not on path $P$ (i.e., intermediate nodes not covered by path $P$), they must be covered by self-loops with weight $1$. Therefore, each cycle cover uniquely corresponds to a path $P$ from $1$ to $n$. 603 604 Since there are $x$ paths in $G$, we only need to ensure that the contribution of each cycle cover is $1$ to obtain a determinant value of $x$. Next, we will analyze how to achieve this by setting the weight of all original edges in $G$ to $-1$. 605 606 For each cycle cover, first consider the product of all edge weights: 607 608 * The main cycle has $k$ edges, among which $k-1$ edges come from path $P$ (each with weight $-1$), and one edge is $n \rightarrow 1$ (with weight $1$). Thus, the product term is $(-1)^{k-1}$. 609 * The weights of all other self-loops are $1$. 610 611 Therefore, the product of all edge weights is $(-1)^{k-1}$. 612 613 Then we consider the sign term $(-1)^{\mathrm{inv}(B)}$. In fact, the parity of the number of inversions $\mathrm{inv}(B)$ in the permutation is consistent with the parity of the number of even cycles in the permutation. The main cycle is a cycle of length $k$, and the self-loops are all cycles of length $1$. Therefore, the sign term is $(-1)^{k-1}$. 614 615 Thus, the contribution of each cycle cover is $(-1)^{k-1} \cdot (-1)^{k-1}=1$. 616 617 Due to the constraints in the problem that the matrix size is at most $80$ and there are at most $3$ non-zero entries per row and column, we need to construct a DAG that satisfies: 618 619 * Exactly $x$ paths from source vertex $1$ to sink vertex $n$. 620 * At most $80$ nodes. 621 * The in-degree of each node $\le 2$ and the out-degree of each node $\le 2$. 622 623 **Step 3** 624 625 Since $80$ is a loose boundary, there might be many constructions that satisfy it. We will introduce a construction method that encodes $x$ in base three. 626 627 The basic unit shown in the figure can form a base-three digit because the number of paths from $1$ to $3$ is $2$, and from $1$ to $4$ is $3$. Node $4$ can be connected to the next unit, forming a chain of units, where each unit corresponds to a base-three digit. Nodes $3$ and $4$ have one free out-degree, which can contribute to the final answer. 628 629  630 631 The example figure below shows how to construct $22=1+3+2 \cdot 3^2$ in this way. There are $\log_3 n$ basic units, each with $4$ nodes. The answer chain has at most $\log_3 n$ nodes. Therefore, the total number of nodes is $5\log_3 n + O(1)$, which can pass the problem. 632 633  634 635 **Code (C++)** 636 637 ``` 638 #include<bits/stdc++.h> 639 using namespace std; 640 const int N=81; 641 int a[N][N]; 642 vector<pair<int,int>> e; 643 void add(int x,int y){ 644 e.push_back({x,y}); 645 } 646 void make_matrix(int n){ 647 for(int i=2;i<n;++i) a[i][i]=1; 648 a[n][1]=1; 649 for(auto [x,y]:e) a[x][y]=-1; 650 } 651 int main(){ 652 int _; scanf("%d",&_); //cin>>_; 653 int max_bit=15; 654 while(_--){ 655 memset(a,0,sizeof(a)); e.clear(); 656 int n=1; 657 for(int i=0;i<max_bit;++i){ 658 add(n,n+1); add(n+1,n+2); add(n+2,n+3); add(n+3,n+4); 659 add(n+1,n+3); add(n+2,n+4); 660 n+=4; 661 } 662 int x,bit_1=1,bit_2=4; scanf("%d",&x); ++n; 663 for(int i=0;i<max_bit;++i){ 664 if (x%3==1) add(bit_1,n),add(n,n+1),++n; 665 if (x%3==2) add(bit_2,n),add(n,n+1),++n; 666 bit_1+=4; bit_2+=4; x/=3; 667 } 668 make_matrix(n); 669 cout << n <<'\n'; 670 for (int r = 1; r <= n; r++) { 671 for (int c = 1; c <= n; c++) { 672 printf("%d ",a[r][c]); 673 } 674 cout << '\n'; 675 } 676 } 677 } 678 ``` 679 680 **Solution 2** 681 682 **Step 1** 683 684 We can consider using Tridiagonal Matrices, where the advantage lies in transforming the calculation of the determinant value into a recursive formula. 685 686 Let $d_{i,j}$ denote the element in the i-th row and j-th column of matrix $D$, $D_k$ represents the submatrix composed of the upper-left $k \times k$ elements, and $A_k$ denotes the determinant value of $D_k$. 687 688 When $k \ge 2$, there are two ways to obtain $D_{k+1}$ from $D_k$: 689 690 * Let $ d_{k+1,k+1}=1, d_{k+1,k}=1,d_{k,k+1}=1$ to get $A_{k+1}=A_k-A_{k-1}$ 691 * Let $ d_{k+1,k+1}=1, d_{k+1,k}=1,d_{k,k+1}=-1$ to get $A_{k+1}=A_k+A_{k-1}$ 692 693 Thus, we transform the problem into constructing a sequence $A_1,\ldots,A_m$ satisfying: 694 695 * $A_1 = |D_1|, A_2 = |D_2|$ 696 * For any $k=2,3,\ldots,m-1$, one of the following two equations holds: $A_{k+1}=A_k-A_{k-1}$, or $A_{k+1}=A_k+A_{k-1}$ 697 * $A_m=n (m \le 80)$ 698 699 **Step 2** 700 701 Consider recursively generating the entire sequence from $A_m=n$ backwards. 702 703 * Choose a positive integer as $A_{m−1}$. 704 * At a certain moment, we have $A_k$ and $A_{k+1}$, and obtain $A_{k−1}$ as follows: 705 706 If $A_k \gt A_{k+1}$, let $A_{k-1}=A_k-A_{k+1}$; otherwise, let $A_{k-1}=A_{k+1}-A_k$ 707 708 This ensures that each number in the sequence is a non-negative integer. 709 * If at some point there exist $D_1,D_2$ satisfying $A_k = |D_1|, A_{k+1} = |D_2|$, successfully finish the construction. 710 711 For example,if we have $A_m=7$ and $A_{m−1}=3$, the final sequence will be $1,2,3,1,4,3,7$, and we will generate the matrix as 712 713 $\begin{pmatrix} 1 & -1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & -1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & -1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & -1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 \end{pmatrix}$ 714 715 Denote $(A_k,A_{k+1})=(x,y)$. 716 717 When $x \gt y$, the recursion process can be written as $(x,y) \rightarrow (x-y,x) \rightarrow (y,x-y)$, increasing the length of the sequence by $2$, completing one iteration of subtraction. 718 719 When $x \le y$, the recursion process can be written as $(x,y) \rightarrow (y-x,x)$, increasing the length of the sequence by $1$, completing one iteration of subtraction. 720 721 The process will eventually lead to $(x,0)$ or $(0,x)$, where $x$ is the GCD of $A_m$ and $A_{m−1}$. 722 723 When $A_m$ and $A_{m−1}$ are coprime, we have $x=1$, meeting the requirements for the sequence. In fact, we can stop earlier when $(1,2)$, and the sequence is still legal. 724 725 When $A_m$ and $A_{m−1}$ are not coprime, we have $x \gt 1$, and this method can't obtain a sequence that meets the requirements. 726 727 **Step 3** 728 729 Given $A_m=n$, we need to find a suitable $A_{m−1}$ such that the length of the final sequence is less than or equal to $80$. 730 731 Since $80$ is a relaxed constraint, and you only need to find one valid $A_{m−1}$, you can try various approaches. 732 733 For example, you could enumerate all possibilities within the range $[1, n-1]$ for some large $n$, and then discover that there are many valid $A_{m−1}$ values that meet the criteria. 734 735 If you randomly search for $A_{m−1}$ within the range, the expected number of attempts required is very low. In fact, the verification program tested all integers $n$ from $10$ to $10^7$, randomly selecting $1000$ possible $A_{m−1}$ values for each n and testing them. The results showed that in the worst case (when $n = 9827370$), there were still $24$ valid $A_{m−1}$ values that met the requirements out of the $1000$ randomly chosen values. 736 737 **Code (C++)** 738 739 Code: 740 741 ``` 742 #include<bits/stdc++.h> 743 using namespace std; 744 int fl[1005],inf=1e9,cnt; 745 int work(int x,int y){ 746 int ans=0,tmp; 747 while(y&&ans<=80){ 748 ++ans; tmp=y; 749 if (x>y) y=x-y; else y=y-x; 750 x=tmp; 751 } 752 if (x>1) return inf; 753 return ans; 754 } 755 void gen(int x,int y){ 756 //printf("%d\n",work(x,y)); 757 vector<int> seq; seq.clear(); seq.push_back(x); seq.push_back(y); 758 int tmp; 759 while(!(x==2&&y==1)){ 760 tmp=y; 761 if (x>y) y=x-y; else y=y-x;//x=tmp; 762 x=tmp; 763 seq.push_back(y); 764 } 765 int ans[105][105]={0}; 766 int pre=seq.back(),n=1; seq.pop_back(); ans[1][1]=1; 767 while(!seq.empty()){ 768 ++n; 769 if (seq.back()>pre) ans[n][n]=1,ans[n][n-1]=1,ans[n-1][n]=-1; 770 else ans[n][n]=1,ans[n][n-1]=1,ans[n-1][n]=1; 771 pre=seq.back(); seq.pop_back(); 772 } 773 printf("%d\n",n); 774 for(int i=1;i<=n;++i){ 775 for(int j=1;j<=n;++j){ 776 printf("%d ",ans[i][j]); 777 } 778 printf("\n"); 779 } 780 } 781 int main(){ 782 int _; cin>>_; mt19937 rd(time(0)); 783 while(_--){ 784 int n; cin>>n; 785 if (n==0) {printf("1\n0\n"); continue;} 786 if (n==1) {printf("1\n1\n"); continue;} 787 while(1){ 788 int y=rd()%(n-1)+1; 789 int tmp=work(n,y); 790 if (tmp<=80) {gen(n,y); break;} 791 } 792 } 793 return 0; 794 } 795 ``` 796 797 Verification Program: 798 799 ``` 800 #pragma GCC optimize(3) 801 #include<bits/stdc++.h> 802 using namespace std; 803 int inf=1e9; 804 int work(int x,int y){ 805 int ans=0,tmp; 806 while(y&&ans<=80){ 807 ++ans; tmp=y; 808 if (x>y) y=x-y; else y=y-x; 809 x=tmp; 810 } 811 if (x>1) return inf; 812 return ans; 813 } 814 int main(){ 815 mt19937 rd(114514); 816 int n=1e7,minn=1e3; 817 for(int x=n;x>=5;x--){ 818 int _=1e3,c=0; 819 while(_--){ 820 int y=rd()%(x-1)+1; 821 int tmp=work(x,y); 822 if (tmp<=80) ++c; 823 } 824 if (c<minn) minn=c,cout<<' '<<minn<<' '<<x<<endl; 825 if (x%10000==1) cout<<clock()<<'#'<<x<<endl; 826 } 827 return 0; 828 } 829 ``` 830 831 **Rate this problem** 832 833 * Amazing problem: 834 * Good problem: 835 * Average problem: 836 * Bad problem: 837 * Horrible problem: 838 839 [2139E2 — Determinant Construction (Hard Version)](https://codeforces.com/contest/2138/problem/E2) 840 841 Idea: [wjy666](/profile/wjy666 "Master wjy666") Preparation: [wjy666](/profile/wjy666 "Master wjy666") 842 843 Since $50$ is a very tight constraint, the author did not find a method to construct the DAG for G2 as in Solution 1 of G1. If you have a better solution, please leave a comment below. 844 845 **Hint** 846 847 In Solution 2, the first two steps remain consistent with G1, but we need a better method to find a suitable $A_{m−1}$ such that the length of the final sequence is less than or equal to $50$. Randomly searching for $A_{m−1}$ within the range $[1, n-1]$ may result in TLE. 848 849 We noticed that if $A_{m−1}$ and $A_m$ are two adjacent fibonacci numbers, the sequence will converge rapidly (with a length within $40$). Although not all $A_m=n$ are fibonacci numbers, we can still draw inspiration from this. 850 851 **Solution A** 852 853 We attempt to decompose $n$ as $n=a \cdot \operatorname{fib}(i)+b \cdot \operatorname{fib}(i-1), a,b \ge 0$, where $\operatorname{fib}(i)$ denotes the $i$-th fibonacci number. 854 855 Then, we set $A_{m-1}=a \cdot \operatorname{fib}(i-1)+b \cdot \operatorname{fib}(i-2)$ 856 857 By iterating further, we obtain $A_{m-2}=a \cdot \operatorname{fib}(i-2)+b \cdot \operatorname{fib}(i-3)$, $\dots$ 858 859 The purpose of this is to make the iteration process rapidly decrease the value in the initial steps, similar to the fibonacci sequence. Intuitively, the larger the $i$ chosen, the higher the probability of finding a legal $A_{m-1}$. 860 861 The author did not provide a rigorous mathematical proof for this, but using a verification program which found a legal $A_{m-1}$ for all $A_m=n \in [2,10^7]$ within one minute. Therefore, it is feasible to prove the correctness of this approach within the data range during the contest. 862 863 **Code (C++)** 864 865 ``` 866 #include<bits/stdc++.h> 867 using namespace std; 868 int fl[1005],inf=1e9,cnt; 869 int work(int x,int y){ 870 int ans=0,tmp; 871 while(y&&ans<=50){ 872 ++ans; tmp=y; 873 if (x>y) y=x-y; else y=y-x; 874 x=tmp; 875 } 876 if (x>1) return inf; 877 return ans; 878 } 879 void gen(int x,int y){ 880 //printf("%d\n",work(x,y)); 881 vector<int> seq; seq.clear(); seq.push_back(x); seq.push_back(y); 882 int tmp; 883 while(!(x==2&&y==1)){ 884 tmp=y; 885 if (x>y) y=x-y; else y=y-x;//x=tmp; 886 x=tmp; 887 seq.push_back(y); 888 } 889 int ans[55][55]={0}; 890 int pre=seq.back(),n=1; seq.pop_back(); ans[1][1]=1; 891 while(!seq.empty()){ 892 ++n; 893 if (seq.back()>pre) ans[n][n]=1,ans[n][n-1]=1,ans[n-1][n]=-1; 894 else ans[n][n]=1,ans[n][n-1]=1,ans[n-1][n]=1; 895 pre=seq.back(); seq.pop_back(); 896 } 897 printf("%d\n",n); 898 for(int i=1;i<=n;++i){ 899 for(int j=1;j<=n;++j){ 900 printf("%d ",ans[i][j]); 901 } 902 printf("\n"); 903 } 904 } 905 typedef long long ll; 906 ll fib[55]={1,1}; 907 ll exgcd(ll a,ll b,ll &x,ll &y){ 908 if(!b){ 909 x=1; y=0; return a; 910 } 911 ll d=exgcd(b,a%b,y,x); 912 y-=(a/b)*x; 913 return d; 914 } 915 map<int,int> mp; 916 int main(){ 917 for(int i=2;i<=50;++i) fib[i]=fib[i-1]+fib[i-2]; 918 int _; cin>>_; 919 while(_--){ 920 int n; cin>>n; 921 if (n==0) {printf("1\n0\n"); continue;} 922 if (n==1) {printf("1\n1\n"); continue;} 923 if (n<=10){ 924 gen(n,n-1); continue; 925 } 926 if (mp[n]) {gen(n,mp[n]); continue;} 927 int noww=0; 928 while(fib[noww]<n) ++noww; 929 int now=noww; 930 while(now>=3){ 931 ll a=fib[now-1],b=fib[now-2],x,y,c=n; 932 ll d=exgcd(a,b,x,y); 933 x*=c,y*=c; 934 //find x,y 935 x=(x%b+b)%b; y=(c-a*x)/b; if (y<0) {--now; continue;} 936 int s=inf,o; 937 while(y>=0){ 938 o=fib[now-2]*x+fib[now-3]*y; 939 s=work(n,o); 940 if (s>50) {x+=b,y-=a; continue;} 941 else break; 942 } 943 if (s>50) {--now; continue;} 944 else{ 945 gen(n,o); mp[n]=o; break; 946 } 947 } 948 // 949 } 950 return 0; 951 } 952 ``` 953 954 **Solution B** 955 956 We note that for the fibonacci sequence, $\lim_{x \to \infty} \frac{\operatorname{fib}(x-1)}{\operatorname{fib}(x)} = \frac{\sqrt 5 -1}{2}$, which suggests that searching for $A_{m-1}$ around $\frac{\sqrt 5 -1}{2}n$ might be a promising approach. 957 958 In fact, directly enumerating $A_{m-1}$ starting from $\frac{\sqrt 5 -1}{2}n$ and trying each one is a efficient method. The author also verified through a verification program that for all $A_m=n \in [2,10^7]$, a legal $A_{m-1}$ was found within one minute. Thus, it is feasible to prove the correctness of this approach within the data range during the contest. 959 960 Considering that the time limit for this problem is relatively loose (5s), most attempts to search for $A_{m-1}$ around $\frac{\sqrt 5 -1}{2}n$ may be able to pass. 961 962 **Code (C++)** 963 964 ``` 965 #include<bits/stdc++.h> 966 using namespace std; 967 int fl[1005],inf=1e9,cnt; 968 int work(int x,int y){ 969 int ans=0,tmp; 970 while(y&&ans<=50){ 971 ++ans; tmp=y; 972 if (x>y) y=x-y; else y=y-x; 973 x=tmp; 974 } 975 if (x>1) return inf; 976 return ans; 977 } 978 void gen(int x,int y){ 979 //printf("%d\n",work(x,y)); 980 vector<int> seq; seq.clear(); seq.push_back(x); seq.push_back(y); 981 int tmp; 982 while(!(x==2&&y==1)){ 983 tmp=y; 984 if (x>y) y=x-y; else y=y-x;//x=tmp; 985 x=tmp; 986 seq.push_back(y); 987 } 988 int ans[55][55]={0}; 989 int pre=seq.back(),n=1; seq.pop_back(); ans[1][1]=1; 990 while(!seq.empty()){ 991 ++n; 992 if (seq.back()>pre) ans[n][n]=1,ans[n][n-1]=1,ans[n-1][n]=-1; 993 else ans[n][n]=1,ans[n][n-1]=1,ans[n-1][n]=1; 994 pre=seq.back(); seq.pop_back(); 995 } 996 printf("%d\n",n); 997 for(int i=1;i<=n;++i){ 998 for(int j=1;j<=n;++j){ 999 printf("%d ",ans[i][j]); 1000 } 1001 printf("\n"); 1002 } 1003 } 1004 map<int,int> mp; 1005 int main(){ 1006 int _; cin>>_; 1007 while(_--){ 1008 int n; cin>>n; 1009 if (n==0) {printf("1\n0\n"); continue;} 1010 if (n==1) {printf("1\n1\n"); continue;} 1011 if (mp[n]) {gen(n,mp[n]); continue;} 1012 double s=(sqrt(5)-1.0)/2.0; 1013 int st=s*n,l=max(1,st),r=n-1; 1014 //int l=1,r=n-1; 1015 int nowy,nows=50; 1016 if (n%2==0){ 1017 if (l%2==0) ++l; 1018 for(int y=l;y<=r;y+=2){ 1019 int tmp=work(n,y); 1020 if (tmp<=nows) {gen(n,y); mp[n]=y; break;} 1021 } 1022 } 1023 else{ 1024 for(int y=l;y<=r;++y){ 1025 int tmp=work(n,y); 1026 if (tmp<=nows) {gen(n,y); mp[n]=y; break;} 1027 } 1028 } 1029 } 1030 return 0; 1031 } 1032 ``` 1033 1034 **Rate this problem** 1035 1036 * Amazing problem: 1037 * Good problem: 1038 * Average problem: 1039 * Bad problem: 1040 * Horrible problem: 1041 1042 [2139F — Ode to the Bridge Builder](https://codeforces.com/contest/2138/problem/F) 1043 1044 Idea: [installb](/profile/installb "Grandmaster installb") Preparation: [installb](/profile/installb "Grandmaster installb") 1045 1046 **Solution** 1047 1048 For convenience, we mark the targets point and the points on the initial segment with $A(0,0),B(1,0),C(p,q)$. 1049 1050 The problem asks us to do at most $\left\lceil 2|AC|\right\rceil$ moves. This constraint is actually not quite usual. We can first show that the theoretical lower bound should be $x=\left\lceil |AC|\right\rceil+\left\lceil |BC|\right\rceil−1$. We can show we can't get less moves by following: If we have already constructed the final structure, then $AC$ and $BC$ should be connected with a path, and we can find a path from $A$ to $C$ and a path from $B$ to $C$ that don't intersect (except at point $C$), otherwise the structure can't be built with non-degenerate triangles. 1051 1052 And we have to alternate progressing through two paths every time we construct a triangle, otherwise we must draw a line longer than $1$. The last triangle will cover both paths, so the number of steps will be decreased by one. The optimal path is two straight segments (which is not always possible). 1053 1054 **Case 1.1:** We first try some simple strategies. Two triangles can form a parallelogram, so we can connect $AC$, choose a point $D$ on $AC$ which makes $|AD|=\frac{|AC|}{\lceil|AC|\rceil}$, which is always in range $[0.5,1]$ when $|AC|\ge 1$. And from $\triangle ADB$ we can construct a parallelogram. We draw a line passing $D$ that is parallel to $AB$, a line passing $B$ that is parallel to $AC$, and they intersect at $E$. Then we pile up the same parallelogram structure until we reach $C$. This always works when $30^\circ\le\angle CAB\le60^\circ$. 1055 1056 Proof: We first prove that all segments have length between $0.5$ and $1$. Because we stack the same parallelogram structure, all segments have length equal to $AB,BD$ or $AD$. $AB$ and $AD$ already meet the requirement. When $30^\circ\le\angle CAB\le60^\circ$, the length of $BD$ is at least $0.5$ as the distance between two parallel lines is at least $0.5$, and at most $1$ as $AB=1$ and $\angle CAB$ is never the largest angle in $\triangle DAB$. We can calculate that the number of moves we used is $2\left\lceil |AC|\right\rceil-1\le\left\lceil 2|AC|\right\rceil$ which matches the requirement (for the last parallelogram we only need one triangle). 1057 1058  1059 1060 **Case 1.2:** We can change the way we construct parallelograms (with sides $AB,BC$) and this method always works when $30^\circ\le\angle CBx\le60^\circ$. The number of moves is $\left\lceil2|BC|\right\rceil\le \left\lceil 2|AC|\right\rceil$. This case is actually necessary, which will be explained in the following part. 1061 1062  1063 1064 **Case 2:** If $\angle CAB \lt \angle CBx \lt 30^\circ$. We first build a point $D$ which makes $AD=1$ and $\angle DAB=30^\circ$ and construct $\triangle DAB$. 1065 1066 We can show that the constraint is actually easier to meet in this situation, because when $\angle CAB \lt \angle CBx \lt 30^\circ$, $|BC| \lt |AC|-0.5$. With this, $\left\lceil |AC|\right\rceil+\left\lceil |BC|\right\rceil−1=\left\lceil 2|AC|\right\rceil-1$ always holds, allowing us one extra move. 1067 1068 Then we draw a line passing $D$ parallel to $BC$. We can show that if $\angle DAB=30^\circ$ and $0\le \angle CAB\le 30^\circ$, the distance from $D$ to line $BC$ is at least $0.5$. So all segments with ends on different lines will have length $\ge 0.5$. 1069 1070 Then we select a point $E$ on $BC$, which makes $DE=1$. We can show that $\sqrt{3}-1\le |BE|\le 1$ based on some calculations in this case. Then we do a similar parallelogram construction process to $C$. The total number of moves is $2\left\lceil |CE|\right\rceil+2$. 1071 1072 There are still two cases here to analyze to prove the number of steps fulfills our requirement. We write $|BC|=a+b$ where $a$ is the integer part of $|BC|$, then we analyze cases about $b$. 1073 1074 * Case 2.1: When $b\ge\sqrt{3}-1$ or $b=0$, we can show that $2\left\lceil |AC|\right\rceil=\left\lceil 2|AC|\right\rceil$, and $\left\lceil |AC|\right\rceil=\left\lceil |BC|\right\rceil+1$ if $|AC|\ge 2$. The number of steps is $2\left\lceil |EC|\right\rceil+2\le 2\left\lceil |BC|\right\rceil+2=2\left\lceil |AC|\right\rceil$. 1075 * Case 2.2: When $0 \lt b \lt \sqrt{3}-1$, we can show that $\left\lceil |EC|\right\rceil=\left\lceil |BC|\right\rceil-1$. The number of steps equals to $2+2\left\lceil |CE|\right\rceil=2\left\lceil |BC|\right\rceil\le \left\lceil |AC|\right\rceil+\left\lceil |BC|\right\rceil=\left\lceil 2|AC|\right\rceil$. 1076 1077 Be careful with small cases where $|BC|$ is too short, which may make $|DF|=|EG| \lt 0.5$. 1078 1079 Note that there are some cases where $\angle CBx \gt 30^\circ$ and $\angle CAB \lt 30^\circ$, where Case 2 strategy doesn't work. So case 1.2 is required. 1080 1081  1082 1083 **Case 3:** If $\angle CBx \gt \angle CAB \gt 60^\circ$. We first build a point $D$ which makes $AD=1$ and $\angle DAB=60^\circ$ and construct $\triangle DAB$. We write $|AC|=a+b$ where $a$ is integer, then we analyze two cases about $b$. 1084 1085 **Case 3.1:** When $b \gt 0.5$ or $b=0$, $2\left\lceil |AC|\right\rceil=\left\lceil 2|AC|\right\rceil$. We begin a same parallelogram construction as Case 1 where the sides of parallelogram are $BC,BD$. We can show that $30^\circ\le\angle CBD\le60^\circ$. So it is possible to pile up to $C$ from $BD$ in $2\left\lceil |BC|\right\rceil-1$ moves. And in total we need $2\left\lceil |BC|\right\rceil\le2\left\lceil |AC|\right\rceil=\left\lceil 2|AC|\right\rceil$ moves. 1086 1087  1088 1089 **Case 3.2:** When $0 \lt b\le 0.5$, $2\left\lceil |AC|\right\rceil=\left\lceil 2|AC|\right\rceil+1$. We instead connect $CD$ and construct parallelogram with sides $DC,DB$. We can show that $120^\circ\le\angle CDB\le150^\circ$ so we can still do the parallelogram construction. When $|AC|\ge \sqrt{3}$, $\left\lceil |CD|\right\rceil=\left\lceil |AC||\right\rceil-1$, making the number of moves $2\left\lceil |CD|\right\rceil+1=2\left\lceil |AC|\right\rceil-1=\left\lceil 2|AC|\right\rceil$. 1090 1091  1092 1093 Actually case 1.1 is not required, because it is impossible to construct a testcase where $\angle CAB \lt 60^\circ, \angle CBx \gt 60^\circ,0 \lt b\le 0.5$ and Case 3.2 fails. 1094 1095 **Code (C++)** 1096 1097 ``` 1098 #include <bits/stdc++.h> 1099 using namespace std; 1100 typedef double db; 1101 const db pi = acos(-1.0); 1102 const int N = 1000005; 1103 1104 inline int sgn(db x){ 1105 if(x < 1e-13 && x > -1e-13) return 0; 1106 if(x > 0) return 1; 1107 return -1; 1108 } 1109 1110 struct point{ 1111 db x,y; 1112 point (db _x = 0.0,db _y = 0.0) : x(_x), y(_y) {} 1113 }; 1114 point operator + (const point &p1,const point &p2){ 1115 return point(p1.x + p2.x,p1.y + p2.y); 1116 } 1117 point operator - (const point &p1,const point &p2){ 1118 return point(p1.x - p2.x,p1.y - p2.y); 1119 } 1120 point operator * (db x,const point &p){ 1121 return point(x * p.x,x * p.y); 1122 } 1123 bool operator == (point x,point y){ 1124 return sgn(x.x - y.x) == 0 && sgn(x.y - y.y) == 0; 1125 } 1126 1127 inline db dot(point p1,point p2){ 1128 return p1.x * p2.x + p1.y * p2.y; 1129 } 1130 1131 inline db det(point p1,point p2){ 1132 return p1.x * p2.y - p2.x * p1.y; 1133 } 1134 1135 inline db len(point p){ 1136 return sqrtl(1.0 * p.x * p.x + 1.0 * p.y * p.y); 1137 } 1138 1139 point project_point(point x,point ya,point yb){ 1140 point v = yb - ya; 1141 return ya + (dot(v,x - ya) / dot(v,v)) * v; 1142 } 1143 1144 db distp(point x,point ya,point yb){ 1145 return fabs(det(ya - x,yb - x)) / len(yb - ya); 1146 } 1147 1148 point line_circle_intersec_point(point o,point la,point lb){ 1149 db dis = distp(o,la,lb),l; 1150 point pj = project_point(o,la,lb); 1151 l = sqrt(1.0 - dis * dis); 1152 point ret = pj + (l / len(lb - la)) * (lb - la); 1153 return ret; 1154 } 1155 1156 tuple <int,int,int> ans[N]; 1157 point p[N],target; 1158 int step; 1159 1160 bool check(int n){ 1161 set <pair <int,int> > st; 1162 st.insert({1,2}); 1163 if(n > step) return 0; 1164 db eps_len = 1e-8,eps_dis = 1e-4; 1165 int fl = 0; 1166 for(int i = 1;i <= n;i ++){ 1167 auto [u,v,w] = ans[i]; 1168 if(u > v) swap(u,v); 1169 if(st.find({u,v}) == st.end()) return 0; 1170 if(len(p[u] - p[w]) < 0.5 - eps_len || len(p[u] - p[w]) > 1.0 + eps_len) return 0; 1171 if(len(p[v] - p[w]) < 0.5 - eps_len || len(p[v] - p[w]) > 1.0 + eps_len) return 0; 1172 st.insert({u,w}); st.insert({v,w}); 1173 if(len(p[w] - target) <= eps_dis) fl = 1; 1174 } 1175 return 1; 1176 } 1177 1178 int solve1a(){ 1179 point dir = target - p[1]; 1180 int split = ceil(len(dir) - 1e-9); 1181 int c = 2; 1182 for(int i = 1;i < split;i ++){ 1183 ++ c; p[c] = p[1] + (1.0 * i / split) * dir; 1184 ans[c - 2] = {c - 2,c - 1,c}; 1185 ++ c; p[c] = p[2] + (1.0 * i / split) * dir; 1186 ans[c - 2] = {c - 2,c - 1,c}; 1187 // construct one parallelogram 1188 } 1189 ++ c; p[c] = target; 1190 ans[c - 2] = {c - 2,c - 1,c}; 1191 if(check(c - 2)) return c - 2; 1192 return 0; 1193 } 1194 1195 int solve1b(){ 1196 point dir = target - p[2]; 1197 int split = ceil(len(dir) - 1e-9); 1198 int c = 2; 1199 for(int i = 1;i <= split;i ++){ 1200 ++ c; p[c] = p[1] + (1.0 * i / split) * dir; 1201 ans[c - 2] = {c - 2,c - 1,c}; 1202 ++ c; p[c] = p[2] + (1.0 * i / split) * dir; 1203 ans[c - 2] = {c - 2,c - 1,c}; 1204 } 1205 if(check(c - 2)) return c - 2; 1206 return 0; 1207 } 1208 1209 int solve2(){ 1210 p[3] = point(sqrt(3.0) / 2,0.5); 1211 p[4] = line_circle_intersec_point(p[3],p[2],target); 1212 if(len(p[4] - p[2]) > 1) 1213 p[4] = p[2] + (1.0 / len(target - p[2])) * (target - p[2]); 1214 ans[1] = {1,2,3}; 1215 ans[2] = {2,3,4}; 1216 point dir = target - p[4]; 1217 int split = ceil(len(dir) - 1e-9); 1218 int c = 4; 1219 for(int i = 1;i <= split;i ++){ 1220 ++ c; p[c] = p[3] + (1.0 * i / split) * dir; 1221 ans[c - 2] = {c - 2,c - 1,c}; 1222 ++ c; p[c] = p[4] + (1.0 * i / split) * dir; 1223 ans[c - 2] = {c - 2,c - 1,c}; 1224 } 1225 if(check(c - 2)) return c - 2; 1226 return 0; 1227 } 1228 1229 int solve3a(){ 1230 p[3] = point(0.5,sqrt(3.0) / 2); 1231 ans[1] = {1,2,3}; 1232 point dir = target - p[2]; 1233 int split = ceil(len(dir) - 1e-9); 1234 int c = 3; 1235 for(int i = 1;i < split;i ++){ 1236 ++ c; p[c] = p[2] + (1.0 * i / split) * dir; 1237 ans[c - 2] = {c - 2,c - 1,c}; 1238 ++ c; p[c] = p[3] + (1.0 * i / split) * dir; 1239 ans[c - 2] = {c - 2,c - 1,c}; 1240 } 1241 ++ c; p[c] = target; 1242 ans[c - 2] = {c - 2,c - 1,c}; 1243 if(check(c - 2)) return c - 2; 1244 return 0; 1245 } 1246 1247 int solve3b(){ 1248 p[3] = point(0.5,sqrt(3.0) / 2); 1249 ans[1] = {1,2,3}; 1250 point dir = target - p[3]; 1251 int split = ceil(len(dir) - 1e-9); 1252 int c = 3; 1253 for(int i = 1;i <= split;i ++){ 1254 ++ c; p[c] = p[2] + (1.0 * i / split) * dir; 1255 ans[c - 2] = {c - 2,c - 1,c}; 1256 ++ c; p[c] = p[3] + (1.0 * i / split) * dir; 1257 ans[c - 2] = {c - 2,c - 1,c}; 1258 } 1259 if(check(c - 2)) return c - 2; 1260 return 0; 1261 } 1262 1263 int solve(){ 1264 if(int res = solve1a()) return res; 1265 if(int res = solve1b()) return res; 1266 if(int res = solve2()) return res; 1267 if(int res = solve3a()) return res; 1268 if(int res = solve3b()) return res; 1269 return 0; 1270 } 1271 1272 int main(){ 1273 int TC; scanf("%d",&TC); 1274 p[1] = point(0,0); 1275 p[2] = point(1,0); 1276 while(TC --){ 1277 int tx,ty; 1278 scanf("%d %d %d",&tx,&ty,&step); 1279 step = ceil(2.0 * sqrt(1.0 * tx * tx + 1.0 * ty * ty)); 1280 target = point(tx,ty); 1281 int n = solve(); 1282 assert(n > 0); 1283 printf("%d\n",n); 1284 for(int i = 1;i <= n;i ++){ 1285 auto [u,v,w] = ans[i]; 1286 printf("%d %d %.12lf %.12lf\n",u,v,p[w].x,p[w].y); 1287 } 1288 } 1289 return 0; 1290 } 1291 ``` 1292 1293 **Rate this problem** 1294 1295 * Amazing problem: 1296 * Good problem: 1297 * Average problem: 1298 * Bad problem: 1299 * Horrible problem: