BrayanD's blog

By BrayanD, history, 3 years ago, In English

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

1630E - Expected Components

Author: BrayanD

Hint 2
Hint 3
Solution

1630F - Making It Bipartite

Author: BrayanD

Hint 1
Hint 2
Hint 3
Solution
  • Vote: I like it
  • +246
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Auto comment: topic has been updated by BrayanD (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it +46 Vote: I do not like it

Really appreciate writing an editorial with hints. Helps a lot!!

»
3 years ago, # |
Rev. 2   Vote: I like it +63 Vote: I do not like it

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)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +35 Vote: I do not like it

    Yes, there is a case that leads to $$$tot_{all} = 0$$$ (mod 998244353)

    30612 ones, 12124 twos, 2 threes

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Love this style of editorial! Thanks!!

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

In case someone is interested, I made video Solutions for A-D(div-2)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.net/contest/1631/submission/144258175

»
3 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it
  • 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 144255745

UPD: The same problem can be done using two pointers with better TC. Solution using two pointers 144364659

»
3 years ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

Problem D was really cool problem. I have solved it with segment tree. link

This contest was:- Operationoforces :)

»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

How to solve D1A/D2C without the k<=n-1 constraint ?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    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

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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).

Idea
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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$$$.

»
3 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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

»
3 years ago, # |
Rev. 3   Vote: I like it -8 Vote: I do not like it

..

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You misread the problem. You need to assign the value $$$a_{l+k+i}$$$ to $$$a_{l+i}$$$, not the other way around.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's wrong with: 144271690

Idea 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.

»
3 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

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 :)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    In problem D1E, we need $$$gcd(n,x)$$$ for all $$$x$$$ independently. So we need to call $$$n$$$ times the $$$gcd$$$ function

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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)?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          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

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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; } }
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              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 that

              for(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.

              • »
                »
                »
                »
                »
                »
                »
                »
                3 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

nice round

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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$$$.

Submission — https://codeforces.net/contest/1630/submission/144278138

»
3 years ago, # |
  Vote: I like it +104 Vote: I do not like it

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) code

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 implementation

You can read my full submission (including IO and templates) here: 144275521

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks!!! Feeling confused when trying to read the official editorial

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am confused about your Option 2: for first(i)<j<i, why can we always assume that the optimal coloring of j always includes coloring first(i)? Or why it won't be the optimal coloring for i if using a j whose optimal coloring don't include coloring first(i)?

»
3 years ago, # |
  Vote: I like it -6 Vote: I do not like it

This is the best editorial writtern in the history of codeforces , thanks a lot

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 )

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain me B , I couldnt get it

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Could anyone explain solution of Div1 C ?

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone hack my code for div1 problem C? I'm failed in test 3 but I don't know what's wrong.

#include <bits/stdc++.h>
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<<ans;
}

»
3 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    can you please explain intution behind this approach.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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 :)

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Div2 C, I got the first 2 cases, but the third case was tricky

»
3 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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 <bits/stdc++.h> 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<n;i++) define rl(i,m,n) for(int i=n;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<int,int> &a,const pair<int,int> &b){return (a.second < b.second);} bool sortd(const pair<int,int> &a,const pair<int,int> &b){return (a.second > b.second);} void printarr(ll arr[], ll n){fl(i,n) cout << arr[i] <<endl;} ll binaryToDecimal(string n){string num = n;ll dec_value = 0;int base = 1;int len = num.length();for(int i = len — 1; 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<ll,ll > m; vector<pair<ll,ll> > 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<<vec[i].ff<<" "<<vec[i].ss<<endl; // cout<<"xxx"<<endl;

vector<pair<ll,ll> > l; ll r=0; for(;r<le;r++) { if(vec[r].second!=0) { l.pb(vec[r]);r++;break;} }

// cout<<"r"<<r<<endl; ll j=0; for(ll i=r;i<le;i++) { if(vec[i].second!=0) { if(vec[i].first> 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<<l[i].ff<<" "<<l[i].ss<<endl;

ll count=0;

fl(i,len) { if(v[l[i].first-1]==v[l[i].second-1]) { count+=l[i].second-1-l[i].first; } else { count+=l[i].second-1-l[i].first-1; } } cout<<count;

}

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice editorial! Appreciate it!!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice editorial, If anyone wants video editorial for problem DIV 2D
Link

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

1630-D is really an impressive problem!!

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is a solution to D2C/D1A — AND Matching that works for arbitrary $$$k$$$ values in $$$O(n \cdot logn)$$$ without any casework or brute force.

It's easy to prove that we can reach the maximum possible $$$k$$$ value for $$$n$$$ by pairing $$$0$$$ with $$$1$$$, $$$2$$$ with $$$3$$$ and so on. After constructing this case, we can decrease the sum by $$$2^n$$$ (where $$$n \geq 1$$$) by swapping $$$x$$$ with $$$x ⨁ 2^n$$$. Of course, we have to take care not to swap pairs of elements that were already swapped before. If $$$k$$$ is odd, we can finally increase the sum by $$$1$$$ by swapping $$$0$$$ and $$$1$$$.

»
14 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I made a mistake, I'm sorry.