### BrayanD's blog

By BrayanD, history, 16 months ago, ### 1631A - Min Max Swap

Author: humbertoyusta

Hint 1
Hint 2
Solution

### 1631B - Fun with Even Subarrays

Author: humbertoyusta

Hint 1
Hint 2
Solution

### 1630A - And Matching

Author: humbertoyusta

Hint 1
Hint 2
Solution

### 1630B - Range and Partition

Author: humbertoyusta

Hint 1
Hint 2
Hint 3
Hint 4
Solution

### 1630C - Paint the Middle

Author: humbertoyusta

Hint 1
Hint 2
Hint 3
Solution

### 1630D - Flipping Range

Author: humbertoyusta

Hint 1
Hint 2
Hint 3
Solution

Author: BrayanD

Hint 2
Hint 3
Solution

### 1630F - Making It Bipartite

Author: BrayanD

Hint 1
Hint 2
Hint 3
Solution Tutorial of Codeforces Round 768 (Div. 1) Tutorial of Codeforces Round 768 (Div. 2) Comments (56)
| Write comment?
 » Auto comment: topic has been updated by BrayanD (previous revision, new revision, compare).
 » Really appreciate writing an editorial with hints. Helps a lot!!
 » 16 months ago, # | ← Rev. 2 →   Did you give the proof of cont cannot be $0$ in problem E? What if $\mathit{tot}_{\mathit{all}} \equiv 0 \pmod{998244353}$?Upd: Thank the authors for replying. It’s just a tiny flaw. I didn’t solve the problem is just because I’m away from training for too long...Looking forward to a specific case with $\mathit{tot}_{\mathit{all}} \equiv 0 \pmod{998244353}$, can someone construct such one?Advertisement: A live recording of me participating this contest (in Chinese, bilibili: BV1kq4y187B4)
•  » » The statement will be fixed, I added the restriction:It is guaranteed that the total number of different permutations of $a$ is not divisible by $M$Sorry for that mistake
•  » » 16 months ago, # ^ | ← Rev. 2 →   Yes, there is a case that leads to $tot_{all} = 0$ (mod 998244353)30612 ones, 12124 twos, 2 threes
 » Love this style of editorial! Thanks!!
 » In case someone is interested, I made video Solutions for A-D(div-2)
 » I think in 1630C problem it is also easy to calculate 1's, for reference we do everything same , but few ranges are joint , for e.g. (x1, y1) && (x2, y2) such that y1 > x2 and y2 > y1 than we can not paint both y1 and x2 but we can paint 1 of them including every other element in range x1, y2 here is implementation https://codeforces.com/contest/1631/submission/144258175
 » 16 months ago, # | ← Rev. 3 →   A simpler approach for Div1B/Div2D using binary search. It was mentioned ai<=n, so we can linearly iterate on x from min element to max element of the array. For every x we can find the first y using binary search that can produce atleast k subarrays. To check if we can create atleast k subarrays given a range [x, y], we count the number of elements inside and outside the range. For every subarray, we will need atleast one extra element inside the range than outside, so we can keep a sorted copy of the array, and using lower bound we can count number of elements inside and outside the range, and if we have atleast k extra elements lying inside, then [x, y] is a valid range. If we have more than K legal subarrays, we can merge some, because merging two legal subarrays will give us a legal subarray always. After we have found y, we can check for y-x, minimize and store them. After we have a desired [x, y] we can linearly traverse again and as soon as we have more elements inside the range [x, y] than outside the range, we can keep it as a subarray, like this we can get k-1 subarrays and for the last subarray, it can contain all the remaining elements. My solution for the same 144255745UPD: The same problem can be done using two pointers with better TC. Solution using two pointers 144364659
•  » » This is exactly what two pointers does in O(n) time :)
•  » » » Yeah got that idea later.
•  » » thanks I was getting confused with editorial
 » 16 months ago, # | ← Rev. 2 →   Problem D was really cool problem. I have solved it with segment tree. linkThis contest was:- Operationoforces :)
 » How to solve D1A/D2C without the k<=n-1 constraint ?
•  » » Notice that $a_i \oplus b_i = a_i + b_i - 2 \cdot (a_i \& b_i)$, where $\oplus$ denotes bitwise xor, which is much nicer for pair-wise budgeting than bitwise and. Thus, in any solution, $\sum_{i=1}^{n/2}{a_i \oplus b_i} = \binom{n}{2} - 2 \cdot k$. The bitwise xor of each pair is between $1$ and $n-1$, so we may reject if this sum is not between $n/2$ and $n/2 \times (n - 1)$. Otherwise, a solution always exists.You can construct one by starting from a pairing that matches every $x$ to $x \oplus C$ for some fixed $C$ and tweaking it at some small number of pairs, similar to what the main editorial does for $k < n - 1$. The simplest tweak is to mess with exactly two pairs. This can be done by, for example, pairing $(0,x)$ and $(C, x \oplus C)$, with a resulting total xor of $(n/2 - 2) \cdot C + 2 \cdot x$. It's easy enough to see that there always exists at least one working choice of $C$ and $x$, but an explicit formula seems a bit messy. My code just brute-forces all possible options: 144268260
 » I really liked the problem 1631C - And Matching, but I think the constructive solution shown in editorial is a bit overly complicated. My solution is similiar, but I don't really need to handle that many cases (it's only necessary to check if a number hasn't been already used). IdeaLet's look at the binary representation of $k$ (as an example, let's say that $k = 1001101$). Let's look at the set of set bits ("set of set bits" sounds funny, doesn't it?) $\lbrace b_1, b_2, b_3, \cdots, b_x \rbrace$, for our example it's $\lbrace 0, 2, 3, 6 \rbrace$ (0-indexed and counting from right). Now we will iterate through this set: we are at index $i$ which corresponds to $b_{i}$-th bit set. We will match ($2^{b_{i}}$, $(n-1)\oplus{2^{b_{i-1}}}$) (for $i=0$ we will simply match with $n-1$). After the last iteration we have to match ($(n-1)\oplus{2^{b_x}}$, $0$), Each time we do that we have to check if none of the numbers were used before. Up to this point, all the pairs we have made sum to $k$ so we need to make sure all other pairs we need to make are zero. We can iterate $i=1 \cdots n-1$ and check if the $i$ we are currently at hasn't been already paired before, if not let's pair it with $(n-1)\oplus{i}$. It's easy to show that pairs formed this way will all sum have their bitwise AND equal to $0$.The question is, why does this work? Well, we can easily see that if $n$ is a power of $2$ then each number from $0, 1, 2, \cdots, n-1$ will have unique XOR with $n-1$ (if there are 2 different numbers $x, y$ then there is atleast 1 bit where they differ, which shows that $x\oplus{(n-1)} \neq y\oplus{(n-1)}$. The problem might come with numbers with their representation like $111011$ becuase in order to $0$ the pair, we need to use some power of $2$ which could have already been used. This is easily solved by pairing ($2^{b_i}$, $(n-1)\oplus{2^{b_{i-1}}}$), because the number is already paired and the bitwise AND is still equal to $2^{b_i}$.Note: If in the first process any number repeats and we need to use it more than once, the answer is $-1$. Code144240803
•  » » I solved it the same way. In simpler terms: match $i$ with $n-1-i$, and then 'shift' the positions of $0, b_1, b_2, ... b_x$. This will make the sum $k$, except when two of them are already matched with each other. It can be proven that this only happens when $n=4$ and $k=3$.
 » 16 months ago, # | ← Rev. 2 →   In the solution of 2D/1B: $[x\le a_i\le y]$What is the name of this square bracket expression? It seems to me that $[\text{true}] = 1$ and $[\text{false}] = 0$.Edit: Iverson bracket
 » 16 months ago, # | ← Rev. 3 →   ..
•  » » You misread the problem. You need to assign the value $a_{l+k+i}$ to $a_{l+i}$, not the other way around.
 » What's wrong with: 144271690Idea 1: If we have two intervals, one of which contains the other, then remove the smaller interval.Idea 2: If we have three intervals which mutally intersect, then remove the middle one.
•  » »
•  » » » Thanks for the help. I've updated the submission now: 144343029, and the stress tester can no longer find a counterexample, unfortunately.
 » 16 months ago, # | ← Rev. 2 →   Reminder that multiple (N) gcd calls over the same variable works in O(log(A) + N) where A is the first number greater than 0 set to it.So div1E's complexity is wrong. Edit: not wrong but there's a lower bound :)
•  » » In problem D1E, we need $gcd(n,x)$ for all $x$ independently. So we need to call $n$ times the $gcd$ function
•  » » » True, let's fix that: let's say x = p * y for some prime p that divides x. gcd(x, n) is gcd(y * p, n) which is either gcd(y, n) or gcd(y, n) * p. Do dp[x] = gcd(x, n), check those 2 cases separately and preprocess some prime for every number. Is there any other part higher than O(N)?
•  » » » » Well, that's interesting. In fact, I had a O(N) solution using euler phi function, but O(N*log) solution was easier to explain. Anyways, your idea is good, and yes, it is O(N) in total.
•  » » » » » 16 months ago, # ^ | ← Rev. 2 →   In fact, just the editorial is O(N), I just was too sleepy to realize:sum log(a[i]) <= sum a[i] == N so sum log(a[i]) is O(N) where a[i] is the frequency of i
•  » » » » » » This is the part of more complexity, are you sure that it is O(N)?  long long res = 0; long long cont = 0; for(int i = 1 ; i <= N ; i++) { long long ggg = N/__gcd(N,i); if(G%ggg == 0) { res = (res + arr[ggg])%MOD; cont = (cont + arr2[ggg])%MOD; } } 
•  » » » » » » » 16 months ago, # ^ | ← Rev. 2 →   No, that's O(NlogN). I guess I went by too quickly through that part of the editorial (because I didn't want to completely spoil the idea).With that code it's clear thatfor(d divisor of N) if(G % (N / d) == 0 or something like this) res += arr[d] * phi(d), cont += arr2[d] * phi(d)is equivalent and another way to optimize the complexity.
•  » » » » » » » » Yes, that was my idea with euler phi function. You can precalculate all phi numbers until N in complexity O(N), or maybe factorize N and do something
 » nice round
 » For Div.2 Problem D, my first intuition is to enumerate x, and for each x use binary search to find the best y. for x in [min, max]: l, r = x, max while l < r: y = (l + r) / 2 if ok(x, y): r = y else: l = y + 1 if ok(x, l): update_answer() The problem is that if we naively implement the predicate ok by traversing the given array, it will be of O(n) time and the overall time will be O(n^2 log(n)), which is hopeless.One important intuition to optimize it is to sort the given array and implement an ok in O(log(n)) time (in other words, for determining the feasibility of a range [x, y], the order of the given array doesn't matter). Then the overall time becomes O(n (log(n))^2), which is good.
•  » » During the contest I only came up with the O(n) implementation of the predicate ok, and I was even thinking about whether there are some kinds of "2D binary search" to eliminate the outmost enumeration of x, but I didn't succeed in that direction.
 » Div1 B can be solved using two pointers on $x$ and $y$ with a fenwick tree. Replacing all elements in the range $[x,y]$ with $1$ and those not in the range with $-1$, the partition can be made if the sum of all elements is at least $k$.
•  » » Even a fenwick ree is not needed since only the sum of all elements is needed
 » I had a different solution to 1630C - Paint the Middle, which I think was very simple and clean (I wrote 5-10 lines of code without any complex expressions, branching, or sorting events/intervals).The idea is to define a DP array $f(i)$ = maximum answer for the subarray $[0, i]$, assuming $0$-indexing. Therefore, $f(0) = 0$ and $f(n-1) = \textit{ans}$. Note that $f(i)$ never involves coloring $a_i$, because it's impossible to color either endpoint of your array.Let's consider our choices for different ways to get candidate values of $f(i)$, assuming we know the previous values of $f$.Option 1: $a_i$ has a previous occurrence at index $j < i$. We can perform the optimal solution for $[0, j]$, then color the $(i-j-1)$ elements strictly between $a_j$ and $a_i$, giving us a score of $f(j) + (i-j-1)$.Option 2: If there is an instance of $a_i$ at some index $k$ such that $k < j < i$, so we can perform the optimal solution for $[0, j]$ except for leaving $a_k$ untouched, then color the remaining elements between $a_j$ (inclusive) and $a_i$ (exclusive), using the fact that $a_k = a_i$. This gives us a score of $(f(j)-1) + (i-j)$, which is the same expression as in the previous paragraph.Option 3: We can always ignore the last element, giving us a score of $f(i-1)$. This can be creatively re-written as the same expression as before: $f(i-1) + (i - (i-1) - 1)$.Therefore, we have the following simple quadratic DP: $f(i) = \max_j \left[f(j) + (i - j - 1)\right]$, for $j$ such that either $\text{first}(a_i) \le j < i$ or $j = i-1$. Equivalently, $\min(\text{first}(a_i), i-1) \le j < i$. quadratic (TLE) codevector first(n + 1, INF); for (int i = n - 1; i >= 0; i--) first[a[i]] = i; vector dp(n, -INF); dp = 0; for (int i = 1; i < n; i++) { int score = -INF; for (int j = 0; j < i; j++) { if (j >= first[a[i]]) score = max(score, dp[j] + (i - j - 1)); } score = max(score, dp[i - 1]); dp[i] = score; } cout << dp[n - 1] << '\n'; In order to optimize this, we make the following rearrangement: $f(i) - i = -1 + \max_j \left[f(j) - j\right]$.Setting $g(i) = f(i) - i$ gives us $g(i) = -1 + \max_j [ g(j) ]$. This can be very easily implemented using a segment tree to compute $\max_j [g(j)]$, and our answer is $f(n-1) = g(n-1) + (n-1)$. Final implementationvector first(n + 1, INF); for (int i = n - 1; i >= 0; i--) first[a[i]] = i; segment_tree st(n, -INF, [](int u, int v) { return max(u, v); }); st.assign(0, 0); for (int i = 1; i < n; i++) { int l = min(first[a[i]], i - 1); st.assign(i, -1 + st.accumulate(l, i)); } cout << st[n - 1] + (n - 1) << '\n'; You can read my full submission (including IO and templates) here: 144275521
•  » » Thanks!!! Feeling confused when trying to read the official editorial
•  » » I am confused about your Option 2: for first(i)
 » This is the best editorial writtern in the history of codeforces , thanks a lot
 » 16 months ago, # | ← Rev. 2 →   hello BrayanD in problem And Matching Constructive approach (easier) The code of this approach in Case 2 : ( k > 0 && k < n — 1 ) if condition ( i != 0 || i != small_k ) should be ( i != 0 && i != small_k )
•  » » In fact, I think that the condition is not important. It can be removed. Anyways, I fixed the solution code. Thanks for noticing it and telling me.
 » Can someone explain me B , I couldnt get it
 » Could anyone explain solution of Div1 C ?
 » 16 months ago, # | ← Rev. 2 →   Can anyone hack my code for div1 problem C? I'm failed in test 3 but I don't know what's wrong. #include using namespace std; const int maxn = 2e5+7; int t,k,m,n; int a[maxn]; int r[maxn]; signed main() { cin>>n; for (int i=1;i<=n;i++) { cin>>a[i]; r[a[i]] = i; } int ans = 0; int r1,r2=0; for (int i=1;i<=n;i++) { r2 = 0; r1 = r[a[i]]; if (r1==i) continue; for (int j=i+1;j<=r1;j++) { r2 = max(r2,r[a[j]]); } if (r2==r1) { ans += r2-i-1; i = r1; } else { ans += r2-i-2; i = r2; } } cout<
•  » » Ah..I see what's wrong with me
 » 16 months ago, # | ← Rev. 2 →   There is another easier (as I consider) solution for Div1 D.Let's look throw elements with position $x \pmod g$. If there are even number of elements $a_i < 0$ — we can make all elements $\geqslant 0$. And if there are odd number — we can make all elements $\geqslant 0$ except 1, any of them.Ok, let's the first set will be remainders $\pmod g$ with even number of negative elements and the second set — remainders with odd number of them.And it turns out, that the optimal set of negative elements in the final answer — the 1 element with minimum module from every remainders of the first set or from every remainders of the second set.The solution with very simple code. 144363709
•  » » can you please explain intution behind this approach.
•  » » » Ok, when we invert the segment — we change (parity of negative elements) of each remainder. (If some of these elements are $0$, let's imagine, that they will be $-0$ now: it doesn't really matter).And the second thought — we can invert any two elements at a distance $g$. Because we can invert $[x, x+g-1]$ and $[x+1, x+g]$. And, of course, we can start to repeat it: $(x, x+g)$ and $(x+g, x+2g)$ will turn into $(x, x+2g)$ and so on.Finally, we can invert any of pair elements with the same remainder $\pmod g$. And from here my solution quickly follows :)
•  » » » Div. 1 D is a harder version of https://atcoder.jp/contests/abc125/tasks/abc125_d. I started with the idea in the first official solution for that problem and ended up with exactly the same solution presented here.
 » For Div2 C, I got the first 2 cases, but the third case was tricky
 » 16 months ago, # | ← Rev. 4 →   Can someone help me with my code div2 problem E . I'm stuck at test case 3 (wrong answer). Although I think my algorithm is correct.include using namespace std; define ll long long define lld long double define ff first define ss second define pb push_back define mp make_pair define fl(i,n) for(int i=0;i=m;i--) define pi 3.141592653589793238 define vr(v) v.begin(),v.end() define rv(v) v.end(),v.begin() define Code ios_base::sync_with_stdio(false); define By cin.tie(NULL); define Asquare cout.tie(NULL);ll gcd(ll a, ll b){if (b == 0)return a;return gcd(b, a % b);} ll lcm(ll a, ll b){return (a/gcd(a,b)*b);} bool sorta(const pair &a,const pair &b){return (a.second < b.second);} bool sortd(const pair &a,const pair &b){return (a.second > b.second);} void printarr(ll arr[], ll n){fl(i,n) cout << arr[i] <= 0; i--){if (num[i] == '1')dec_value += base;base = base * 2;}return dec_value;} bool isPrime(ll n){if(n<=1)return false;if(n<=3)return true;if(n%2==0||n%3==0)return false;for(int i=5;i*i<=n;i=i+6)if(n%i==0||n%(i+2)==0)return false;return true;} bool isPowerOfTwo(int n){if(n==0)return false;return (ceil(log2(n)) == floor(log2(n)));} bool isPerfectSquare(ll x){if (x >= 0) {ll sr = sqrt(x);return (sr * sr == x);}return false;} ll moduloMultiplication(ll a,ll b,ll mod){ll res = 0;a %= mod;while (b){if (b & 1)res = (res + a) % mod;b >>= 1;}return res;} ll powermod(ll x, ll y, ll p){ll res = 1;x = x % p;if (x == 0) return 0;while (y > 0){if (y & 1)res = (res*x) % p;y = y>>1;x = (x*x) % p;}return res;}int main() { ll n; cin>>n; vector v; ll x;fl(i,n) { cin>>x; v.pb(x); }unordered_map m; vector > vec;ll u=1;fl(i,n) { if(m[v[i]]==0) { m[v[i]]=u; vec.pb(mp(i+1,0)); u++; } else { vec[m[v[i]]-1]=mp(vec[m[v[i]]-1].first,i+1); } }ll le=vec.size();// fl(i,le) // cout< > l; ll r=0; for(;r l[j].second) { l.pb(vec[i]); j++; } else if(vec[i].second>l[j].second) { l[j]=mp(l[j].first,vec[i].ss); } } }ll len=l.size();// fl(i,len) // cout<
 » Nice editorial! Appreciate it!!
 » 1630-D is really an impressive problem!!
 » can anyone tell what is wrong in my code 1631B - Fun with Even Subarrays
 » For 1630A， if k>n-1 what should we do?