na

na

na

na

74Traktor never lets me down....

Yeah I tried it using two pointers but got wrong answer on 776th number of test case 2. Can you check my code, where am I wrong?

    cin >> n >> k;
    vll v(n), zero(n + 1, 0);
 
    rep(i,0,n) cin >> v[i];
 
    rep(i,0,n){
        sum += v[i];
        if(sum > k) {
            sum = 0;
            zero[i] = 1;
        }
    }
 
    per(i,n - 1,0){
        if(zero[i]) zero[i] = zero[i + 1] + 1;
        else zero[i] = zero[i + 1];
    }
 
    // rep(i,0,n) cout << zero[i] << " ";
    // cout << nL;
 
    sum = 0;
    l = 0;
    r = 0;
    while(l < n){
         while(r < n && sum + v[r] <= k){
            sum += v[r++];
        }
        
        ans += ((n - r - 1) - (r < n - 1 ? (zero[r + 1]) : (0))) + (r - l);
        // cout << r << " ";
        sum -= v[l++];
        if(r == n && sum <= k) ans++;
        // cout << ans << " " << l << nL;
    }
   
    cout << ans << nL;
   

can you please explain how?

This is my code: 271271875

So if we start at mushroom $$$i$$$ with $$$g=0$$$ before performing any operations we will hit $$$g=0$$$ again at some $$$j\geq{i}$$$.

There might be multiple possible values of $$$j$$$ for $$$i$$$ since $$$g$$$ might become zero multiple times over and over again.

We only need to calculate the smallest such $$$j$$$. Let that number be $$$l_i$$$.

If $$$j$$$ doesn't exist that means we got to the end of the array and still $$$g\leq{x}$$$. In that case we can assign $$$l_i=-1$$$.

vector<int> l(n, -1);
int j=0;
ll sum=0;
for(int i=0; i<n; i++) {
	while(j<n && sum<=x) {
		sum+=a[j];
		j++;
	}
	l[i]=j-1;
	if(sum<=x) {
		l[i]=-1;
		break;
	}
	sum-=a[i];
}

Now if we choose $$$l=i$$$, $$$r$$$ can't be $$$l_i$$$ because in that case g will result in zero. Now if we choose $$$l=i$$$, $$$r$$$ can't be $$$l_i$$$ because in that case g will result in zero.

But $$$l_i$$$ is not the only $$$r$$$ we aren't allowed to pick. Lets say we don't pick $$$r=l_i$$$ and instead go further. Next index $$$k$$$ when $$$g$$$ will hit $$$0$$$ will be

Now let $$$dp_i$$$ represent how many values $$$r\geq{i}$$$ we can't pick. The transition is $$$dp_i=1+dp_{l_i+1}$$$. Array $$$dp$$$ can be calculated in $$$O(n)$$$ by for loop going from last to first element.

Now we will for every $$$1\leq{l}\leq{n}$$$ calculate the number of possible values of $$$r$$$. It is equal to $$$n-l-dp_l$$$ (0-indexed). The total sum is the answer.

i did like this,idk what is the issue

cant we solve problem C like this-

1.first applying sliding window and count all the subarras having toxicity less then equal to x.

now it said process can continue and we have to see if at last it is not zero,so we calculate the min element less then or equal to x from end of the array, let kth posn.

2.and then again applying sliding window from start to kth posn to find all subarray whose sum>x.

then just add both 1 and 2.

no

010000 -> 011111 l = 2, r = 6

011111 -> 001111 l = 1, r = 2

s = 010000; l = 5, r = 6 => s = 010001; l = 4, r = 5 => s = 010011; l = 3, r = 4 => s = 010111; l = 2, r = 3 => s = 011111; l = 1, r = 2 => s = 001111 = t. The answer is "YES". i = 2 — the position of the first '1' in s, and there are only '0' in the interval [1, i) in t, so, according to given solution the answer is also "YES".

this problem is too troll, if it's placed as C i think i can prolly solve it in 10 min lol

hey can you share some resources to study for bitwise operation. I always find it difficult whenever i have to deal with these types of question

after solving it today, i also agree with you. the idea isn't that complicated

Real

Me!

you have to dp some way or the other

If we choose i as l, we have maximum n-i choices for r. (0<=i<n). When we take i as I and r as n-1 and if we calculate g for all positions from i to n-1, we may encounter ct positions where g is zero. This is a significant finding, as it means there are ct indices that cannot be r if i is chosen as l. To keep track of this crucial information, we introduce an array c[n], which stores the number of zeros encountered when i is chosen as I and r is chosen as n-1. Now, we only need to find array c[n]. Now, we will define an array sum[n], which will store g if we calculate it backward from n-1 to 0. Lets say the resulting array is something like this [-,-,-,-,0,-,-,-,0-,-,-,-] let say the position of zeros be x and y, (y>x). So for all indices x<i<=y, we take i as l and n-1 as r, then we will encounter only one position with g equals zero. Similarly, for all 0<=l<=x and r=n-1, we will encounter two indices with g=0. Extend this to a general case, and we have an array that gives c[i] (number of indices at which g=0 if l=i and r=n-1). Then we have ans=summation(n-i-c[i]).

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n,x;
        cin>>n>>x;
        int arr[n];
        for(int i(0);i<n;++i) cin>>arr[i];
        int sum[n]={0};
        int c[n]={0}; // counts the number of zeros from i to n-1
        sum[n-1]=arr[n-1];
        int ct=0; // counts number of zeros
        long long ans=0;
        for(int i(n-1);i>=0;--i){
            if(i!=(n-1)){
                sum[i]=(arr[i]+sum[i+1]);
                c[i]=c[i+1];
            }
            if(sum[i]>x) sum[i]=0;
            if(sum[i]==0){
                ++ct;
                c[i]=ct;
            }
        }
        for(int i(0);i<n;++i){
            ans+=(n-c[i]-i);
        }

        cout<<ans<<endl;
    }

    return 0;
}

Editorial means to solve for each component consisting of only black edges.

dp(i) means count of all good subarrays with i as starting point which is easier to do as transition is O(1) time comp. while if we take for dp(i) as count of good subarrays such that ending at i then transitions are not possible in O(1) but O(n) complexity as there are continuous ranges of index one or more j<=i at which we can always end at i with a nonzero value.

as size of the array and arr[i] both are up to 1e6, then how can we say that it won't give TLE ??

Is there any proof for this??

Please share it will he helpful

mod is m that we need to find

Note that we have chosen $$$x+1$$$ numbers, so by the pigeonhole principle, some two numbers will be equal modulo $$$x$$$.

There always is a solution

Because there are $$$x + 1$$$ numbers from $$$0$$$ to $$$x - 1$$$.

By starting from the (n-1) -th operation and working our way down to the first operation, we ensure that we can always find pairs of vertices to connect, gradually reducing the number of components until the graph is fully connected

how can we prove this ?

upd: Resolved

Thanks for explanation :)

Great explanation!

way better explanation than the editorial

Thank you so much

I have also used same logic..

Simpler implementation: MY SUBMISSION LINK

I’ve tried, but it seems to be wrong.I can’t guarantee that the graph is connected.The graph I make may contain loops.

In all, being 74 rounds means higher chance of being sponsored but higher chance of low quality.

Better quality of problems — higher chance of Global

That is really laughing.

Start deleting from the leaf nodes one by one . Then as soon as you get the required size, you can delete the entire tree.

can you suggest, how to handle bitwise problem efficiently during contest. They always makes me uncomfortable

The problem only happens when you use char array, suggested by my testings. I still don't know the cause though, if anyone knows please explain, thanks.

The problem occurs when you have an array of size exactly n for an n character long string. If you change from

    scanf("%d",&n);
    char s[n], t[n];
    scanf("%s",s);
    scanf("%s",t);

to

    scanf("%d",&n);
    char s[n+1], t[n+1];
    scanf("%s",s);
    scanf("%s",t);

it would work fine. I believe this happens because the last character of an array of char must be '\0' or null character but I don't know the details lol.