### BrayanD's blog

By BrayanD, history, 4 months ago, ### 1631A - Мин-макс замены

Author: humbertoyusta

Hint 1
Hint 2
Solution

### 1631B - Веселье с четными подмассивами

Author: humbertoyusta

Hint 1
Hint 2
Solution

### 1630A - И-сопоставление

Author: humbertoyusta

Hint 1
Hint 2
Solution

### 1630B - Отрезок и разбиение

Author: humbertoyusta

Hint 1
Hint 2
Hint 3
Hint 4
Solution

### 1630C - Раскрась середину

Author: humbertoyusta

Hint 1
Hint 2
Hint 3
Solution

### 1630D - Переверни отрезки

Author: humbertoyusta

Hint 1
Hint 2
Hint 3
Solution

Author: BrayanD

Hint 2
Hint 3
Solution

### 1630F - Сделай его двудольным!

Author: BrayanD

Hint 1
Hint 2
Hint 3
Solution Tutorial of Codeforces Round #768 (Div. 1) Tutorial of Codeforces Round #768 (Div. 2) Comments (85)
 » Auto comment: topic has been updated by BrayanD (previous revision, new revision, compare).
 » Really appreciate writing an editorial with hints. Helps a lot!!
 » 4 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
•  » » 4 months ago, # ^ | ← Rev. 2 →   Yes, there is a case that leads to $tot_{all} = 0$ (mod 998244353)30612 ones, 12124 twos, 2 threes
•  » » » Can you put the Easiest Solution for Problem E in Editorial?LinkI don't know How I missed this intution!!"All I know is, I know nothing But how Do I know?"
 » Love this style of editorial! Thanks!!
 » In case someone is interested, I made video Solutions for A-D(div-2)
•  » » Thanks!
•  » » <3
 » nice edi
 » 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
 » 4 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
 » 4 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 - И-сопоставление, 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$.
 » 4 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
 » 4 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.
•  » » » Thank You sir
 » 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.
•  » » » »
 » 4 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.
•  » » » » » 4 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; } } 
•  » » » » » » » 4 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 - Раскрась середину, 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
 » 4 months ago, # | ← Rev. 2 →   Check out my solution for 1631B. I think it's a good bit simpler than the one in the tutorial. Same core logic I think, though.144280684
 » Div 2 B : Fun with Even subarrays video Editorial LINK
 » This has been the most organized editorial that I have seen so far with solutions of different complexities and hints, Great work
 » Thanks everyone, for this fun and amazing contest.
 » 4 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.
 » nice solutions !!! thank u!
 » https://codeforces.com/contest/1631/problem/C Can anyone help me in understanding why I am getting the wrong answer, If I directly output the answer instead of storing all the results for a particular test case in a vector and then print the answer. https://codeforces.com/contest/1631/submission/144287685 (solution with using the vector [Accepted]) https://codeforces.com/contest/1631/submission/144285733 (solution without using the vector[Wrong Answer])
 » Nice editorial
 » For 1631B — Fun with Even Subarrays, I implemented something similar to O(n) solution described, but instead of reversing the array. I traversed backwards, while jumping the maximum span possible at each iteration. Can you suggest some testcases for which it fails? https://codeforces.com/contest/1631/submission/144231299wrong answer 19821st numbers differ - expected: '3', found: '0'
•  » » Submission I used same approach it passed. Your solution might be failing at some edge case.
•  » »
•  » » » Thank you stranger! This tool is helpful. But there's a very weird problem I fail to decode. Locally, I run the failing test case with 10 cases (t=10) and I get a value of 2 for the last testcase. But If I run the last test case only by passing (t=1) I get a value of 3 which is correct. I'm not able to understand this behaviour.https://ibb.co/w6nB8B6 (img link)
•  » » » » That's a pretty common mistake. Whenever your code passes single testcase inputs, but fails on multi test case inputs, there are only 2 possible reasons. Incorrect initialization of global variables. Early termination Since you aren't using any global variable, it leaves us with Early Termination, and in your submission, you can see that when $n == 1$, you print the answer as zero and move to the next iteration using continue, but you don't really take the full input for that test case. This messes up the future testcases.Don't mix cin/cout with continue/break (or be attentive when you do that).
 » Can anyone explain me what does this statement mean "Select some subarray from a of even size 2k that begins at position l (1≤l≤l+2⋅k−1≤n, k≥1) and for each i between 0 and k−1 (inclusive), assign the value al+k+i to al+i."
•  » » 4 months ago, # ^ | ← Rev. 2 →   It means you can choose a subarray of even size and make any element in first half equal to the corresponding element in second half. Eg array a->[1,2,5,4,7,8,9,0] Here, you can choose the subarray starting at index 3(1-based) array b-> [5,4,7,8,9,0] and make b = b, b = b, b = b
•  » » » Bro can you explain this "al+k+i to al+i"? with values of l,k and i
•  » » » » In above subarray b is of length 6. Therefore 2k = 6 => k = 3.The subarray starts at index 3 (in the original array a),So l = 3 (starting point of first half) and l+k i.e., index 6 is starting point for second half. Now i goes from 0 to k-1, and we make a[l+i] = a[l+k+i]
•  » » » » » Got it bro thanks!
 » Can someone explain me B , I couldnt get it
 » Could anyone explain solution of Div1 C ?
 » 4 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
 » Is the complexity not NlogN*longN for Question D
 » Thanks buddy!!, i apriciate your initiative, it is very much helpfull!!
 » 4 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 :)
•  » » » » Thanks a lot.
•  » » » 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.
•  » » » » Thanks a lot
 » For Div2 C, I got the first 2 cases, but the third case was tricky
 » 4 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!!
 » Nice editorial, If anyone wants video editorial for problem DIV 2D Link
 » What is the expected rating of problem C?
 » 1630-D is really an impressive problem!!
 » if i have the edges that are making my graph non-bipartite ,how can i see which is the minimum number of vertexes to erase ,so it becomes bipartite?