1428.md (35460B)
1 Source: https://codeforces.com/blog/entry/83771 2 3 ## [1428A - Box is Pull](/contest/1428/problem/A) 4 5 Setter: [bensonlzl](/profile/bensonlzl "Master bensonlzl") 6 Prepared by: [errorgorn](/profile/errorgorn "Grandmaster errorgorn") 7 8 **Hint 1** 9 10 Consider when $x_1=x_2$ 11 12 **Hint 2** 13 14 Consider when $x_1 \ne x_2$ 15 16 **Solution** 17 18 We consider 2 cases. 19 20 The first is that the starting and ending point lie on an axis-aligned line. In this case, we simply pull the box in 1 direction, and the time needed is the distance between the 2 points as we need 1 second to decrease the distance by 1. 21 22 The second is that they do not lie on any axis-aligned line. Wabbit can pull the box horizontally (left or right depends on the relative values of $x_1$ and $x_2$) for $|x_1-x_2|$ seconds, take 2 seconds to move either above or below the box, then take another $|y_1-y_2|$ seconds to move the box to $(x_2,y_2)$. 23 24 **Code (C++)** 25 26 ``` 27 #include <bits/stdc++.h> 28 29 using namespace std; 30 31 int main(){ 32 ios_base::sync_with_stdio(false); 33 cin.tie(0); 34 int t, x1, y1, x2, y2; 35 cin >> t; 36 for (int i = 1; i <= t; ++i){ 37 cin >> x1 >> y1 >> x2 >> y2; 38 if (x1 == x2 || y1 == y2){ 39 cout << abs(x1-x2) + abs(y1-y2) << '\n'; 40 } 41 else cout << abs(x1-x2) + abs(y1-y2) + 2 << '\n'; 42 } 43 } 44 ``` 45 46 **Code (Python)** 47 48 ``` 49 tc=int(input()) 50 for i in range(tc): 51 a,b,c,d=map(int,input().split(" ")) 52 53 ans=abs(a-c)+abs(b-d) 54 if (a!=c and b!=d): ans+=2 55 56 print(ans) 57 ``` 58 59 ## [1428B - Belted Rooms](/contest/1428/problem/B) 60 61 Setter: [oolimry](/profile/oolimry "Master oolimry") 62 Prepared by: [oolimry](/profile/oolimry "Master oolimry") 63 64 **Hint 1** 65 66 There are 2 cases to consider for a room to be returnable. 67 68 **Hint 2** 69 70 For a room to be returnable, either go one big round around all the rooms or move to an adjacent room and move back. 71 72 **Solution** 73 74 Let's consider two ways to return to the start point. The first is to go one big round around the circle. The second is to move 1 step to the side, and return back immediately. 75 76 Going one big round is only possible if and only if: 77 78 * There are no clockwise belts OR 79 * There are no anticlockwise belts 80 81 If we can go one big round, all rooms are returnable. 82 83 If there are both clockwise and anticlockwise belts, then we can't go one big round. For any room to be returnable, it must have an **off** belt to the left or to the right. 84 85 In summary, check if clockwise belts are absent or if anticlockwise belts are absent. If either is absent, the answer is $n$. Otherwise, we have to count the number of rooms with an **off** belt to the left or to the right. 86 87 **Other comments** 88 89 Sorry for the unclear statement for B, we should've explained each sample testcase more clearly with better diagrams. Additionally, we're also sorry for the weak pretests. We should've added more testcases of smaller length, and thanks to hackers for adding stronger tests. 90 91 **Code (C++)** 92 93 ``` 94 #include <bits/stdc++.h> 95 using namespace std; 96 97 int main(){ 98 ios_base::sync_with_stdio(false); cin.tie(0); 99 100 int TC; cin >> TC; 101 while(TC--){ 102 int n; cin >> n; 103 string s; cin >> s; 104 105 bool hasCW = false; 106 bool hasCCW = false; 107 for(int i = 0;i < n;i++){ 108 if(s[i] == '<') hasCW = true; 109 if(s[i] == '>') hasCCW = true; 110 } 111 112 if(hasCW && hasCCW){ 113 int ans = 0; 114 s += s[0]; 115 for(int i = 0;i < n;i++){ 116 if(s[i] == '-' || s[i+1] == '-') ans++; 117 } 118 cout << ans << "\n"; 119 } 120 else{ 121 cout << n << "\n"; 122 } 123 } 124 } 125 ``` 126 127 **Code (Python)** 128 129 ``` 130 TC = int(input()) 131 for tc in range(TC): 132 n = int(input()) 133 s = input() 134 135 hasCW = False 136 hasCCW = False 137 for c in s: 138 if c == '>': 139 hasCW = True 140 if c == '<': 141 hasCCW = True 142 143 if hasCW and hasCCW: 144 s += s[0] 145 ans = 0; 146 for i in range(n): 147 if s[i] == '-' or s[i+1] == '-': 148 ans += 1 149 print(ans) 150 151 else: 152 print(n) 153 ``` 154 155 ## [1428C - ABBB](/contest/1428/problem/C) 156 157 Setter: [errorgorn](/profile/errorgorn "Grandmaster errorgorn") and [shenxy13](/profile/shenxy13 "Grandmaster shenxy13") 158 Prepared by: [errorgorn](/profile/errorgorn "Grandmaster errorgorn") and [oolimry](/profile/oolimry "Master oolimry") 159 160 **Hint 1** 161 162 `AB` and `BB` means that `?B` can be removed. 163 164 **Hint 2** 165 166 The final string is `BAAA...` or `AAA...`. 167 168 **Solution** 169 170 This game is equivalent to processing left to right and maintaining a stack. If the current processed character is `A`, we add it to the stack, if the current processed character is `B`, we can either add it to the stack or pop the top of the stack. 171 172 In the optimal solution, we will always pop from the stack whenever possible. To prove this, we will use the stay ahead argument. 173 174 Firstly, we notice that the contents of the stack do not actually matter. We actually only need to maintain the length of this stack. Decrementing the size of the stack whenever possible is optimal as it is the best we can do. And in the case where we must push `B' to the stack, this is optimal as the parity of the length of the stack must be the same as the parity of the processed string, so obtaining a stack of length 0 is impossble. 175 176 **Bonus:** what is the length of the longest string that Zookeeper can make such that there are no moves left? 177 178 **Other comments** 179 180 We're also sorry for the weak pretests in this problem. About 1 hour before the contest, we found out that c++ $O(N^2)$ solution using `find` and `erase` would pass. Then we added testcases to kill the c++ solutions, but we didn't test the $O(N^2)$ solution for python using `replace`. 181 182 **Code (C++)** 183 184 ``` 185 //雪花飄飄北風嘯嘯 186 //天地一片蒼茫 187 188 #include <bits/stdc++.h> 189 #include <ext/pb_ds/assoc_container.hpp> 190 #include <ext/pb_ds/tree_policy.hpp> 191 #include <ext/rope> 192 using namespace std; 193 using namespace __gnu_pbds; 194 using namespace __gnu_cxx; 195 #define ll long long 196 #define ii pair<ll,ll> 197 #define iii pair<ii,ll> 198 #define fi first 199 #define se second 200 #define endl '\n' 201 #define debug(x) cout << #x << " is " << x << endl 202 203 #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 204 #define all(x) (x).begin(),(x).end() 205 #define sz(x) (int)(x).size() 206 207 #define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> 208 //change less to less_equal for non distinct pbds, but erase will bug 209 210 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); 211 212 int main(){ 213 ios::sync_with_stdio(0); 214 cin.tie(0); 215 cout.tie(0); 216 cin.exceptions(ios::badbit | ios::failbit); 217 218 int TC; 219 cin>>TC; 220 221 while (TC--){ 222 string s; 223 cin>>s; 224 225 int stk=0; 226 227 rep(x,0,sz(s)){ 228 if (stk && s[x]=='B') stk--; 229 else stk++; 230 } 231 232 cout<<stk<<endl; 233 } 234 } 235 ``` 236 237 **Code (Python)** 238 239 ``` 240 TC = int(input()) 241 for tc in range(TC): 242 s = input() 243 ans=0 244 for i in s: 245 if (i=='B' and ans!=0): ans-=1 246 else: ans+=1 247 print(ans) 248 ``` 249 250 ## [1428D - Bouncing Boomerangs](/contest/1428/problem/D) 251 252 Setter: [bensonlzl](/profile/bensonlzl "Master bensonlzl") 253 Prepared by: [bensonlzl](/profile/bensonlzl "Master bensonlzl") 254 255 **Hint 1** 256 257 Consider $a_i \in \{0,1,2\}$. 258 259 **Hint 2** 260 261 Consider $a_i=\{3,3,3, \ldots , 3,1\}$. 262 263 **Solution** 264 265 Clearly, columns with $a_j=0$ are completely empty and we can ignore them. 266 267 Let's first consider just columns with $1$ s and $2$ s. When a boomerang strikes its first target, it will change directions from upwards to rightwards. If $a_j=1$, the boomerang in column $j$ exits the grid on the right. 268 269  270 271 This means that if the target that it hits in on row $r$, there is no other target to its right on row $r$. 272 273 For columns with $a_j=2$, the boomerang in column $j$ has to hit second target in some column $k$ before moving downwards. 274 275  276 277 The $2$ targets that this boomerang hits must be in the same row, and since no row contains more than $2$ targets, these are the only $2$ targets in the row. Additionally, there isn't any target below the second target. This means $a_k=1$. 278 279 This tells us that columns $j$ with $a_j=2$ must be matched with columns $k$ with $a_k=1$ to its right with $j \lt k$. If we only had $a_j=1$ and $a_j=2$, we can simply greedily match $2$ s to $1$ s that are available. 280 281 $3$ s initially seem difficult to handle. The key observation is that $3$ s can "link" to $3$ s to its right. The way to do this for the have the first target for one boomerang be the third target for another boomerang. 282 283  284 285 This allows us to "chain" the $3$ s together in one long chain. 286 287 Thus, we only care about the first $3$, which has to use either a $2$ or a $1$ (if it uses a $1$, that $1$ cannot be matched with a $2$). We should always use a $2$ if possible since it will never be used by anything else, and the exact $1$ that we use also doesn't matter. 288 289 Thus the solution is as follows: Process from right to left. If the current value is a $1$, add it to a list of available ones. If the current value is a $2$, match it with an available $1$ and remove the $1$ from the list. If the current value is a $3$, match it with $3$,$2$ or $1$ in that order of preference. 290 291 Once we have found the chains and matches, we can go from left to right and give each chain / match some number of rows to use so that they do not overlap. The final time complexity is $O(n)$. 292 293 **Bonus $1$:** Show that the directly simulating the path of each boomerang is overall $O(n)$. 294 295 **Bonus $2$ (unsolved):** Solve for $0 \leq a_j \leq 4$. 296 297 **Code (C++)** 298 299 ``` 300 #include <bits/stdc++.h> 301 302 using namespace std; 303 304 int N, A[100005], T; 305 306 vector<pair<int,int> > targets; 307 vector<int> ones, twos, threes; 308 309 int currow = 1, col[100005], twomatch[100005], threematch[100005]; 310 311 int main(){ 312 ios_base::sync_with_stdio(false); 313 cin.tie(0); 314 cin >> N; 315 for (int i = 1; i <= N; ++i){ 316 cin >> A[i]; 317 } 318 for (int i = N; i >= 1; --i){ 319 if (A[i] == 1){ 320 ones.push_back(i); 321 } 322 else if (A[i] == 2){ 323 if (ones.size() == 0){ 324 cout << -1 << '\n'; 325 return 0; 326 } 327 else{ 328 twomatch[i] = ones.back(); 329 ones.pop_back(); 330 } 331 twos.push_back(i); 332 } 333 else if (A[i] == 3){ 334 if (threes.size() > 0){ 335 threematch[i] = threes.back(); 336 } 337 else if (twos.size() > 0){ 338 threematch[i] = twos.back(); 339 } 340 else if (ones.size() > 0){ 341 threematch[i] = ones.back(); 342 ones.pop_back(); 343 } 344 else{ 345 cout << -1 << '\n'; 346 return 0; 347 } 348 threes.push_back(i); 349 } 350 } 351 for (int i = 1; i <= N; ++i){ 352 if (col[i] == 1 || A[i] == 0) continue; 353 int curcol = i; 354 while (curcol != 0){ 355 col[curcol] = 1; 356 if (A[curcol] == 1){ 357 targets.emplace_back(currow,curcol); 358 curcol = 0; 359 currow++; 360 } 361 else if (A[curcol] == 2){ 362 targets.emplace_back(currow,curcol); 363 curcol = twomatch[curcol]; 364 } 365 else if (A[curcol] == 3){ 366 targets.emplace_back(currow,curcol); 367 curcol = threematch[curcol]; 368 targets.emplace_back(currow,curcol); 369 currow++; 370 } 371 } 372 } 373 cout << targets.size() << '\n'; 374 for (auto it : targets){ 375 cout << it.first << ' ' << it.second << '\n'; 376 } 377 } 378 ``` 379 380 **Code (Python)** 381 382 ``` 383 def die(): 384 print(-1) 385 exit(0) 386 387 ones = [] 388 ans = [] 389 H = 1 390 lastThree = (-1,-1) 391 392 n = int(input()) 393 arr = list(map(int,input().split(" "))) 394 395 for i in range(n-1, -1, -1): 396 if arr[i] == 0: 397 continue 398 elif arr[i] == 1: 399 ones.append((i,H)) 400 ans.append((i,H)) 401 H += 1 402 elif arr[i] == 2: 403 if len(ones) == 0: 404 die() 405 T = ones[-1] 406 ones.pop() 407 ans.append((i, T[1])) 408 lastThree = (i,T[1]) 409 elif arr[i] == 3: 410 if lastThree[0] == -1: 411 if len(ones) == 0: 412 die() 413 else: 414 lastThree = ones[-1] 415 ones.pop() 416 ans.append((i, H)) 417 ans.append((lastThree[0], H)) 418 lastThree = (i,H) 419 H += 1 420 421 print(len(ans)) 422 for ii in ans: 423 print(n-ii[1] + 1, end = ' ') 424 print(ii[0] + 1) 425 ``` 426 427 ## [1428E - Carrots for Rabbits](/contest/1428/problem/E) 428 429 Setter: [errorgorn](/profile/errorgorn "Grandmaster errorgorn") 430 Prepared by: [errorgorn](/profile/errorgorn "Grandmaster errorgorn") 431 Orz proof by: [oolimry](/profile/oolimry "Master oolimry") 432 433 **Hint 1** 434 435 Greedy. 436 437 **Hint 2** 438 439 Let us define $f(l,p)$ as the sum of time needed when we have a single carrot of length $l$ and it is split into $p$ pieces. 440 441 We can show that $f(l,p−1)−f(l,p)≥f(l,p)−f(l,p+1)$. 442 443 **Solution** 444 445 Let us define $f(l,p)$ as the sum of time needed when we have a single carrot of length $l$ and it is split into $p$ pieces. 446 447 **More details** 448 449 In an optimal cutting for a single carrot, we will only cut it into pieces of length $w$ and $w+1$, for some $w$. 450 451 Such cutting is optimal as suppose we have $2$ pieces of length $\alpha$ and $\beta$, and $\alpha+2 \leq \beta$. Then, it is better to replace those $2$ pieces of carrots with length $\alpha+1$ and $\beta-1$, since $(\alpha+1)^2+(\beta-1)^2 \leq \alpha^2+\beta^2$. 452 453 To calculate $f(l,p)$, we need to find $p_1,p_2$ such that $p_1 (w) + p_2 (w+1)=l$ and $p_1+p_2=p$, minimizing $p_1(w)^2+p_2(w+1)^2$. 454 455 Clearly, $w=\lfloor \frac{l}{p} \rfloor$ and $p_2=l\mod p$. Thus, calculating $f(l,p)$ can be done in $O(1)$. 456 457 We can use the following greedy algorithm. We consider making zero cuts at first. We will make $k$ cuts one by one. When deciding where to make each cut, consider for all the carrots, which carrot gives us the largest decrease in cost when we add an extra cut. If a carrot of length $l$ currently is in $p$ pieces, then the decrease in cost by making one extra cut is $f(l,p) - f(l,p+1)$. 458 459 The important observation here is that $f(l,p-1)-f(l,p) \geq f(l,p)-f(l,p+1)$. 460 461 **Proof** 462 463 Consider $f(2l,2p)$. 464 465 Since the length is even and we have an even number of pieces, we know that the will be one cut down the middle and each half will have $p$ pieces. As such, $f(2l,2p) = 2f(l,p)$ This is because there even number of $w$ length pieces and an even number of $w+1$ length pieces, hence the left half and the right half are the same. 466 467 Also, $f(l,p-1) + f(l,p+1) \geq f(2l,2p)$, since $f(l,p-1) + f(l,p+1)$ is describing cutting a carrot of length $2l$ first into $2$ carrots of length $l$ and cutting it into $p-1$ and $p+1$ pieces respectively. The inequality must hold because this is a way to cut a carrot of length $2l$ into $2p$ pieces. 468 469 Since we have $f(l,p-1) + f(l,p+1) \geq f(2l,2p)$ and $f(2l,2p) = 2f(l,p)$. 470 471 We have $f(l,p-1) + f(l,p+1) \geq f(l,p) + f(l,p)$. 472 473 Rearranging terms gives $f(l,p-1)-f(l,p) \geq f(l,p)-f(l,p+1)$ 474 475 In other words, the more cuts we make to a carrot, there is a diminishing returns in the decrease in cost per cut. As such, For any carrot, we don't need to think about making the $(p+1)$-th cut before making the $p$-th cut. 476 477 Hence, all we need to do is choose carrot with the largest decrease in cost, and add one extra cut for that. Which carrot has the largest decrease in cost can be maintained with a priority queue. Hence, we get a time complexity of $O(klog(n))$. 478 479 **Bonus:** solve this problem for $k \leq 10^{18}$. 480 481 **Other comments** 482 483 When preparing this problem, I started with putting $n,k\leq 5000$ because i thought if I put larger values it would be guessforces. However, several testers made $O(nk \log n)$ and $O(nk)$ dp solutions. Which version of the problem do you think is better? 484 485 **Code (C++)** 486 487 ``` 488 //雪花飄飄北風嘯嘯 489 //天地一片蒼茫 490 491 #include <bits/stdc++.h> 492 #include <ext/pb_ds/assoc_container.hpp> 493 #include <ext/pb_ds/tree_policy.hpp> 494 #include <ext/rope> 495 using namespace std; 496 using namespace __gnu_pbds; 497 using namespace __gnu_cxx; 498 #define ll long long 499 #define ii pair<ll,ll> 500 #define iii pair<ll,ii> 501 #define fi first 502 #define se second 503 #define endl '\n' 504 #define debug(x) cout << #x << " is " << x << endl; 505 506 #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 507 #define all(x) (x).begin(),(x).end() 508 #define sz(x) (int)(x).size() 509 510 #define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> 511 //change less to less_equal for non distinct pbds, but erase will bug 512 513 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); 514 515 int n,k; 516 ll cost=0; 517 priority_queue<iii> pq; 518 519 ll sq(ll i){ 520 return i*i; 521 } 522 523 ll val(ll len,ll nums){ 524 ll unit=len/nums; 525 ll extra=len-unit*nums; 526 527 return (nums-extra)*sq(unit)+extra*sq(unit+1); 528 } 529 530 int main(){ 531 ios::sync_with_stdio(0); 532 cin.tie(0); 533 cout.tie(0); 534 535 cin>>n>>k; 536 537 rep(x,0,n){ 538 ll t; 539 cin>>t; 540 cost+=sq(t); 541 542 pq.push(iii(val(t,1)-val(t,2),ii(t,2))); 543 } 544 545 rep(x,0,k-n){ 546 cost-=pq.top().fi; 547 int a=pq.top().se.fi,b=pq.top().se.se; 548 pq.pop(); 549 550 pq.push(iii(val(a,b)-val(a,b+1),ii(a,b+1))); 551 } 552 553 cout<<cost<<endl; 554 } 555 ``` 556 557 **Code (Python)** 558 559 ``` 560 from heapq import * 561 562 n,k=map(int,input().split(" ")) 563 564 def val(l,nums): 565 unit=l//nums 566 extra=l-unit*nums 567 return (nums-extra)*unit*unit+extra*(unit+1)*(unit+1) 568 569 pq=[] 570 arr=list(map(int,input().split(" "))) 571 572 total=0 573 for x in range(n): 574 total+=arr[x]*arr[x] 575 heappush(pq,(-val(arr[x],1)+val(arr[x],2),arr[x],2)) 576 577 for x in range(k-n): 578 temp=heappop(pq) 579 total+=temp[0] 580 a,b=temp[1],temp[2] 581 heappush(pq,(-val(a,b)+val(a,b+1),a,b+1)) 582 583 print(total) 584 ``` 585 586 ## [1428F - Fruit Sequences](/contest/1428/problem/F) 587 588 Setter: [bensonlzl](/profile/bensonlzl "Master bensonlzl") 589 Prepared by: [dvdg6566](/profile/dvdg6566 "Grandmaster dvdg6566") 590 591 **Hint 1** 592 593 Line sweep. 594 595 **Hint 2** 596 597 How does $f(l,r)$ change when we increase r? 598 599 **Solution** 600 601 For a fixed $r$, let us graph $f(l,r)$ in a histogram with $l$ as the $x$-axis. We notice that this histogram is non-increasing from left to right. Shown below is the histogram for the string $11101011$ with $r = 6$, where $1$ box represents $1$ unit. 602 603  604 605 The area under this histogram is the sum of all $f(l,r)$ for a fixed $r$. Consider what happens to the histogram when we move from $r$ to $r+1$. If $s_{r+1} = 0$, then the histogram does not change at all. If $s_{r+1} = 1$, then we may need to update the histogram accordingly. 606 607  608 609 Above is the histogram for $11101011$ when $r=7$. 610 611  612 613 And this is the histogram for $11101011$ when $r=8$. 614 615 When adding a new segment of $k$ $1$s, we essentially fill up the bottom $k$ rows of the histogram. Thus, we let $L_x$ be the largest $l$ such that $f(l,r) = x$. We maintain these $L_x$ values in an array. When we process a group of $k$ 1s, we update the values for $L_1, L_2, \cdots, L_k$, change the area of the histogram and update the cumulative sum accordingly. 616 617 With proper processing of the segments of 1s, this can be done in $O(n)$ time. 618 619 **Other comments** 620 621 Interestingly, many testers found F not much harder than E, as such we gave them the same score. However, it seems that F was signficicantly harder than E based on the number of solves. Another thing was that FST for this problem were caused by testdata that involved sequences of '1's of increasing length. 622 623 **Code (C++)** 624 625 ``` 626 #include <bits/stdc++.h> 627 628 using namespace std; 629 630 typedef long long ll; 631 632 ll hist[2000005], tot = 0, cur = 0; 633 int N, S[2000005]; 634 635 int main(){ 636 ios_base::sync_with_stdio(false); 637 cin.tie(0); 638 cin >> N; 639 for (int i = 1; i <= N; ++i){ 640 char x; 641 cin >> x; 642 S[i] = (x - '0'); 643 } 644 for (int i = 1; i <= N; ++i){ 645 if (S[i] == 0) tot += cur; 646 else{ 647 int l = i, r = i; 648 while (r < N && S[r+1] == 1) r++; 649 for (int x = 1; x <= (r-l+1); ++x){ 650 cur += (l-1+x) - hist[x]; 651 tot += cur; 652 hist[x] = r-x+1; 653 } 654 i = r; 655 } 656 } 657 cout << tot << '\n'; 658 } 659 ``` 660 661 **Code (Python)** 662 663 ``` 664 import sys 665 range = xrange 666 input = raw_input 667 668 inp=sys.stdin.read().split() 669 670 n = int(inp[0]) 671 s=inp[1] 672 673 tot=0 674 cur=0 675 676 hist=[0]*1000005 677 678 i=0 679 680 while (i<n): 681 if (s[i]=='0'): 682 tot+=cur 683 else: 684 l=i 685 r=i 686 while (r+1<n and s[r+1]=='1'): r+=1 687 for x in range(r-l+1): 688 cur+=(l+x+1)-hist[x] 689 tot+=cur 690 hist[x]=r-x+1 691 692 i=r 693 i+=1 694 695 print(tot) 696 ``` 697 698 ## [1428G1 - Lucky Numbers (Easy Version)](/contest/1428/problem/G1), [1428G2 - Lucky Numbers (Hard Version)](/contest/1428/problem/G2) 699 700 Setter: [oolimry](/profile/oolimry "Master oolimry") 701 Prepared by: [oolimry](/profile/oolimry "Master oolimry") 702 703 **Hint 1** 704 705 0 is a lucky number as well. 706 707 **Hint 2** 708 709 There is at most one number whose digits is not entirely 0, 3, 6, 9. 710 711 **Hint 3** 712 713 Knapsack. 714 715 **Hint 4** 716 717 Group same items. 718 719 **Solution** 720 721 Suppose in our final solution, there is a certain position (ones, tens...) that has two digits which are not $0$, $3$, $6$, or $9$. Let these two digits are $a$ and $b$. If $a+b \leq 9$, we can replace these two digits with $0$, and $a+b$. Otherwise, we can replace these two digits with $9$ and $a+b-9$. By doing this, our solution is still valid as the sum remains the same, and the total fortune will not decrease since $a$ and $b$ are not $3$, $6$ or $9$. 722 723 As such, in the optimal solution, there should be at most one number that consists of digits that are not $0$, $3$, $6$ or $9$. Let's call this number that has other digits $x$. 724 725 ### Easy Version 726 727 Since there's only one query, we can try all possibilities of $x$. The question reduces to finding the maximum sum of fortune among $k-1$ numbers containing the digits $0$, $3$, $6$ and $9$ that sum up to exactly $n-r$. We can model this as a 0-1 knapsack problem, where the knapsack capacity is $n-r$. 728 729 For the ones position, the value (fortune) can be increased by $F_0$ for a weight of $3$ a total of $3(k-1)$ times, so we can create $3(k - 1)$ objects of weight $3$ and value $F_0$. For tens it's $F_1$ for a weight of $30$, and so on. Since there are many duplicate objects, we can group these duplicate objects in powers of $2$. For example, $25$ objects can be grouped into groups of $1$, $2$, $4$, $8$, $10$. 730 731 This runs in $O(ndlogk)$ where $d$ is the number of digits (6 in this case) 732 733 ### Hard Version 734 735 In the hard version, we are not able to search all $n$ possibilities for the last number $x$ as there are many queries. 736 737 Using the 0-1 knapsack with duplicates, we have computed the dp table for the first $k-1$ numbers. The rest is incorporating the last number into the dp table. We can do this by considering each digit separately. Then, we can update the dp table by considering all possible transitions for all digits from $0$ to $9$. 738 739 **Code (easy version)** 740 741 ``` 742 #include <bits/stdc++.h> 743 using namespace std; 744 745 static long long inf = (1LL << 58LL); 746 static long long F[6]; 747 static long long ten[6] = {1, 10, 100, 1000, 10000, 100000}; 748 static long long dp[1000005]; 749 int N, K; 750 751 int main(){ 752 cin >> K; 753 for(int i = 0;i <= 5;i++) cin >> F[i]; 754 755 int Q; cin >> Q; 756 assert(Q == 1); 757 758 int N; cin >> N; 759 760 ///0-1 knapsack with duplicate elements 761 fill(dp,dp+N+1,-inf); dp[0] = 0; 762 for(int d = 0;d <= 5;d++){ 763 long long left = 3 * (K - 1); 764 long long group = 1; 765 766 ///grouping 3*(K-1) elements into groups of powers of 2 767 while(left > 0){ 768 group = min(group, left); 769 770 long long value = group * F[d]; 771 long long weight = group * ten[d] * 3; 772 for(int i = N;i >= weight;i--) dp[i] = max(dp[i], dp[i-weight] + value); ///knapsack DP 773 774 left -= group; 775 group *= 2; 776 } 777 } 778 779 long long ans = 0; 780 for(int X = 0;X <= N;X++){ 781 ///calculating the fortune of X 782 long long fortune = 0; 783 int x = X; 784 for(int d = 0;d <= 5;d++){ 785 int rem = x % 10; 786 if(rem == 3 || rem == 6 || rem == 9) fortune += (rem / 3) * F[d]; 787 x /= 10; 788 } 789 790 ans = max(ans, fortune + dp[N-X]); 791 } 792 793 cout << ans; 794 } 795 ``` 796 797 **Code (hard version)** 798 799 ``` 800 #include <bits/stdc++.h> 801 using namespace std; 802 803 const long long inf = (1LL << 58LL); 804 long long F[6]; 805 long long fortune[10] = {0, 0, 0, 1, 0, 0, 2, 0, 0, 3}; 806 long long ten[6] = {1, 10, 100, 1000, 10000, 100000}; 807 long long dp[1000005]; 808 809 int main(){ 810 ios_base::sync_with_stdio(false); cin.tie(0); 811 int K; int N = 999999; 812 813 cin >> K; 814 for(int i = 0;i <= 5;i++) cin >> F[i]; 815 816 817 fill(dp,dp+N+1,-inf); dp[0] = 0; 818 for(int d = 0;d <= 5;d++){ 819 long long left = 3 * (K - 1); 820 long long group = 1; 821 822 ///grouping 3*(K-1) elements into groups of powers of 2 823 while(left > 0){ 824 group = min(group, left); 825 826 long long value = group * F[d]; 827 long long weight = group * ten[d] * 3; 828 for(int i = N;i >= weight;i--) dp[i] = max(dp[i], dp[i-weight] + value); ///knapsack DP 829 830 left -= group; 831 group *= 2; 832 } 833 } 834 835 for(int d = 0;d <= 5;d++){ 836 for(int i = N;i >= 0;i--){ 837 for(int b = 1;b <= 9;b++){ 838 int pre = i - ten[d] * b; 839 if(pre < 0) break; 840 dp[i] = max(dp[i], dp[pre] + fortune[b] * F[d]); 841 } 842 } 843 } 844 845 int Q; cin >> Q; 846 while(Q--){ 847 int n; cin >> n; 848 cout << dp[n] << "\n"; 849 } 850 } 851 ``` 852 853 ## [1428H - Rotary Laser Lock](/contest/1428/problem/H) 854 855 Setter: [bensonlzl](/profile/bensonlzl "Master bensonlzl") and [oolimry](/profile/oolimry "Master oolimry") 856 Prepared by: [bensonlzl](/profile/bensonlzl "Master bensonlzl") 857 858 **Hint 1** 859 860 Using only arc $0$, find at least $1$ position where arc $0$ exactly matches another arc. 861 862 **Hint 2** 863 864 Binary Search. 865 866 **Solution** 867 868 ### Algorithm Analysis 869 870 Flatten the circle such that it becomes $n$ rows of length $nm$ with vertical sections numbered from $0$ to $nm-1$ that loops on the end. We say that the position of an arc is $x$ if the left endpoint of the arc is at section $x$. Indices are taken modulo $nm$ at all times. Moving arcs right is equivalent to rotating them clockwise, and moving arcs left is equivalent to rotating them counter-clockwise. 871 872 Notice that if we shift arc 0 right and the display increases, then the leftmost section of arc 0 had no other arcs in the same section. Thus, if we shift arc 0 right again and the display does not increase, we are certain that there was another arc at that position, so we shift arc 0 left. We now enter the **detection stage** to find any arc that coincides with arc 0 (of which there exists at least 1) at this position. Let's note down this positions as $x$. 873 874 Let $S$ be the set of arcs that we do not know the positions of yet (this set initially contains all arcs from 1 to $N-1$) and $T$ and $F$ be an empty sets. $T$ will be the set of all candidate arcs (those that **may** coincide here) and $F$ will contain all arcs that we have shifted leftwards. Take all elements in $S$ and put them in $T$, and pick half of the elements in $S$ and add them to the set $F$. We now shift all elements in $F$ left. 875 876 We move arc 0 left to check if any arc is at position $x-1$. 877 878 If there is, then we know that an arc that initially coincided at $x$ lies in $F$. In this case, we set $T$ to $T \cap F$ (elements of $T$ that are in $F$), pick half of the elements in $T$ to move right and remove those from $F$. 879 880 If no arc is at position $x-1$, then the arc we are looking for lies in $T \ \backslash \ F$ (elements in $T$ that are not in $F$). We set $T$ to be $T \ \backslash \ F$ and pick half of $T$ to move left and add those to $F$. We then shift arc 0 right and recurse. 881 882 When we have narrowed $T$ to exactly 1 arc, we know where exactly that arc is now. We shift that arc left such that its right endpoint is at $x-2$ so that it does not cover position $x-1$, which we may still need for future tests. Now we remove the arc found from $S$ and leave the **detection stage** and continue searching for the other arcs. 883 884 Once we have found all $n-1$ other arcs, we find the relative position to arc 0 and print them as the final output. 885 886 ### Query Analysis 887 888 Whenever we shift arc 0 right and are not in the **detection stage**, we use 1 shift. This occurs at most $2nm-m$ times because it takes up to $nm-m$ shifts right to find the first position where arc 0 coincides, and another $nm$ to traverse the entire circle again to find all of the arcs. 889 890 Whenever we enter the **detection stage**, we find one arc and use $2$ shifts initially when we move arc 0 right then left, yielding a total of $2n-2$ such shifts. Each binary search requires $2 \log |T|$ shifts of arc 0 (left and right), so across the $n-1$ **detection stages** this is at most $2n\log n$ when summed across all stages. 891 892 The way we perform the binary search is quite important here. Performing it in a naive manner (e.g. shifting half left, test and shifting them back) can use up to $n^2$ queries. 893 894 Instead, we set the number of elements that move in / out of $F$ at each iteration of the binary search to be the smaller half. This way we can guarantee that the number of shifts done by the candidate arcs is at most the total number of candidate arcs in the first place. This becomes $\frac{n(n-1)}{2}$ since we start with $n-1$ candidate arcs and reduce that number by 1 after each **detection stage**. 895 896 When we shift each of the arcs left by $m$ or $m+1$ (depending on whether they were in $F$ when we narrowed it down to 1 arc), we use at most $(n-1)(m+1) = nm+n-m-1$ shifts. 897 898 Thus in total, we use at most $2nm-m+2n-2+2n\log n + \frac{n(n-1)}{2} + nm+n-m-1$ shifts. For $n=100,m=20$, this is less than $13000$, which is much lower than the query limit of $15000$. 899 900 ### Other Comments 901 902 The limit was set higher than the provable bound to allow for other possible solutions. At least $1$ tester found a different solution that used around $13500$ queries. 903 904 Some other optimizations that empirically improve the number of queries: 905 906 * Instead of using arc $0$ as the detector, we can randomly pick one of the $n$ arcs as the detector arcs. 907 * At the very beginning, we perform some constant number of random shifts of the arcs (e.g. $300$ to $400$ random shifts). This helps to break up long groups of arcs that overlap, which speeds up the initial $nm$ search. 908 909 The official solution, augmented with these optimizations uses well below $11500$ queries and is very consistent for non-handcrafted test cases. 910 911 **Code** 912 913 ``` 914 #include <bits/stdc++.h> 915 916 using namespace std; 917 918 int queryRotation(int r, int d){ // Auxiliary function to print query and receive answer 919 int res; 920 cout << "? " << r << ' ' << d << endl << flush; // Print query 921 cout.flush(); 922 cin >> res; // Get response 923 if (res == -1) exit(1); // Error occured, exit immediately 924 else return res; // Return result 925 } 926 927 int main(){ 928 ios_base::sync_with_stdio(false); 929 cin.tie(0); 930 931 int N, M; // Number of rings and number of sections per ring 932 int totalPositions; // totalPositions = N*M 933 int newNum; 934 int currentNum; // track the current number on the display (responses from interactor) 935 int state = 0; // 0 means searching for rings, 1 means finding the ring at this position 936 int relpos[105] = {}; // Array to store the final relative positions 937 938 cin >> N >> M; 939 totalPositions = N*M; 940 941 // While this statement doesn't do anything, 942 // it serves as a reminder that we are taking 943 // the initial starting position of ring 0 944 // to be position 0 945 relpos[0] = 0; 946 947 currentNum = queryRotation(0,1); 948 relpos[0] = (relpos[0] + 1) % totalPositions; 949 950 951 // Now we prepare the set of unknown rings S 952 vector<int> S; 953 for (int i = 1; i < N; ++i){ 954 S.push_back(i); 955 } 956 957 // We now perform a preliminary rotation of ring 0 around until 958 // we are certain that ring 0 coincides with another ring 959 // at its leftmost point and the section to its left is empty 960 961 // This occurs when the difference changes from increasing when 962 // ring 0 moves right to non-increasing when ring 0 963 // moves right 964 int hasIncreased = 0; 965 while (1){ 966 // Rotate once, get the new number 967 newNum = queryRotation(0,1); 968 relpos[0] = (relpos[0] + 1) % totalPositions; 969 // Check if the number has increased 970 if (newNum > currentNum){ 971 hasIncreased = 1; 972 currentNum = newNum; 973 } 974 else{ // Otherwise the number hasn't increased 975 currentNum = newNum; 976 // Check if we have increased before 977 if (hasIncreased){ 978 979 // If we have, it means that our previous position 980 // coincided with the left endpoint of another arc 981 // Time to begin the detection stage 982 state = 1; 983 currentNum = queryRotation(0,-1); 984 relpos[0] = (relpos[0] - 1 + totalPositions) % totalPositions; 985 break; 986 } 987 } 988 989 } 990 991 while (!S.empty()){ // While we haven't found all of the rings yet 992 if (state == 1){ // If we are searching for an arc here 993 int curArc = 0; // to store the new arc 994 995 vector<int> T = S; // set of candiate arcs 996 vector<int> F; // set of arcs that have been moved left 997 998 for (int i = 0; i < T.size()/2; ++i){ // take the smaller half 999 F.push_back(T[i]); 1000 currentNum = queryRotation(T[i],-1); 1001 } 1002 1003 while (T.size() > 1){ // while the number of candidate arcs is > 1, we binary search on the remaining arcs 1004 int newNum = queryRotation(0,-1); 1005 relpos[0] = (relpos[0] - 1 + totalPositions) % totalPositions; 1006 if (newNum >= currentNum){ // the arc that we are looking for lies in F 1007 1008 // Set T to F 1009 T.clear(); 1010 for (auto it : F){ 1011 T.push_back(it); 1012 } 1013 1014 // Half the size of F by moving the smaller half to the right 1015 int sz = F.size()/2; 1016 for (int i = 0; i < sz; ++i){ 1017 int revRing = F.back(); 1018 currentNum = queryRotation(revRing,1); 1019 F.pop_back(); 1020 } 1021 1022 } 1023 else{ // the arc we are looking for does not lie in F 1024 vector<int> temp; 1025 for (auto it1 : T){ 1026 int check = 0; 1027 for (auto it2 : F){ 1028 if (it1 == it2) check = 1; 1029 } 1030 if (!check) temp.push_back(it1); 1031 } 1032 T = temp; 1033 F.clear(); 1034 for (int i = 0; i < T.size()/2; ++i){ // take the smaller half once again 1035 currentNum = queryRotation(T[i],-1); 1036 F.push_back(T[i]); 1037 } 1038 } 1039 currentNum = queryRotation(0,1); // bring arc 0 back 1040 relpos[0] = (relpos[0] + 1) % totalPositions; 1041 } 1042 1043 curArc = T[0]; // we have found the arc 1044 1045 1046 // we want this arc to be M+1 sections away from the current position 1047 // of arc 0 so that it does not interfere with later searches 1048 1049 if (!F.empty()){ // the arc we found still lies in F 1050 for (int i = 0; i < M; ++i){ // move the arc back by M sections 1051 currentNum = queryRotation(curArc,-1); 1052 } 1053 relpos[curArc] = relpos[0] - M - 1; 1054 } 1055 else{ // the arc we found does not lie in F 1056 for (int i = 0; i <= M; ++i){ // move the arc back by M+1 sections 1057 currentNum = queryRotation(curArc,-1); 1058 } 1059 relpos[curArc] = relpos[0] - M - 1; 1060 } 1061 // We now remove curArc from S 1062 vector<int> temp; 1063 for (auto it : S){ 1064 if (it != curArc) temp.push_back(it); 1065 } 1066 S.clear(); 1067 for (auto it : temp) S.push_back(it); 1068 1069 1070 state = 0; 1071 currentNum = queryRotation(0,-1); 1072 relpos[0] = (relpos[0] - 1 + totalPositions) % totalPositions; 1073 hasIncreased = 0; 1074 } 1075 else{ // keep moving right 1076 1077 newNum = queryRotation(0,1); 1078 relpos[0] = (relpos[0] + 1) % totalPositions; 1079 if (newNum <= currentNum && hasIncreased == 1){ // start searching 1080 newNum = queryRotation(0,-1); 1081 relpos[0] = (relpos[0] - 1 + totalPositions) % totalPositions; 1082 state = 1; 1083 } 1084 else if (newNum > currentNum) hasIncreased = 1; 1085 currentNum = newNum; 1086 } 1087 1088 } 1089 cout << "! "; 1090 for (int i = 1; i < N; ++i){ 1091 cout << (((relpos[i] - relpos[0] + 5 * totalPositions)%totalPositions) + totalPositions) % totalPositions << ' '; 1092 } 1093 cout << endl << flush; 1094 1095 } 1096 ```