Krypton31's blog

By Krypton31, history, 2 months ago, In English

Can you please help me see my mistake, in Subarray Sums || It gives WA for 2 cases.


int main(){ FastIO; int n; ll x; cin>>n>>x; ll a[n]; ll prefix[n]; for(int i=0;i<n;i++){ cin>>a[i]; prefix[i] = a[i]; if(i>0) prefix[i]+=prefix[i-1]; } map<ll,ll>cache; int cnt =0; for(int i =0;i<n;i++){ cache[prefix[i]]+=1; if(prefix[i]==x and cache[0]==0) cnt+=1; else cnt+=cache[prefix[i]-x]; } cout<<cnt; return 0; }
 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I modified this part of the code and got accepted.

map<ll,ll>cache;
cache[0] = 1; 
  int cnt = 0;
  for(int i=0;i<n;i++){
    int need = x - prefix[i];
    cnt += cache[-need]; // Notice the minus right there
    cache[prefix[i]]++;
    //cache[prefix[i]]+=1;
    //if(prefix[i]==x and cache[0]==0) cnt+=1;
    //else cnt+=cache[prefix[i]-x];
  }
  cout<<cnt;
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey Thanks, can you please elaborate what was my mistake, like any edge cases also can you put simply why you did what you did?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    also why — sign tho, what difference does it make and I get that you added 0 for prefix(i)=x so what is wrong with the if condition of mine, plz help?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Your code will fail for testcases like these 5 100 100 100 100 100 100 because cache[0] = 0 initially so everytime after the first 100 we will add 1 to the ans due to if condition. So initially cache[0] should be made 1 and if condition should be removed. cache[prefix[i]]+=1; should be done at the end of the loop so as to manage testcases like 5 0 0 0 0 0 0 and cnt should be made ll.

      int main(){
        int n;
        ll x;
        cin>>n>>x;
        ll a[n];
        ll prefix[n];
        for(int i=0;i<n;i++){
          cin>>a[i];
          prefix[i] = a[i];
          if(i>0) prefix[i]+=prefix[i-1];
        }
        map<ll,ll>cache;
        cache[0] = 1;
        ll cnt =0;
        for(int i =0;i<n;i++){
          cnt+=cache[prefix[i]-x];
       
          cache[prefix[i]]+=1;
        }
        cout<<cnt;
        return 0;
      }