awoo's blog

Educational Codeforces Round 176 Editorial
By awoo, history, 5 hours ago, translation, In English

2075A - To Zero

Idea: BledDest

Tutorial
Solution (BledDest)

2075B - Array Recoloring

Idea: BledDest

Tutorial
Solution (Neon)

2075C - Two Colors

Idea: fcspartakm

Tutorial
Solution (awoo)

2075D - Equalization

Idea: BledDest

Tutorial
Solution (Neon)

2075E - XOR Matrix

Idea: BledDest

Tutorial
Solution (BledDest)

2075F - Beautiful Sequence Returns

Idea: adedalic

Tutorial
Solution (adedalic)
  • Vote: I like it
  • +14
  • Vote: I do not like it

»
5 hours ago, # |
  Vote: I like it -13 Vote: I do not like it

It's a good thing that you remember to share the Editorial!

→ Reply
»
5 hours ago, # |
  Vote: I like it -7 Vote: I do not like it

Thanks! The tasks were really interesting!

→ Reply
»
5 hours ago, # |
  Vote: I like it -7 Vote: I do not like it

Nice~~~

→ Reply
»
5 hours ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Can anyone share the approach to problem C's solution using suffix array? Btw, thanks for the editorial, really helpful!

→ Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    #include <bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo(i, n) for (i = 0; i < n; i++)
#define Fo(i, k, n) for (i = k; k < n ? i < n : i > n; k < n ? i += 1 : i -= 1)
#define ll long long
#define deb(x) cout << #x << "=" << x << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, false, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for (auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
#define mod 1000000007
typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        ll n, m;
        cin>>n>>m;

        vector<ll> color(m);
        for(int i = 0; i < m ;i ++) {
            cin>>color[i];
        }

        sort(color.begin(), color.end());


        ll ans = 0;
        for(int i = 1; i <= n/2; i++) {

            ll lowerColor = lower_bound(color.begin(), color.end(), i) - color.begin();
            lowerColor = m - lowerColor;
            ll upperColor = lower_bound(color.begin(), color.end(), n - i) - color.begin();
            upperColor = m - upperColor;

            ll tempAns = ((lowerColor * upperColor) - upperColor);
            if(n % 2 != 0 || i != n /2) {
                tempAns *= 2;
            }
        
            ans += max(0LL, tempAns);
        }

        cout<<ans<<endl;
    }
    return 0;
}
    → Reply
  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    #include <iostream>
#include <bits/stdc++.h>

using namespace std;


#define ar array
#define ll long long
#define ld long double
#define sza(x) ((int)x.size())
#define all(a) (a).begin(), (a).end()

const int MAX_N = 1e5 + 5;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;



void solve() {
    ll n,m;
    cin>>n>>m;
    vector<ll> arr(m);
    for(int i = 0; i<m; i++){
        cin>>arr[i];
    }
    sort(arr.begin(),arr.end());
    ll ans = 0;
    vector<ll> rec(n+2);
    
    for(int i = 1; i<=n; i++){
        ll ext = lower_bound(arr.begin(),arr.end(),i) - arr.begin();
        ll freq = m-ext;
        rec[i+1]=freq;
        

    }
    for(int i = 1; i<=n+1; i++){
        rec[i] += rec[i-1];
    }
    
    for(int i = 0; i<m; i++){
        ll min_to_paint = 1;
        ll max_to_paint = min(arr[i],n);
        ll left_to_paint_min = n - max_to_paint;
        ll left_to_paint_max = n - 1;
        ans += rec[left_to_paint_max+1]-rec[left_to_paint_min];
        if(left_to_paint_min <= arr[i]){
                        ans -= min(left_to_paint_max,arr[i])-left_to_paint_min+1;
        }
        if(arr[i] >= n){
            ans++;
        }
    }

    cout<<ans<<endl;
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t=1;
    cin >> t;

    while(t--){
        solve();
    }

    return 0;
}

    f

    → Reply
»
4 hours ago, # |
  Vote: I like it +6 Vote: I do not like it

No rating rollback? There are clear cheaters in top 100

→ Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    give them some time eventually they are skipped (at least most of them)

    → Reply
»
2 hours ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Here is a clean implementation of task C, if anyone is interested in taking a look.

void solve() {
    ll n, m; cin >> n >> m;
    vector<ll> a(m);

    for(auto &x : a) cin >> x;

    sort(a.begin(), a.end());

    ll ans = 0;
    for(ll i = 1; i < n; i++) {
        ll val1 = m - (lower_bound(a.begin(), a.end(), i) - a.begin());
        ll val2 = m - (lower_bound(a.begin(), a.end(), n - i) - a.begin());
        ll val3 = m - (lower_bound(a.begin(), a.end(), max(i, n - i)) - a.begin());
        ans += (val1 * val2);
        ans -= val3;
    }

    cout << ans << "\n";
}
→ Reply
»
2 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

For problem C, there is also an $$$O(m \log m)$$$ solution (example: 311315934) which is what I did during the contest, arguably overengineering the solution.

The essential idea is that if you have two paints with indices $$$i$$$ and $$$j$$$, then you can use them to paint the fence only if $$$a_i + a_j ≥ n$$$, and if you clip the values of $$$a$$$ to $$$n - 1$$$ (because you can never paint more than $$$n - 1$$$ boards with a single color) then the number of ways to paint the fence with these two colors is $$$a_i + a_j - n + 1$$$.

That gives a trivial $$$O(m^2)$$$ solution where we consider all possible pairs of $$$i$$$ and $$$j$$$, but of course that is too slow. But we can improve this by first sorting the array $$$a$$$, then for each index $$$j$$$ you can calculate the first index $$$i < j$$$ such that $$$a_i + a_j ≥ n$$$, and the number of ways to paint the fence such that the right half is painted with index $$$j$$$ is $$$\sum_{k=i}^j a_k + a_j - n + 1$$$ (in my code, the result of this sum is stored in acc).

As $$$j$$$ increases, $$$i$$$ decreases. We can update the sum (acc) as we increment j and add new values of $$$i$$$ as they become available. Since in this we assume $$$k < j$$$ we are only counting half of the solutions, so we need to multiply the result by $$$2$$$ to obtain the final answer.

The main algorithm runs in $$$O(m)$$$ time, but since this requires sorting the array $$$a$$$ first, it's technically $$$O(m \log m)$$$.

→ Reply
»
114 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

D actually doesn't require DP, and can be solved if x,y are given as binary strings of length <= 2e5.

Say we have to remove last p bits of x and last q bits of y.

For now suppose p,q are atleast 3, let r be the smallest number such that r(r+1)/2 >= p+q.

I claim the optimal way to select the numbers for the operations are 1,....r and remove r(r+1)/2-(p+q) incase p+q != r(r+1)/2.

This is clearly the minimum as we'd like to minimize the maximum number we take which will be r, and further we'd like to remove the largest possible number, if we take all numbers from 1 to r.

I didn't explicitly prove we can split them to obtain (p,q) , but it can probably proved by induction, however it fails if min(p,q) is 1 or 2 so we have to add some extra checks when min(p,q) is 0,1 or 2.

You can refer to https://codeforces.me/contest/2075/submission/311165732 for those edge cases.

→ Reply
»
109 minutes ago, # |
← Rev. 4   Vote: I like it +11 Vote: I do not like it

Alternate solution for E: everything before $$$a_1 \oplus a_2 = b_1 \oplus b_2$$$ is the same. Now, let $$$g(n, m)$$$ denote the number of pairs $$$(i, j)$$$ such that $$$0 \le i < j \le n$$$ and $$$i \oplus j = m$$$.

First, I claim that $$$g(n, m) = g(n, 2^k)$$$ where $$$k$$$ is largest integer with $$$2^k \le m$$$. This is because $$$j \oplus 2^k < j \iff j \oplus m < j$$$, i.e. any number $$$j$$$ that can be xorred with $$$2^k$$$ can be xorred with $$$m$$$ and vice versa.

This already means that the number of quadruplets $$$(a_1, a_2, b_1, b_2)$$$ is $$$\sum_{k=0}^{\log \max} 2^k g(A, 2^k) g(B, 2^k)$$$, where a factor of $$$2^k$$$ comes from the fact that there are $$$2^k$$$ values of $$$m$$$ with this $$$k$$$.

All that remains is quickly evaluating $$$g(n, 2^k)$$$. This is simply the count of integers from $$$0$$$ to $$$n$$$ with $$$k$$$-th bit set because any number with the $$$k$$$-th bit on has a pair, and every pair contains exactly one number with the $$$k$$$-th bit on.

→ Reply
»
9 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

For C, can someone confirm that the following is an O(n+m) solution -- Suppose I create an array $$$cnt[]$$$ such that $$$cnt[j]$$$ denotes the number of paints that can paint at least $$$j$$$ fences (this can be done in O(n) time). Now I create another array sol[] such that

$$$sol[i]=cnt[n-i]+cnt[n-i+1]+\cdots+cnt[n-2]+cnt[n-1],$$$

then sol[i] denotes the number of solutions to the equation

$$$x_1+x_2=n,$$$

where

$$$1\leq x_1\leq i.$$$

This can also be done in O(n) time. Then, the answer is just the sum

$$$\sum_{1\leq i\leq m}sol[a_i],$$$

subtracting (2*a[i]-n+1) whenever 2*a[i]>=n (to account for x_1 and x_2 representing the same colour).

→ Reply