codeforces-scrape

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

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 ![ ](/predownloaded/55/cc/55ccd0ef5b474ae90e244683a22752ad42ad3655.png)
    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 ![ ](/predownloaded/85/90/8590c89b6d2543ee243771e72e27a70e8d682c77.png)
    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 ![ ](/predownloaded/21/15/21155f018ee7437556ac80bac96ce4bf63baca01.png)
    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 ![ ](/predownloaded/90/1f/901f0a95c632f057567707548dfba58df6cd759e.png)
    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 ![ ](/predownloaded/66/a2/66a2b7e033a609715e3efd3eb4a684ec1839832d.png)
    608 
    609 Above is the histogram for $11101011$ when $r=7$.
    610 
    611 ![ ](/predownloaded/5e/61/5e61635831e88b6209ccbbaf488e7da1f3593d85.png)
    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 ```