#	User	Rating
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

#	User	Contrib.
1	maomao90	174
2	awoo	164
3	adamant	161
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	SecondThread	147
9	orz	146
10	pajenegod	145

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"; }

define int long long

int binary_search(int i,vectora,vectorpref,int s) { int l=i; int r=a.size()-1; int ans=-1; while(l<=r) { int mid=(l+r)/2; if(pref[mid]-s<=a[i]) { ans=mid; l=mid+1; } else { r=mid-1; } } return ans; } void solve() { int n; cin>>n; vectora(n),b(n); for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++) cin>>b[i]; vectorpref(n); int sum=0; for(int i=0;i<n;i++) { sum+=b[i]; pref[i]=sum; } int i=0; vectorind(n+1,0); vectorans(n+1,0); while(i<n) { int s=i>0?pref[i-1]:0; //cout<<s<<endl; int t=binary_search(i,a,pref,s); //cout<<t<<endl; if(t!=-1) { ind[t+1]--; ans[t+1]+=a[i]-pref[t]+s; } else { ind[i]--; ans[i]+=a[i]; } i++; } sum=0; for(int i=0;i<n;i++) { sum+=ind[i]; ind[i]=i+1+sum; // cout<<ind[i]<<" "<<sum<<endl; } // cout<<endl; for(int i=0;i<n;i++) { ans[i]=ind[i]*b[i]+ans[i]; } for(int i=0;i<n;i++) cout<<ans[i]<<" "; cout<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); int t; cin>>t; for(int i=0;i<t;i++) solve(); } why I am getting TLE even though my solution being o(nlog(n))

Comments (28)

Show archived | Write comment?

McPqndq

14 months ago, # |

Copy paste error in tutorial for F

→ Reply

awoo

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