Educational Codeforces Round 143 Editorial

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Tutorial

Solution (Neon) 1

#include <bits/stdc++.h>

using namespace std;

int main() {
  auto ok = [](string s) {
    for (int i = 1; i < (int)s.size(); ++i)
      if (s[i - 1] == s[i]) return false;
    return true;    
  };
  
  int t;
  cin >> t;
  while (t--) {
    int n, m;
    string s, t;
    cin >> n >> m >> s >> t;
    bool f = false;
    for (int x = 0; x < 2; ++x) {
      string cs = s, ct = t;
      for (int i = 0; i < n; ++i) {
        f |= ok(cs) && ok(ct);
        ct.push_back(cs.back());
        cs.pop_back();
      }
      swap(n, m);
      swap(s, t);   
    }
    cout << (f ? "YES\n" : "NO\n");
  }
}

Solution (Neon) 2

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, m;
    string s, t;
    cin >> n >> m >> s >> t;
    reverse(t.begin(), t.end());
    s += t;
    int cnt = 0;
    for (int i = 1; i < n + m; ++i) cnt += s[i - 1] == s[i];
    cout << (cnt <= 1 ? "YES\n" : "NO\n");
  }
}

1795B - Ideal Point

Idea: BledDest

Tutorial

Solution (Neon)

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    int L = 0, R = 55;
    while (n--) {
      int l, r;
      cin >> l >> r;
      if (l <= k && k <= r)
        L = max(L, l), R = min(R, r);
    }
    cout << (L == R ? "YES\n" : "NO\n");
  }
}

1795C - Tea Tasting

Idea: BledDest

Tutorial

Solution (Neon)

#include <bits/stdc++.h>

using namespace std;

using li = long long;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<li> a(n), b(n);
    for (auto& x : a) cin >> x;
    for (auto& x : b) cin >> x;
    vector<li> sum(n + 1);
    for (int i = 0; i < n; ++i) sum[i + 1] = sum[i] + b[i];
    vector<li> cnt(n + 1), add(n + 1);
    for (int i = 0; i < n; ++i) {
      int j = upper_bound(sum.begin(), sum.end(), a[i] + sum[i]) - sum.begin() - 1;
      cnt[i] += 1;
      cnt[j] -= 1;
      add[j] += a[i] - sum[j] + sum[i];
    }
    for (int i = 0; i < n; ++i) {
      cout << cnt[i] * b[i] + add[i] << ' ';
      cnt[i + 1] += cnt[i];   
    }
    cout << '\n';
  }
}

1795D - Triangle Coloring

Idea: BledDest

Tutorial

Solution (BledDest)

#include <bits/stdc++.h>
 
using namespace std;

const int MOD = 998244353;

int add(int x, int y)
{
    return ((x + y) % MOD + MOD) % MOD;
}

int mul(int x, int y)
{
    return x * 1ll * y % MOD;   
}

int binpow(int x, int y)
{
    int z = 1;
    while(y)
    {
        if(y % 2 == 1) z = mul(z, x);
        x = mul(x, x);
        y /= 2;
    }
    return z;
}

int inv(int x)
{
    return binpow(x, MOD - 2);    
}

int divide(int x, int y)
{
    return mul(x, inv(y));
}

int main()
{
    int n;
    cin >> n;
    int ans = 1;
    for(int i = 1; i <= n / 6; i++)
        ans = mul(ans, divide(i + n / 6, i));
    for(int i = 0; i < n / 3; i++)
    {
        vector<int> a(3);
        for(int j = 0; j < 3; j++)
            cin >> a[j];
        int mn = *min_element(a.begin(), a.end());
        int cnt_min = count(a.begin(), a.end(), mn);
        ans = mul(ans, cnt_min);
    }
    cout << ans << endl;
}

1795E - Explosions?

Idea: BledDest

Tutorial

Solution (adedalic)

import java.util.*

fun main() {
    repeat(readln().toInt()) {
        val n = readln().toInt()
        var h = readln().split(' ').map { it.toInt() }

        val d = Array(2) { LongArray(n) { 0 } }
        for (tp in 0..1) {
            val s = Stack<Pair<Int, Int>>()

            for (i in h.indices) {
                while (s.isNotEmpty() && s.peek().first > h[i] - i)
                    s.pop()
                var j = maxOf(-1, i - h[i])
                if (s.isNotEmpty())
                    j = maxOf(j, s.peek().second)

                val len = (i - j).toLong()
                d[tp][i] = len * h[i] - len * (len - 1) / 2
                if (j >= 0 && len < h[i])
                    d[tp][i] += d[tp][j]

                s.push(Pair(h[i] - i, i))
            }
            h = h.reversed()
        }
        d[1] = d[1].reversedArray()

        var ans = 1e18.toLong()
        val sum = h.fold(0L) { total, it -> total + it }
        for (i in h.indices) {
            val cur = sum - d[0][i] - d[1][i] + 2 * h[i]
            ans = minOf(ans, cur)
        }
        println(ans)
    }
}

1795F - Blocking Chips

Idea: BledDest

Tutorial

Solution (awoo)

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < int(n); i++) 

vector<vector<int>> g;
vector<int> req;
vector<char> used;

vector<int> d;

bool dfs(int v, int p = -1){
    d[v] = 0;
    for (int u : g[v]) if (u != p){
        if (!dfs(u, v)) return false;
        if (!used[u]) d[v] = max(d[v], d[u] + 1);
    }
    if (req[v] == 0 || d[v] >= req[v]) return true;
    if (p == -1 || used[p]) return false;
    used[p] = true;
    req[p] = req[v] - 1;
    return true;
}

int main(){
    int t;
    scanf("%d", &t);
    while (t--){
        int n;
        scanf("%d", &n);
        g.assign(n, {});
        d.resize(n);
        forn(i, n - 1){
            int v, u;
            scanf("%d%d", &v, &u);
            --v, --u;
            g[v].push_back(u);
            g[u].push_back(v);
        }
        int k;
        scanf("%d", &k);
        vector<int> a(k);
        forn(i, k){
            scanf("%d", &a[i]);
            --a[i];
        }
        int l = 1, r = n;
        int res = 0;
        while (l <= r){
            int m = (l + r) / 2;
            used.assign(n, 0);
            req.assign(n, 0);
            forn(i, k){
                used[a[i]] = true;
                req[a[i]] = m / k + (i < m % k);
            }
            if (dfs(0)){
                res = m;
                l = m + 1;
            }
            else{
                r = m - 1;
            }
        }
        printf("%d\n", res);
    }
}

1795G - Removal Sequences

Idea: BledDest

Tutorial

Solution (awoo)

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < int(n); i++) 

typedef unsigned long long uli;

int main(){
    int t;
    scanf("%d", &t);
    while (t--){
        int n, m;
        scanf("%d%d", &n, &m);
        vector<int> a(n);
        forn(i, n) scanf("%d", &a[i]);
        vector<vector<int>> g(n);
        forn(i, m){
            int v, u;
            scanf("%d%d", &v, &u);
            --v, --u;
            g[v].push_back(u);
            g[u].push_back(v);
        }
        vector<char> rem(n);
        vector<int> d(n);
        forn(i, n) d[i] = g[i].size();
        queue<int> q;
        forn(i, n) if (a[i] == d[i]) q.push(i);
        vector<pair<int, int>> ord;
        while (!q.empty()){
            int v = q.front();
            q.pop();
            rem[v] = true;
            for (int u : g[v]) if (!rem[u]){
                --d[u];
                ord.push_back({v, u});
                if (d[u] == a[u])
                    q.push(u);
            }
        }
        reverse(ord.begin(), ord.end());
        vector<uli> mask(n);
        long long ans = n * 1ll * (n + 1) / 2;
        for (int l = 0; l < n; l += 64){
            int r = min(n, l + 64);
            for (int i = l; i < r; ++i)
                mask[i] = 1ull << (i - l);
            for (const pair<int, int> &it : ord)
                mask[it.first] |= mask[it.second];
            forn(i, n){
                ans -= __builtin_popcountll(mask[i]);
                mask[i] = 0;
            }
        }
        printf("%lld\n", ans);
    }
}

void solve() { ll n, x; cin >> n; ll a[n]; for (ll i = 0; i < n; i++) { cin >> a[i]; } multiset<ll> s; ll val = 0; for (ll i = 0; i < n; i++) { cin >> x; ll mn = min(x, a[i]), c = 0; s.insert(a[i] + val); auto it = s.begin(); vector<ll> toBeRemoved; while (1) { if (it == s.end()) break; if (*it - val <= x) { c += *it - val; toBeRemoved.push_back(*it); } else { break; } it++; } for (auto e : toBeRemoved) s.erase(e); val += x; c += s.size() * x; // c += mn; a[i] -= mn; cout << c << " "; } cout << "\n"; }

Comments (28)

Show archived | Write comment?

McPqndq

22 months ago, # |

Copy paste error in tutorial for F

→ Reply

awoo

22 months ago, # ^ |

Whoops, how did that happen. Fixed.

t.muksunov

+13

I like your profile picture

Rahul_abr

I found problem C difficult in this round.

Tale

I try problem C using segment tree and got AC.

here is the idea:

Link

rolandpetrean

that's just unnecessarily complicated tho

sahaun

Not really.

If you need to update and query a range, segment tree is intuitive. Adding a number and querying the sum in a range has is one the most common forms of segment trees. Also, you don't need to type a segment tree. It's just a copy-paste.

not_ahmed_hamed

My approach for problem C

hk2255

The time complexity is O(n^2) right? It's accepted?

It's O(Nlog(N))

for (auto e : toBeRemoved)
            s.erase(e);

erase takes O(logN) at the worst case (erase all elements that became 0)

c += s.size() * x; take the value x from all elements in the set that will not become zero after we take x (greater than x)

wittywho

please explain your approach

The array "a" stores some values ** consider a[0] this value will be reduced by all values in b -> b[0:n[ a[1] will be reduced by all values in b -> b[1:n[

consider b[1] b[1] will reduce values in a[1] and a[0]

so when you take b[i] which is x in my solution add it to variable "val" which store sum of values of b until i (I'm sure that val will reduce all previous "a" values with its value) so for each element in the set, when an element becomes zero that's mean I can't reduce it any more so I should remove it from the set but other elements in the set that when I reduce it by x, It won't be zero (c+= x*size). I'm very bad at explanation so if you don't understand tell me.

palindrome2024

← Rev. 4 →

BledDest i guess, there is a typo in a problem C editorial

" Now you want to find the largest j such that pref[ j-1 ]−pref[ i ] ≤ a[ i ]. Rewrite it as pref[ j-1 ] ≤ a[ i ] + pref[ i ] "

it should be pref[ j ] not pref[ j-1 ] because here pref[ j ] = b[ 0 ] + b[ 1 ] + b[ 2 ].......b[ j-1 ] any comment ?

Yeah, I think you are correct. Let me fix it real quick.

500_IQ

+11

I got enlightenment guys,
the technique which is know as difference array technique by commoners has actually a fancy name : DELTA ENCODING

Xu_Hongxi

Is there any better solution in problem G?

MikuNakano0505

maybe the difficulty gap between D&E was bigger than before (, that's probably because C was difficult and D was easier than usual .

Socrates1232

G's compression trick is truly beautiful. Still I wonder is a n*n bool matrix works too?(Once I test it out I'll post the result below this comment)

Nevermind. Can't apply bitwise or on bool array.

ChitreshApte

← Rev. 2 →

In tutorial of E, why would the explosion series stop when $$$h_{p - i} \le h_{p} - i$$$ Doesn't this mean the explosion can proceed more left?

Ahaooops

Can someone help to explain why the answer is n*(n+1)/2 — reachable pairs in problem G?

Oh, I've already understood, never mind ^_^. Btw, really elegant solution.

For G, Java don't have the function __builtin_popcountll and the same algorithm gets TLE at case 22(I compared the code with mine and the main parts are essentialy the same). Is there a java code that got accepted? Or should I just throw Java into a trash can and start using c++? And here's the code which got TLE at case 22. I even improved the edges iteration parts QAQ 194239334

BledDest

+26

Computing the number of bits set to 1 naively is too slow. Here are some ways to improve it if your language of choice doesn't support that function:

precalculate the number of bits set to 1 in all integers up to some number $$$2^k-1$$$. Let's say that $$$k = 16$$$. Then you can calculate the number of bits set to 1 in a 64-bit number in much fewer actions if you divide the number into blocks of $$$k$$$ bits (for $$$k = 16$$$, you need only $$$4$$$ blocks).
use something like a bitset (although if you use it, it might be better to deal with larger number of bits, not 64).

fakhrulsojib

In the 9th paragraph of the tutorial of E, shouldn't this be corrected like this?

The last question is finding for each i the closest j<i such that ~~a_j−i~~ a_j−j ≤ a_i−i. Note that...

Correct me if I am wrong.

lightmon

9 months ago, # |

C is a good problem for practising Segment Tree.

nandan_3352

7 months ago, # |

IN PROBLEM D: can anyone say why we are not considering pairing a triple with same color? Because "So, for each triple of vertices, there will be either one red vertex and two blue ones, or two red ones and one blue" from editorial. or why can't BBB RRB RRB RRB give maximum weight for sure in any case??

Verma_26

7 months ago, # ^ |

because then maximum weight will not be considered if we take all blue. read problem carefully

awoo's blog