Copy paste error in tutorial for F

I found problem C difficult in this round.

I try problem C using segment tree and got AC.

here is the idea:

My approach for problem C

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

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 ?

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

Is there any better solution in problem G?

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

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)

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?

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

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

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.

.

Problem C

include<bits/stdc++.h>

using namespace std;

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

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

My solution for problem C using Priority Queues. I myself don't know how I came up with that!

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner ab = new Scanner(System.in);
        int T = ab.nextInt();
        while (T-- > 0) {
            int N = ab.nextInt();
            long[] tea = new long[N];
            for(int i=0; i<N; i++) tea[i] = ab.nextInt();
            long[] cap = new long[N];
            for(int i=0; i<N; i++) cap[i] = ab.nextInt();

            PriorityQueue<Long> pq = new PriorityQueue<>();
            long bal = 0;
            for(int i=0; i<N; i++) {
                long ans = 0;
                while(!pq.isEmpty()) {
                    long avl = pq.peek() - bal;
                    if(avl > cap[i]) {
                        ans += (cap[i]*pq.size());
                        break;
                    } else ans += (pq.poll() - bal);
                }
                ans += Math.min(tea[i], cap[i]);
                bal += cap[i];
                if(tea[i] > cap[i]) pq.offer(tea[i] - cap[i] + bal);

                System.out.print(ans + " ");
            }

            System.out.println();
            
        }
    }
}

In problem D, we can observe a recurrence relation that defines the number of ways to color the (i)th triangle while maintaining a balance (j):

where ( f(i, j) ) represents the number of ways to color the (i)th triangle with a given balance (j). Each triangle has two possible colorings:

• (2 red + 1 black) → increases (j) by 1
• (2 black + 1 red) → decreases (j) by 1

Since we must use the same number of red and black colors overall, the final balance ( j ) must be zero after coloring all triangles.

Base Case

The base case is:

A straightforward dynamic programming approach would take ( O(N^2) ) time. However, with a key observation, we can optimize this.

Key Observations

Expanding the recurrence further, we get:

where ( c[i] ) represents the number of ways to color the (i)th triangle (which belongs to {1,2,3}, as evident from the problem constraints).

Continuing this expansion, we realize that the problem reduces to finding the number of ways to go from ( j = 0 ) to ( j = 0 ) in exactly ( N/3 ) steps, where each step can increment or decrement ( j ) by 1. The total number of ways is then multiplied by the product of ( c[i] ) from 1 to ( N/3 ).

Pascal’s Triangle Connection

Drawing the DP table reveals a structure similar to Pascal’s Triangle. The required answer corresponds to the middle element of the (( N/3 + 1 ))th row of Pascal’s Triangle. Since ( N/3 + 1 ) is always odd, this middle element always exists.

Final Answer

This reduces the time complexity to O(N) compared to the naive O(N^2) DP approach.

Problem C was gold. Here is my binary search solution(I did all brainstorming of edge cases and passed in first try)#include <bits/stdc++.h> using namespace std; ~~~~~~ int main() { int t; cin>>t; while(t--){ int n; cin>>n; vector a(n),b(n); for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++) cin>>b[i]; vector fix(n+1,0); vector residual(n,0); vector cap_sum(n,0); cap_sum[0]=b[0]; for(int i=1;i<n;i++){ cap_sum[i]=cap_sum[i-1]+b[i]; } long long int last=0; for(int i=0;i<n;i++){ long long int cur=last+a[i]; int idx = lower_bound(cap_sum.begin(),cap_sum.end(),cur)-cap_sum.begin(); if(idx<=i){ residual[i]+=a[i]; } else{ fix[i]+=1; if(idx>=n) fix[n]-=1; else if(cap_sum[idx]>cur){ fix[idx]-=1; if(idx-1>=0) residual[idx]+=cur-cap_sum[idx-1]; } else{ fix[idx+1]-=1; } } last=cap_sum[i]; }

       for(int i=1;i<=n;i++) fix[i]+=fix[i-1];
       vector<long long> ans(n,0);
       for(int i=0;i<n;i++){

// cout<<"fix:"<<fix[i]<<" "; // cout<<"res:"<<residual[i]<<" "<<endl; ans[i]=fix[i]*b[i]+residual[i]; } for(int i=0;i<n;i++) cout<<ans[i]<<" "; cout<<endl;

    }

} ~~~~~~

Hello guys, I am seeking help for best practices when dealing with bounds and prefix sums, here's my submission link for problem C: https://codeforces.me/contest/1795/submission/352586130. I made few bounds check to fix OOB accesses on the fly and made it pass, but this doesn't seem like a good practice in long run. Thanks!